Array Interview Problems: The 12 Patterns That Solve Almost All of Them

Arrays are the first topic in every DSA sheet and the most common topic in online assessments and first coding rounds, from TCS NQT to Amazon and Google. The trap is treating each question as unique. Interviewers draw from a small number of underlying techniques, dressed up in different stories. Once you can map "maximum profit from one buy and one sell" to "Kadane on price differences", or "smallest missing positive" to "put each value at its own index", array rounds become recognition plus clean implementation.

This guide is that map. For each of the 12 patterns: how to recognise it, one representative problem solved fully, and the related problems it unlocks. If you are new to complexity analysis, skim Big-O explained first.

How to Spot the Right Array Pattern From the Problem Statement

Pattern 1: Two Pointers on a Sorted Array

Signal: sorted input (or you can sort), and you are looking for a pair or triplet, or removing elements in place. Two indices move toward each other (opposite ends) or in the same direction (read/write pointers).

Representative problem: Two Sum II (sorted input). Given sorted nums and target, return the indices of two numbers that add up to target. If the current sum is too small, only moving left right can increase it; if too large, only moving right left can decrease it. Each step discards one element safely, so the scan is O(n).

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1
        else:
            right -= 1
    return []

#include <vector>
using namespace std;

vector<int> twoSumSorted(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        long long s = (long long)nums[left] + nums[right];   // avoid int overflow
        if (s == target) return {left, right};
        if (s < target) ++left; else --right;
    }
    return {};
}

Same-direction variant: Move Zeroes and Remove Duplicates use a write pointer that marks where the next kept element goes, while a read pointer scans. Extensions: 3Sum (fix one element, two-pointer the rest, skip duplicates), Container With Most Water (move the shorter wall). The two pointers deep dive covers proofs of why discarding is safe.

Complexity: O(n) time, O(1) space (plus O(n log n) if you have to sort).

Pattern 2: Sliding Window for Contiguous Subarrays

Signal: "longest/shortest/maximum contiguous subarray such that..." where the condition is monotonic: extending the window only makes the sum or count grow. That is guaranteed when values are non-negative.

Representative problem: Minimum Size Subarray Sum (LeetCode 209). Positive integers, find the shortest subarray with sum at least target. Expand right every step; while the window is valid, record its length and shrink from the left.

def min_subarray_len(target, nums):
    best = float("inf")
    left = window = 0
    for right, x in enumerate(nums):
        window += x
        while window >= target:
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

#include <algorithm>
#include <climits>

int minSubArrayLen(int target, const vector<int>& nums) {
    int best = INT_MAX, left = 0;
    long long window = 0;
    for (int right = 0; right < (int)nums.size(); ++right) {
        window += nums[right];
        while (window >= target) {
            best = min(best, right - left + 1);
            window -= nums[left++];
        }
    }
    return best == INT_MAX ? 0 : best;
}

Dry run with target = 7, nums = [2, 3, 1, 2, 4, 3]:

Each element enters and leaves the window at most once: O(n) time even with the nested while. Fixed-size windows (maximum sum of k consecutive elements) are the simpler cousin: add the new element, subtract the one leaving. More variations live in the sliding window guide.

Pattern 3: Prefix Sums for Range Queries

Signal: repeated sum queries over ranges of a static array, or "pivot/equilibrium index". Build prefix[i] = sum of the first i elements; then the sum of nums[l..r] is prefix[r+1] - prefix[l] in O(1).

class RangeSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def query(self, l, r):          # inclusive l..r
        return self.prefix[r + 1] - self.prefix[l]

def pivot_index(nums):
    total, left = sum(nums), 0
    for i, x in enumerate(nums):
        if left == total - left - x:
            return i
        left += x
    return -1

The extra leading zero (size n+1) removes every "if l == 0" special case. The 2D version, P[i][j] = sum of the top-left rectangle, answers submatrix sums with inclusion-exclusion. The difference array is the inverse trick: to add v to every element in [l, r] for many updates, do diff[l] += v; diff[r+1] -= v and take one prefix sum at the end (Corporate Flight Bookings, Car Pooling). See prefix sum interview problems for more.

Pattern 4: Prefix Sum + Hashmap for Exact-Sum Subarrays

Signal: count or find subarrays with sum exactly K, divisible by K, or equal numbers of 0s and 1s, especially when negatives are present. A subarray (j, i] sums to K exactly when prefix[i] - prefix[j] = K, i.e. when we have previously seen prefix value prefix[i] - K.

Representative problem: Subarray Sum Equals K (LeetCode 560).

def subarray_sum(nums, k):
    count = prefix = 0
    seen = {0: 1}                    # empty prefix: lets subarrays starting at index 0 count
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

