Array problems are the most common category in coding interviews, appearing in over 40% of questions. This guide organizes array problems by technique rather than difficulty, giving you a systematic approach to recognize and solve any array problem you encounter.
Hash Map Technique
Use a hash map for O(1) lookups when the brute force involves searching for a complement or counting occurrences. Two Sum: for each element, check if (target – element) exists in the map. If yes, found. If no, add element to map. O(N). Contains Duplicate: add elements to a set. If already present, duplicate found. O(N). Longest Consecutive Sequence: add all elements to a set. For each element that is the start of a sequence (element-1 not in set), count consecutive elements. O(N). Subarray Sum Equals K: prefix sum + hash map (covered in our Prefix Sum guide). O(N). Top K Frequent Elements: count frequencies with a hash map, then use a min-heap of size K or bucket sort. O(N log K) or O(N). Key insight: when the brute force is O(N^2) because of a nested search, a hash map reduces the inner search to O(1).
Sorting Technique
Sorting transforms random data into structured data, enabling efficient algorithms. 3Sum: sort the array. Fix one element, use two pointers (opposite direction) on the remaining. Skip duplicates. O(N^2). Meeting Rooms: sort intervals by start time. Check for overlaps (current.start “34” because “934” > “349”. O(N log N). Valid Anagram: sort both strings and compare. O(N log N). Or use frequency array: O(N). H-Index: sort citations descending. The h-index is the largest h where citations[h-1] >= h. O(N log N). Or counting sort: O(N). Key insight: after sorting, related elements are adjacent, enabling linear scans. Sorting adds O(N log N) but often reduces the overall complexity from O(N^2).
Two Pointers Technique
Two pointers work on sorted arrays or when scanning from both directions. Container With Most Water: left and right pointers. Area = min(height[left], height[right]) * (right – left). Move the shorter side inward (the only way to potentially increase area). O(N). Trapping Rain Water: for each position, water = min(max_left, max_right) – height. Two-pointer approach: left and right pointers. If height[left] < height[right]: water at left = left_max – height[left]. Advance left. Else: water at right = right_max – height[right]. Advance right. O(N), O(1) space. Remove Duplicates from Sorted Array: slow pointer marks the write position. Fast pointer scans. When a new value is found, write at slow and advance. O(N). Move Zeroes: same pattern. Write non-zero elements at slow pointer, fill remaining with zeros. Sort Colors (Dutch National Flag): three pointers partition 0s, 1s, and 2s. O(N). Key insight: two pointers avoid nested loops by maintaining a state relationship between the pointers.
Kadane Algorithm and Subarray Maximum
Kadane algorithm finds the maximum subarray sum in O(N). At each position: either extend the current subarray or start a new one. current_sum = max(nums[i], current_sum + nums[i]). Track the global maximum. Why it works: if current_sum becomes negative, any future subarray including it would be smaller than starting fresh. So reset. Variations: (1) Maximum Product Subarray: track both current_max and current_min (a negative times a negative becomes positive). current_max = max(nums[i], current_max * nums[i], current_min * nums[i]). (2) Maximum Circular Subarray Sum: the answer is either: max subarray (standard Kadane) OR total_sum – min subarray (the maximum wrapping subarray is the complement of the minimum non-wrapping subarray). (3) Maximum Sum with at most K elements: sliding window of size K. (4) Minimum Size Subarray Sum: variable-size sliding window (expand right, shrink left when sum >= target). Key insight: Kadane is a special case of DP where the state depends only on the previous element. The “extend or restart” decision captures the optimal substructure.
In-Place and Cyclic Techniques
Modify the array in-place without extra space. Rotate Array by K: three reverses. Reverse entire array, reverse first K, reverse remaining. O(N), O(1) space. Or cyclic replacement: move each element to its destination (i + K) % N. Find the Duplicate Number (N+1 numbers in range [1,N]): Floyd cycle detection on the “linked list” formed by f(x) = nums[x]. The cycle entry is the duplicate. O(N), O(1) space. First Missing Positive: place each number in its correct position (nums[i] should be at index nums[i]-1). Iterate: if nums[i] is in range [1, N] and not in the correct position, swap. After positioning: the first index where nums[i] != i+1 is the answer. O(N), O(1) space. Set Matrix Zeroes: use first row and column as markers. First pass: mark. Second pass: zero based on markers. O(1) extra space. Product of Array Except Self: two-pass (left products then right products). O(N), O(1) extra space (using the result array). Key insight: when O(1) space is required, use the array itself as storage. Cyclic swaps place elements at correct indices. Multiple passes avoid the need for auxiliary data structures.
Drill the patterns next:
