Top 12 Array Interview Problems: The Patterns Behind Them

Arrays show up in roughly half of all coding interview problems. Not because interviewers lack imagination, but because these top array interview problems all run on the same dozen patterns, dressed in different costumes. Solve one Two Sum variant and you've built a reflex that handles dozens of "find a pair" problems. Understand why Kadane's works and you'll see it hiding in stock profit, circular subarrays, and product problems.

The problem isn't the algorithm. The problem is recognizing which algorithm to reach for before you start typing.

The 12 at a Glance

#	Problem	Difficulty	Pattern
1	Two Sum	Easy	Hash map complement
2	Best Time to Buy and Sell Stock	Easy	Running minimum, single pass
3	Contains Duplicate	Easy	Hash set membership
4	Maximum Subarray	Easy	Kadane's 1D DP
5	Product of Array Except Self	Medium	Prefix and suffix products
6	3Sum	Medium	Sort + two pointers
7	Container With Most Water	Medium	Converging pointers, greedy
8	Subarray Sum Equals K	Medium	Prefix sum + hash map
9	Search in Rotated Sorted Array	Medium	Binary search with rotation
10	Merge Intervals	Medium	Sort by start, scan
11	Trapping Rain Water	Hard	Two pointers, bottleneck argument
12	Sliding Window Maximum	Hard	Monotonic deque

---

Easy Array Problems: These Should Feel Automatic

"Should feel automatic" means you should solve them in under five minutes without much deliberation. Not because they're trivial, but because the pattern is a primitive. If any of the next four still feel like open problems, that's where to start.

Two Sum

The brute force checks every pair: O(n²). The O(n) insight is to store each element's complement (target minus current) in a hash map so every future lookup is O(1).

Walk the array once. For each element, check whether its complement already exists in the map. If yes, return the pair. If no, store the current element and continue.

One edge case candidates miss: the same index can't be used twice. Check the map before inserting the current element. Otherwise, when target == 2 * nums[i], an element matches itself.

Reach for this pattern any time the problem asks you to find a pair with some property.

Best Time to Buy and Sell Stock

You must buy before selling. Comparing every buy-sell pair is O(n²). The O(n) trick is to track the minimum price seen so far. For each day, profit is today's price minus that running minimum.

One pass, O(1) extra space. The same idea, tracking the best left context as you scan right, shows up in problems asking for the furthest valid left boundary or the cheapest prior state.

Contains Duplicate

Add each element to a set as you scan. Return true the moment you see an element already in the set. O(n) time, O(n) space.

The follow-up you'll likely hear: can you do it in O(1) space? Sort the array and check adjacent elements. O(n log n), no extra memory. Name both and say which tradeoff matters under which constraints.

Maximum Subarray

Kadane's algorithm makes a local decision at every index: extend the previous subarray, or start fresh from here.

max_sum = current = nums[0]
for num in nums[1:]:
    current = max(num, current + num)
    max_sum = max(max_sum, current)
return max_sum

Initialize to nums[0], not 0. If every element is negative, the answer is the least-negative element, not zero. Initializing to zero silently produces a wrong answer on all-negative inputs. It's the single most common bug on this problem.

A deeper walkthrough of the proof and the circular subarray variant is in Kadane's algorithm.

---

Medium Problems: Pattern Recognition Is the Whole Job

Real post from r/leetcode. If the Easy problems are taking you 90 minutes each, the patterns below are your immediate priority.

The gap between easy and medium is not about algorithm difficulty. It's about whether you spot the pattern before you start typing. Mediums don't announce what they are. You have to read the constraints and the shape of the problem, then make a call.

Product of Array Except Self

The constraint says no division. Two passes solve it without any. First pass left to right: for each index i, store the product of all elements to its left. Second pass right to left: multiply by the running product of everything to its right.

result = [1] * len(nums)
left = 1
for i in range(len(nums)):
    result[i] = left
    left *= nums[i]
right = 1
for i in range(len(nums) - 1, -1, -1):
    result[i] *= right
    right *= nums[i]
return result

The output array counts as O(1) auxiliary space by convention. Interviewers will ask you to state your space complexity. "The output array doesn't count" is the expected answer here.

The underlying pattern is prefix-and-suffix decomposition. It shows up whenever an element depends on the product, sum, or max of everything else in the array.

3Sum

Fix one element. Run two pointers on the rest of the sorted array to find pairs summing to its negation. Most candidates think the two-pointer part is where they'll fail. It isn't. The real challenge is duplicate handling, and that's what silently breaks most solutions.

After finding a valid triple, skip over equal values at both pointers before continuing. Also skip equal values at the outer loop when the index is above zero.

nums.sort()
result = []
for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    lo, hi = i + 1, len(nums) - 1
    while lo < hi:
        s = nums[i] + nums[lo] + nums[hi]
        if s == 0:
            result.append([nums[i], nums[lo], nums[hi]])
            while lo < hi and nums[lo] == nums[lo + 1]: lo += 1
            while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1
            lo += 1; hi -= 1
        elif s < 0:
            lo += 1
        else:
            hi -= 1