#include <unordered_map>

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<long long, int> seen{{0, 1}};
    long long prefix = 0;
    int count = 0;
    for (int x : nums) {
        prefix += x;
        auto it = seen.find(prefix - k);
        if (it != seen.end()) count += it->second;
        ++seen[prefix];
    }
    return count;
}

Dry run with nums = [1, 2, 3], k = 3: prefix 1 looks up -2 (none); prefix 3 looks up 0 (found once, count 1, the subarray [1,2]); prefix 6 looks up 3 (found once, count 2, the subarray [3]). Answer 2.

Variants: store the first index of each prefix instead of a count to get the longest subarray with sum K; store prefix % k for divisibility (normalise negative remainders in Java/C++ with ((p % k) + k) % k); map 0 to -1 and look for prefix 0 for "equal 0s and 1s" (Contiguous Array). The order of the two lines inside the loop matters: look up before inserting the current prefix, or k = 0 counts empty subarrays.

Pattern 5: Kadane's Algorithm for Maximum Subarray

Signal: maximum (or minimum) sum of a contiguous subarray. At each index decide: extend the best subarray ending at the previous index, or start fresh here. That is a one-variable DP.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)      # extend or restart
        best = max(best, cur)
    return best

long long maxSubArray(const vector<int>& nums) {
    long long best = nums[0], cur = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        cur = max((long long)nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}

Dry run on [-2, 1, -3, 4, -1, 2, 1, -5, 4]: cur goes -2, 1, -2, 4, 3, 5, 6, 1, 5 and best ends at 6 (subarray [4, -1, 2, 1]). Initialising with nums[0] rather than 0 handles all-negative arrays correctly, a very common bug.

Disguises: Best Time to Buy and Sell Stock (track the minimum price so far, which is Kadane on daily differences), Maximum Sum Circular Subarray (max of normal Kadane and total minus minimum subarray, unless all negative), Maximum Product Subarray (track both max and min because a negative flips them). The full treatment is in Kadane's algorithm explained.

Pattern 6: Hash Set and Hash Map Lookups

Signal: unsorted data, and you need "have I seen the complement / neighbour / duplicate before?" in O(1). Trading O(n) memory for O(n) time is the most common optimisation step in interviews.

Representative problem: Longest Consecutive Sequence (LeetCode 128), required in O(n), so sorting is out.

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:          # x starts a run; only start counting here
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best

The x - 1 not in s check is the whole trick: each run is walked once from its start, so total work is O(n) despite the nested loop. Two Sum is the canonical member of this family; see Two Sum explained. For how hashmaps work internally and when they degrade, read the hashing guide.

Pattern 7: Cyclic Sort and Index Marking (Values in 1..n)

Signal: values are in range 1..n (or 0..n) and you must find missing or duplicate numbers in O(n) time and O(1) extra space. Use the array itself as the hash table: value v belongs at index v - 1.

Representative problem: First Missing Positive (LeetCode 41, Hard).

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1                    # compute target index first
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i)
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
            swap(nums[i], nums[nums[i] - 1]);
    for (int i = 0; i < n; ++i)
        if (nums[i] != i + 1) return i + 1;
    return n + 1;
}

Every swap puts at least one value in its final position, so there are at most n swaps in total: O(n). The nums[nums[i]-1] != nums[i] guard prevents infinite loops on duplicates.

Index marking is the sibling trick: for "find all duplicates" with values 1..n, negate nums[abs(v) - 1] when you see v; if it is already negative, v is a duplicate. Related: Missing Number (also solvable with XOR or the n(n+1)/2 formula), Find All Numbers Disappeared, Set Mismatch, Find the Duplicate Number (which forbids modifying the array, so use Floyd's cycle detection instead).

Pattern 8: Dutch National Flag (Three-Way Partition)

Signal: partition an array into two or three groups in place, in one pass. Sort Colors (0s, 1s, 2s) is the classic; quicksort's 3-way partition and "move negatives before positives" are relatives.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    # invariant: [0,low) are 0s, [low,mid) are 1s, (high,end] are 2s, [mid,high] unknown
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                # do NOT advance mid: the swapped-in value is unexamined

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = (int)nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) swap(nums[low++], nums[mid++]);
        else if (nums[mid] == 1) ++mid;
        else swap(nums[mid], nums[high--]);
    }
}

Stating the invariant out loud is what interviewers want to hear; it also explains the asymmetry (why mid advances after swapping with low but not with high: the element coming from low is already known to be a 1).

Pattern 9: Prefix and Suffix Passes

Signal: the answer at index i depends on aggregates of everything to its left and everything to its right. Do one pass left to right, one right to left, and combine.

Representative problem: Product of Array Except Self (no division, O(1) extra space apart from the output).

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):              # out[i] = product of everything left of i
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):  # multiply in product of everything right of i
        out[i] *= right
        right *= nums[i]
    return out

