- Understand common patterns: duplicates, rotation, merging, partitioning
- Learn string patterns: anagrams, palindromes, longest unique substring
- See Kadane's algorithm for max subarray in O(n)
Advanced Array and String Concepts
You've learned basics. Now let's tackle patterns that show up in real problems.
Multi-dimensional Arrays
A 2D array is an array of arrays. Think of it as a grid or matrix.
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
matrix[0][0] # 1 (row 0, column 0)
matrix[1][2] # 6 (row 1, column 2)
matrix[2][1] # 8 (row 2, column 1)
Traversing:
for row in matrix:
for element in row:
print(element, end=' ')
print()
Or with indices:
for i in range(len(matrix)): # Rows
for j in range(len(matrix[i])): # Columns
print(matrix[i][j], end=' ')
print()
Memory layout: Row-major order. All of row 0, then all of row 1, etc.
[1, 2, 3, 4, 5, 6, 7, 8, 9]
To access matrix[i][j] in a matrix with cols columns: base + (i × cols + j) × element_size.
Still O(1) access.
Common Array Patterns
Finding Duplicates
Naive: Check every pair. O(n²).
Better: Use a set.
def has_duplicates(arr):
seen = set()
for num in arr:
if num in seen:
return True
seen.add(num)
return False
O(n) time, O(n) space.
If array values are in a known range (say, 1 to n): use the array itself.
def find_duplicate(arr):
# Values are 1 to n, array has n+1 elements
# Mark visited by negating
for num in arr:
index = abs(num)
if arr[index] < 0:
return index # Duplicate
arr[index] = -arr[index]
O(n) time, O(1) space (modifies array).
Rotating an Array
Rotate [1, 2, 3, 4, 5] by 2 positions right: [4, 5, 1, 2, 3].
Naive: Create a new array, copy in rotated order. O(n) time and space.
In-place: Reverse parts.
def rotate(arr, k):
k = k % len(arr) # Handle k > len
# Reverse entire array
reverse(arr, 0, len(arr) - 1)
# Reverse first k elements
reverse(arr, 0, k - 1)
# Reverse remaining
reverse(arr, k, len(arr) - 1)
def reverse(arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
For [1, 2, 3, 4, 5], k=2:
- Reverse all:
[5, 4, 3, 2, 1] - Reverse first 2:
[4, 5, 3, 2, 1] - Reverse remaining:
[4, 5, 1, 2, 3]
O(n) time, O(1) space.
Merging Two Sorted Arrays
You have [1, 3, 5] and [2, 4, 6]. Merge into [1, 2, 3, 4, 5, 6].
def merge(arr1, arr2):
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# Add remaining
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
O(n+m) time, O(n+m) space.
This is the "combine" step of merge sort.
Partitioning (Quicksort's Core)
Partition around a pivot: smaller elements left, larger right.
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
O(n). Single pass.
After partitioning [3, 7, 1, 9, 2] with pivot 2:
- Result:
[1, 2, 3, 9, 7](2 is in final position, smaller left, larger right)
Common String Patterns
Checking if Two Strings are Anagrams
Anagrams: same letters, different order. "listen" and "silent".
Approach 1: Sort both. O(n log n).
def are_anagrams(s1, s2):
return sorted(s1) == sorted(s2)
Approach 2: Count characters. O(n).
def are_anagrams(s1, s2):
if len(s1) != len(s2):
return False
count = {}
for char in s1:
count[char] = count.get(char, 0) + 1
for char in s2:
if char not in count or count[char] == 0:
return False
count[char] -= 1
return True
Palindrome Check
Already covered with two pointers. O(n).
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
Longest Substring Without Repeating Characters
"abcabcbb" → "abc" (length 3).
Use sliding window:
def longest_unique_substring(s):
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
O(n). Each character is added and removed at most once.
String Compression
"aaabbcccc" → "a3b2c4".
def compress(s):
if not s:
return ""
result = []
count = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
count += 1
else:
result.append(s[i - 1] + str(count))
count = 1
result.append(s[-1] + str(count))
compressed = ''.join(result)
return compressed if len(compressed) < len(s) else s
O(n).
Dynamic Programming on Arrays
Kadane's Algorithm (Max Subarray Sum)
Find contiguous subarray with maximum sum.
def max_subarray_sum(arr):
max_ending_here = max_so_far = arr[0]
for i in range(1, len(arr)):
max_ending_here = max(arr[i], max_ending_here + arr[i])
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
For [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
- Max subarray:
[4, -1, 2, 1]with sum 6.
O(n) time, O(1) space.
The idea: at each position, decide whether to extend the current subarray or start a new one.
Longest Increasing Subsequence (LIS)
For [10, 9, 2, 5, 3, 7, 101, 18], LIS is [2, 3, 7, 101] (length 4).
Dynamic programming approach: O(n²).
def lis_length(arr):
if not arr:
return 0
dp = [1] * len(arr)
for i in range(1, len(arr)):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Better approach with binary search: O(n log n). (More advanced.)
Practical Tips
Avoid unnecessary copies: Modifying in-place saves space.
Use built-in methods: sorted(), str.join(), set() are optimized.
Watch for edge cases: Empty arrays/strings, single elements, all duplicates.
Think about constraints: If values are bounded, you can use array indexing instead of hash maps.
Two pointers and sliding window solve many problems efficiently. Recognize the pattern.
The Takeaway
Advanced array/string problems often combine:
- Basic operations (access, search, insert)
- Patterns (two pointers, sliding window, partitioning)
- Data structures (sets, hash maps for counting/tracking)
- Algorithms (binary search, DP, greedy)
Practice these patterns, and you'll solve most array/string problems you encounter.