Array problems are the most common category in coding interviews, appearing in over 40% of questions. This comprehensive 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.