return result

This is the sort-then-two-pointer template. See two-pointer technique for how the converging pointer pattern extends to other variants.

Container With Most Water

Two pointers starting at opposite ends. Move the shorter line inward. The correctness argument: area is always bounded by the shorter line. Moving the taller pointer can only decrease width while height stays capped by the other side. Moving the shorter pointer gives some chance of improvement.

This is the exchange argument applied to array pointers. It shows up anywhere greedy pointer movement needs formal justification. Articulate it out loud in the interview. The reasoning matters as much as the code.

Subarray Sum Equals K

The prefix sum up to index j minus the prefix sum up to index i equals the subarray sum from i+1 to j. Track prefix sums in a hash map. For each index, check whether current_sum - k already exists in the map. Start the map with {0: 1} to handle subarrays starting at index 0.

count, prefix = 0, 0
seen = {0: 1}
for num in nums:
    prefix += num
    count += seen.get(prefix - k, 0)
    seen[prefix] = seen.get(prefix, 0) + 1
return count

Any time you see "subarray with some sum property," reach for prefix sums first. More patterns in prefix sum problems.

Search in Rotated Sorted Array

A rotated sorted array is still half sorted at any midpoint. Identify which half is cleanly sorted. If the target falls inside it, search there. Otherwise search the other half. Full binary search, one extra conditional.

If nums[lo] <= nums[mid], the left half is sorted. Target in [nums[lo], nums[mid]) means go left; otherwise go right. Mirror the logic when the right half is sorted.

The rotation doesn't break the binary search invariant. It just requires one more check before deciding which half to discard. The systematic approach is in binary search invariant.

Merge Intervals

Sort intervals by start time. Then scan: if the current interval starts at or before the last merged interval's end, they overlap. Merge them by updating the last end to max(current_end, last_end). Without the max(), a fully contained interval silently truncates the result.

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])
return merged

Sorting turns O(n²) pairwise overlap checks into an O(n) linear scan. This pattern appears across scheduling, meeting room, and event problems.

---

Hard Problems: The Non-Obvious Reframings

The word "hard" on LeetCode doesn't mean genius required. It usually means the non-obvious reframing is further from the surface. The brute force is obvious. The optimization requires a different way of thinking about the problem.

Trapping Rain Water

Water at position i is bounded by min(left_max[i], right_max[i]) - height[i]. Precomputing both max arrays takes O(n) time and O(n) space. Fine. That's a valid solution.

The two-pointer improvement: if left_max < right_max, water at the left pointer is fully determined. It is left_max - height[left]. You don't need the actual right maximum, only the guarantee that it's at least as large.

Move the pointer on the smaller-max side inward, compute its contribution, update the running max. O(n) time, O(1) space. The insight is the bottleneck argument: when one side constrains the result completely, you can act on it without knowing the other side exactly.

This sounds obvious once you see it. It takes most people three reads to actually believe it.

You, reading the Trapping Rain Water problem and wondering why moving the smaller pointer works.

Sliding Window Maximum

Naive rescanning gives O(nk). A monotonic deque solves this in O(n) by storing only candidates that could still be the window maximum.

When a new element arrives, pop every element from the back that is smaller. They can never be the max while the new element is in the window. The front of the deque is always the current window maximum. Evict from the front when an index falls outside the window.

from collections import deque
dq, result = deque(), []
for i, num in enumerate(nums):
    while dq and nums[dq[-1]] < num:
        dq.pop()
    dq.append(i)
    if dq[0] < i - k + 1:
        dq.popleft()
    if i >= k - 1:
        result.append(nums[dq[0]])
return result

Each element is pushed and popped at most once. O(n) total. Whenever a problem asks for the max or min over a sliding window, this is the structure to reach for.

---

Read the Signal Before You Code

Interviewers watch whether you recognize the pattern before you start typing. That signal matters as much as whether you finish. These are also the LeetCode array problems that appear most consistently across interview loops at every tier of company.

Sorted input suggests two pointers or binary search. "Subarray sum" suggests prefix sums. A fixed-size window with a max or min suggests a monotonic deque. Two elements that should add to something suggests a hash map.

The routine: state the brute force, name what makes it slow, then identify the data structure that removes the redundancy. That progression is what gets written in the feedback doc.

If you want to practice explaining these patterns out loud under interview conditions, SpaceComplexity runs voice-based DSA mock interviews with rubric-based feedback on communication, problem-solving, code quality, and testing.

Further Reading

• LeetCode: Array problems
• Wikipedia: Maximum subarray problem (Kadane's algorithm)
• Wikipedia: Prefix sum
• Wikipedia: Dutch national flag problem
• GeeksforGeeks: Two pointers technique