For [1, 2, 3, 4]: after the left pass out = [1, 1, 2, 6]; the right pass multiplies by 24, 12, 4, 1 giving [24, 12, 8, 6]. The same structure solves Trapping Rain Water (water at i = min(max left, max right) minus height), Candy, and "maximum profit with at most two transactions". Walkthroughs: Product of Array Except Self and Trapping Rain Water.

Pattern 10: Monotonic Stack for Next Greater and Smaller Elements

Signal: "next greater element", "days until a warmer temperature", "stock span", "largest rectangle in histogram". Keep a stack of indices whose values are monotonic; when a new element breaks the order, it is the answer for every element it pops.

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []                       # indices, values strictly decreasing bottom to top
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

#include <stack>

vector<int> nextGreater(const vector<int>& nums) {
    vector<int> res(nums.size(), -1);
    stack<int> st;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

For [2, 1, 5, 3, 6] the result is [5, 5, 6, 6, -1]. Each index is pushed and popped once: O(n). Circular arrays (Next Greater Element II) loop over 2n indices using i % n. The full family, including the histogram problem, is in monotonic stack problems.

Pattern 11: Binary Search on Sorted and Rotated Arrays

Signal: sorted or rotated-sorted input with O(log n) expected, or a monotonic yes/no question over a numeric answer range ("minimum capacity to ship in D days").

Representative problem: Search in Rotated Sorted Array (LeetCode 33). At every step, at least one half around mid is sorted. Check whether the target lies in that sorted half; otherwise go to the other half.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                 # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                     # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

int searchRotated(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;           // overflow-safe midpoint
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

The <= in nums[lo] <= nums[mid] matters when lo == mid (two-element ranges). With duplicates allowed (LeetCode 81) the worst case degrades to O(n), because nums[lo] == nums[mid] == nums[hi] tells you nothing; shrink both ends by one. For off-by-one-proof templates and "binary search on answer", see binary search patterns.

Pattern 12: Sort Then Scan (Intervals and Greedy)

Signal: intervals, meetings, ranges, or any problem where processing elements in sorted order makes a greedy decision obviously safe.

Representative problem: Merge Intervals (LeetCode 56).

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:          # overlaps the last kept interval
            merged[-1][1] = max(merged[-1][1], end)    # max matters: [1,10] then [2,3]
        else:
            merged.append([start, end])
    return merged

After sorting by start, any interval that overlaps the merged set must overlap its last interval, so one scan suffices: O(n log n) overall. Variants: sort by end for "minimum intervals to remove" (Non-overlapping Intervals, the activity selection greedy), sweep start and end events separately for "minimum meeting rooms". See interval problems and Merge Intervals explained.

Two bonus tricks worth knowing

Boyer-Moore voting finds a majority element (more than n/2 occurrences) in O(n) time and O(1) space: keep a candidate and a counter, increment on match, decrement otherwise, and replace the candidate when the counter hits zero. Reversal rotation rotates an array right by k in place: reverse all, reverse the first k, reverse the rest (use k % n first).

def majority_element(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate            # verify with a second pass if a majority is not guaranteed

Array Patterns Complexity Table

Array Practice List: 45 Problems by Pattern

Do them in this order: easy anchors first, then the medium disguises. LeetCode numbers are given so you can find them quickly.

If you follow a sheet such as Striver's or NeetCode, these overlap heavily; the sheet comparison helps you pick one and stick with it.

Array Interview Tips and Common Pitfalls

A five-step routine for any array question

1. Clarify. Sorted? Negatives? Duplicates? Can I modify the input? Is the answer indices or values? Empty array behaviour? Each answer eliminates or selects patterns.
2. State brute force with its complexity. Usually O(n²) over all pairs or subarrays. This anchors the conversation and earns partial credit.
3. Name the repeated work. "I recompute the sum of overlapping subarrays" leads to sliding window or prefix sums. "I search for the complement linearly" leads to a hashmap.
4. Code the pattern template, then adapt. Templates prevent off-by-one errors.
5. Dry run on a small example including an edge case (single element, all negative, all duplicates), then state final time and space complexity.

This routine is covered in more depth in how to approach a DSA problem in an interview.

Bugs interviewers see constantly

• Integer overflow in Java/C++ sums and midpoints. Use long/long long for sums and lo + (hi - lo) / 2.
• Initialising Kadane with 0, which returns 0 for an all-negative array.
• Sliding window with negatives, which silently gives wrong answers.
• Sorting when indices are needed, losing the original positions.
• Negative modulo in Java/C++: -1 % 5 is -1, not 4.
• Modifying the input without asking; some interviewers count that as a wrong answer.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.