# Stop Solving Array Problems Randomly: 5 Patterns Every Developer Should Know

You open LeetCode, read an array problem, and write two nested loops. It passes. Accepted.

The next problem looks the same, but `n` is now 100,000. Same loops. This time: **Time Limit Exceeded**.

Your C++ is fine. What's missing is one question: *what work am I repeating, and can I skip it?* Most array techniques in DSA answer that question, each by removing a different kind of repeated work. Spot the kind, and hundreds of problems shrink to a few shapes.

So don't memorize hundreds of solutions. **Learn to recognize the pattern.**

*Code assumes* `#include <bits/stdc++.h>` *and* `using namespace std;`*. Every snippet was compiled and tested against brute force.*

---

## 1\. Two Pointers: Stop Checking Every Pair

**Problem:** sorted array `[1, 2, 4, 6, 8, 9]`, target `10`. Find two numbers that add up to it (LeetCode 167).

Checking every pair is O(n²). But the array is sorted, so each sum tells you which way to go. Put one pointer at each end. Sum too small? Move `left` forward. Too big? Move `right` back.

![The pointers walk toward each other until the sum matches.](https://cdn.hashnode.com/uploads/covers/6815b2643a547c35f1fb76bb/d363bb06-5844-43b0-82d7-41a47f563b88.png align="center")

```cpp
// Returns 0-based indices. LeetCode 167 wants 1-based: return {left + 1, right + 1}.
vector<int> twoSumII(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;

    while (left < right) {
        long long sum = (long long)nums[left] + nums[right];

        if (sum == target) return {left, right};
        if (sum < target) left++;
        else right--;
    }
    return {};
}
```

**Why is it safe?** If `nums[left] + nums[right]` is too small, then `nums[left]` is too small with every number at or before `right`. It can never be in the answer, so we drop it.

**Dry run, target 13:** `1+9=10` too small, move left. `2+9=11` too small, move left. `4+9=13` match. Each pointer moves one way, so it's **O(n) time, O(1) space**.

**Same idea, other shapes**

- **Container With Most Water:** move the *shorter* line. The taller one can't help, because the shorter line still caps the height.
- **Valid Palindrome:** compare from both ends. No sorting needed. Sorting matters only when the *direction* of a move depends on order.
- **Reader and writer:** one pointer reads, one marks where the next kept item goes (Remove Duplicates, Move Zeroes).
- **Fast and slow:** steps of 1 and 2, used to find cycles in linked lists.

```cpp
int removeDuplicates(vector<int>& nums) {      // sorted input
    if (nums.empty()) return 0;
    int slow = 0;                              // last unique value
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[slow]) nums[++slow] = nums[fast];
    }
    return slow + 1;
}
```

**Use it for:** sorted pairs, both-ends checks, in-place filtering. **Skip it** if you can't explain why a move is safe (Two Sum on an *unsorted* array needs a hash map).

**Remember:** every move drops candidates that can't win.

---

## 2\. Sliding Window: Reuse What Overlaps

A subarray is a continuous chunk, and the next chunk overlaps the last. Don't rebuild it.

### Fixed size

**Problem:** biggest sum of 3 neighbors in `[2, 1, 5, 1, 3, 2]`. Re-adding 3 numbers each time costs O(n·k). Instead, remove the number that leaves and add the one that enters.

![New Sum = Previous Sum - Outgoing + Incoming.](https://cdn.hashnode.com/uploads/covers/6815b2643a547c35f1fb76bb/a191c630-b919-422f-8141-77939bbaeb64.png align="center")

```cpp
long long maxSumK(const vector<int>& nums, int k) {
    int n = nums.size();
    if (k <= 0 || k > n) return 0;               // decide this per problem

    long long window = 0;
    for (int i = 0; i < k; i++) window += nums[i];
    long long best = window;

    for (int right = k; right < n; right++) {
        window += nums[right];                   // enters
        window -= nums[right - k];               // leaves
        best = max(best, window);
    }
    return best;
}
```

The windows sum to 8, 7, 9, 6, so the answer is 9. **O(n) time, O(1) space.**

### Variable size

**Problem:** `[2, 3, 1, 2, 4, 3]`, target 7. Find the shortest subarray with sum at least 7 (LeetCode 209). Grow `right` until the window is valid, then shrink `left` while it stays valid.

![Grow with right, shrink with left. The orange row is the shortest valid window.](https://cdn.hashnode.com/uploads/covers/6815b2643a547c35f1fb76bb/26377e1f-6b76-4abc-8010-de153acac933.png align="center")

```cpp
// Assumes no negative numbers and target > 0.
int minSubArrayLen(int target, const vector<int>& nums) {
    int left = 0, best = INT_MAX;
    long long sum = 0;

    for (int right = 0; right < (int)nums.size(); right++) {
        sum += nums[right];                          // grow

        while (sum >= target) {                      // shrink while valid
            best = min(best, right - left + 1);
            sum -= nums[left++];
        }
    }
    return best == INT_MAX ? 0 : best;
}
```

- **Why** `while`**, not** `if`**?** After dropping one number the window can still be valid. `[3, 1, 2, 4]` sums to 10, and dropping the 3 still leaves 7.
- **Why O(n)?** `right` moves at most n times and `left` at most n times in total. Neither goes back. The answer here is 2, from `[4, 3]`.

### The catch: negative numbers

This works only if adding a number never lowers the sum and removing one never raises it. That's true without negatives. Try `[-3, -3, 1]` with target 1: the answer is 1 (`[1]`), but this code returns 0. The negatives drag the sum down, and the window only shrinks once it's valid, so it never lets go. For negatives, use Prefix Sum + HashMap (next).

### Rules that aren't sums

Sometimes the rule is about repeats or counts, so use a count table instead of a sum.

```cpp
int lengthOfLongestSubstring(const string& s) {       // LeetCode 3
    vector<int> count(256, 0);
    int left = 0, best = 0;

    for (int right = 0; right < (int)s.size(); right++) {
        count[(unsigned char)s[right]]++;
        while (count[(unsigned char)s[right]] > 1) {  // repeat: shrink
            count[(unsigned char)s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}
```

"At most K distinct" is the same loop with a map and the rule `map.size() > k`. For "exactly K distinct" (LeetCode 992), count subarrays with *at most* K and subtract those with at most K − 1.

**Use it for:** the longest or shortest continuous range under a rule. **Skip it** for sums with negatives, or when items needn't be neighbors.

**Remember:** update the overlap, don't rebuild it.

---

## 3\. Prefix Sum: Add Once, Answer Fast

**Problem:** thousands of queries like "sum from index `l` to `r`". Looping each time costs O(n) per query.

Think of an odometer: distance between two points is one reading minus another. A prefix array stores those readings.

```cpp
prefix[i] = prefix[i - 1] + nums[i]
rangeSum(l, r) = prefix[r] - prefix[l - 1]
```

![Sum of indices 1 to 3 is prefix[3] - prefix[0] = 10 - 2 = 8.](https://cdn.hashnode.com/uploads/covers/6815b2643a547c35f1fb76bb/4b892a23-7330-4467-ab5c-f706610178f3.png align="center")

For `[2, 4, 1, 3, 5]` the prefix array is `[2, 6, 7, 10, 15]`. Indices 1 to 3 sum to `10 - 2 = 8`, which matches `4 + 1 + 3`.

**The** `l = 0` **edge case:** `prefix[-1]` doesn't exist. Nothing comes before index 0, so use 0.

```cpp
vector<long long> buildPrefix(const vector<int>& nums) {
    vector<long long> prefix(nums.size());
    for (int i = 0; i < (int)nums.size(); i++)
        prefix[i] = nums[i] + (i > 0 ? prefix[i - 1] : 0);
    return prefix;
}

long long rangeSum(const vector<long long>& prefix, int l, int r) {
    return l == 0 ? prefix[r] : prefix[r] - prefix[l - 1];
}
```

Build **O(n)**, each query **O(1)**, space **O(n)**.

### Prefix Sum + HashMap

**Problem:** count subarrays with sum `k` (LeetCode 560). Negatives allowed, so no sliding window.

`prefix[r] - prefix[l - 1] = k` means `prefix[l - 1] = prefix[r] - k`. So as you scan, ask: *how many earlier prefix sums equal my current prefix minus k?*

```cpp
int subarraySum(const vector<int>& nums, int k) {
    unordered_map<long long, int> seen;
    seen[0] = 1;                               // the empty prefix
    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]++;                        // add AFTER the lookup
    }
    return count;
}
```

**Why** `seen[0] = 1`**?** It stands for the empty prefix, so subarrays starting at index 0 count. For `[3]` and `k = 3` we look for `0`. Without the seed, the answer is 0 instead of 1. Add the current prefix *after* the lookup, or `k = 0` would count empty subarrays.

**O(n) on average**, O(n) space. **Contiguous Array** (LeetCode 525) is the same trick: turn each 0 into -1, then find the longest subarray with sum 0 by saving the *first* index of each running total.

**Use it for:** range queries, "sum equals K", "equal counts". **Skip it** for a single pass, frequent updates (use a Fenwick tree), or a *maximum* sum (Kadane).

**Remember:** store running totals, answer by subtraction.

---

## 4\. Kadane's Algorithm: Continue or Restart

**Problem:** biggest sum of a continuous subarray in `[-2, 1, -3, 4, -1, 2, 1, -5, 4]` (LeetCode 53).

Checking every start and end is O(n²). Instead, at each number ask: *extend the previous subarray, or start fresh here?* A negative running sum only hurts, so restart.

```cpp
currentSum = max(nums[i], currentSum + nums[i])
maxSum     = max(maxSum, currentSum)
```

This is dynamic programming in its smallest form: the best sum ending at `i` depends only on the one ending at `i - 1`.

![The best subarray is [4, -1, 2, 1] with sum 6.](https://cdn.hashnode.com/uploads/covers/6815b2643a547c35f1fb76bb/a4efad48-edaa-4dda-a2e0-a4b72ddd3b90.png align="center")

```cpp
long long maxSubArray(const vector<int>& nums) {   // assumes non-empty input
    long long current = nums[0], best = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {
        current = max((long long)nums[i], current + nums[i]);
        best = max(best, current);
    }
    return best;
}
```

`currentSum` goes -2, 1, -2, 4, 3, 5, 6, 1, 5, and the best seen is 6. **O(n) time, O(1) space.**

**All-negative arrays:** start from `nums[0]`, not 0. Starting at 0 allows an empty subarray, so `[-2, -3, -1]` would return 0 instead of -1.

**Variations**

- **Minimum sum:** swap `max` for `min`.
- **Start and end:** remember where the current run began, and reset it on each restart.
- **Circular array** (LeetCode 918): the best subarray is inside the array or wraps around. A wrapping one is the total minus the *smallest* middle chunk. If every number is negative, that gives 0 (empty), so return the normal maximum.

```cpp
long long maxSubarraySumCircular(const vector<int>& nums) {
    long long total = nums[0];
    long long curMax = nums[0], bestMax = nums[0];
    long long curMin = nums[0], bestMin = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {
        long long x = nums[i];
        total += x;
        curMax = max(x, curMax + x); bestMax = max(bestMax, curMax);
        curMin = min(x, curMin + x); bestMin = min(bestMin, curMin);
    }
    if (bestMax < 0) return bestMax;             // all negative
    return max(bestMax, total - bestMin);
}
```

**Not a sliding window:** a window shrinks because a *rule* broke. Kadane just decides locally, so negatives are fine. **Skip it** for exact-target sums, counting subarrays, or fixed sizes.

**Remember:** continue the run, or restart here.

---

## Array Techniques in DSA: How to Pick One

![Problem clue to technique. Treat each as a good first guess, not a rule.](https://cdn.hashnode.com/uploads/covers/6815b2643a547c35f1fb76bb/e27e5de6-d025-4553-a056-211fc9178967.png align="center")

| If the problem says | Try |
| --- | --- |
| Sorted array, pair or target | Two Pointers |
| Exactly K neighbors | Fixed Sliding Window |
| Longest or shortest valid range | Variable Sliding Window |
| Many range-sum queries | Prefix Sum |
| Count subarrays with sum K | Prefix Sum + HashMap |
| Maximum subarray sum | Kadane's |

Keywords are **clues, not guarantees**. Ask first: Is it continuous? Fixed or variable? Any negatives? Am I repeating work I could save?

---

## Speed and Overflow

| Technique | Time | Space |
| --- | --- | --- |
| Two Pointers | O(n) | O(1) |
| Fixed Sliding Window | O(n) | O(1) |
| Variable Sliding Window | O(n) | O(1), not counting any map |
| Prefix Sum | O(n) to build | O(n) |
| Prefix Sum + HashMap | O(n) average | O(n) |
| Kadane's | O(n) | O(1) |

**Let the limits guide you.** With `n = 100,000`, a nested loop does about 10¹⁰ steps. A rough rule says a judge runs about 10⁸ simple operations per second, so that's far too slow. This is only an estimate, not a promise: real speed depends on language, machine and platform. Still, `n ≤ 10⁵` usually means you need O(n) or O(n log n).

**Know your number sizes.** `int` holds about -2.1 billion to 2.1 billion. `long long` holds about -9.22 × 10¹⁸ to 9.22 × 10¹⁸.

Small numbers can make a big sum. 100,000 numbers of 100,000 each add up to 10,000,000,000. In an `int` that overflows (you may see a wrong value like 1,410,065,408, and C++ calls it undefined behavior). Use `long long` for sums, and write `(long long)a * b`, because `long long x = a * b;` multiplies as `int` first.

---

## Common Mistakes

- Nested loops without asking what repeats.
- A sliding window on a sum problem with negatives.
- Moving a pointer without knowing why it's safe.
- `if` where the window needs `while`.
- Skipping edge cases: empty array, `k > n`, all negatives.

---

## Practice

Name the pattern before you code.

- **Two Pointers:** [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/), [Move Zeroes](https://leetcode.com/problems/move-zeroes/), [Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
- **Sliding Window:** [Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/), [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/), [Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)
- **Prefix Sum:** [Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/), [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/), [Contiguous Array](https://leetcode.com/problems/contiguous-array/)
- **Kadane's:** [Maximum Subarray](https://leetcode.com/problems/maximum-subarray/), [Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/)

---

## The Takeaway

Next time an array problem shows up, don't start typing loops. Ask whether the range is continuous, fixed or variable, whether negatives appear, and what the limits allow. Those questions will point you to the right one of these array techniques in DSA far more often than memorized code.

You don't need hundreds of solutions. You need to recognize the pattern in front of you.