Chapter 2a — Array Problem Patterns

Chapter 2 gave you the physical reality of arrays: why access is O(1), why middle insertion is O(n), why JavaScript's [] is a dynamic structure managed by V8. This chapter is different in purpose. Here you stop understanding and start doing. The goal is to build pattern recognition — the ability to look at a problem you have never seen before and immediately know which technique applies. That ability does not come from reading. It comes from solving enough problems deeply enough that the patterns become instinct. Every problem in this chapter is solved with full reasoning and a complete dry run. You do not move on until you can reproduce the reasoning cold, without looking.

One important boundary: Two Pointers and Sliding Window each get their own chapters (5 and 6). They are used here — because they are array techniques — but treated as previews. You will see them introduced on one problem each. The deep treatment comes later.

The Pattern Map

Before any problem, this is how you read the signal:

Signal: "maximum or minimum of something over all subarrays" → Kadane's pattern. You maintain a running local value and a global best simultaneously.

Signal: "sum of a range" or "how many subarrays sum to k" or "equilibrium index" → Prefix sum. Possibly combined with a HashMap if counting is involved.

Signal: "in-place", "O(1) extra space", "remove elements" → Two-index read/write. One index reads every element, one index writes only the keepers.

Signal: "intervals", "overlapping ranges", "merge", "non-overlapping" → Sort by start, then sweep. Intervals collapse to an array problem after sorting.

Signal: "sorted array, find pair/triplet", "container", "two ends" → Two Pointers from ends. Full treatment in Chapter 5 — one preview here.

Signal: "contiguous subarray with constraint on length or sum" → Sliding Window. Full treatment in Chapter 6 — one preview here.

Signal: "product of everything except current index" → Prefix product + suffix product. A specific but important pattern.

Hold these signals. Every problem below maps to one of them.

Pattern 1: Kadane's Algorithm — The Running Best

The core idea is this: at every position in the array, you make a single local decision — "does including this element make my current subarray better, or am I better off starting fresh from here?" Alongside that local decision, you track the best answer you have seen globally.

This pattern applies whenever the problem is: find the subarray (contiguous) that maximizes or minimizes some value. The insight — which we will derive — is that you never need to look backward more than one step.

Problem 1: Maximum Subarray (LeetCode 53)

Problem: Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Reason: [4, -1, 2, 1] has the largest sum = 6

Q1: What do I have? An array of n integers. Integers can be negative. n can be up to 10⁵.

Q2: What do I want? The maximum sum of any contiguous subarray. Not the subarray itself — just the sum.

Q3: What is the brute force? Check every possible subarray. Two nested loops to pick start and end indices, sum each subarray.

function maxSubarrayBrute(nums) {
  let max = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      max = Math.max(max, sum);
    }
  }
  return max;
}

Time: O(n²). Space: O(1). For n = 10⁵ that is 10¹⁰ operations. Too slow.

Q4: Where is the waste?

Look at what the brute force does: for start index i = 3 (value 4), it computes sums for subarrays [4], [4,-1], [4,-1,2], and so on. Then for i = 4 (value -1), it recomputes [-1], [-1,2], etc. There is massive overlap.

But here is the deeper insight: ask yourself this question at every index i — should the best subarray ending at position i include what came before, or start fresh at i?

If the best subarray ending at i-1 has a positive sum, you want to include it — it can only help. If it has a negative sum, you are better off ditching it and starting at i — dragging in a negative sum makes your total worse.

This is a single comparison per element. No looking backward beyond the previous result.

The algorithm:

function maxSubarray(nums) {
  let currentSum = nums[0];  // best sum ending AT current position
  let globalMax = nums[0];   // best sum seen so far across all positions

  for (let i = 1; i < nums.length; i++) {
    // Decision: extend the previous subarray, or start fresh here?
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    globalMax = Math.max(globalMax, currentSum);
  }

  return globalMax;
}

Full dry run on [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

We initialize with the first element because an empty subarray is not valid — there must be at least one element.

Start: currentSum = -2,  globalMax = -2

i=1, nums[1]=1:
  currentSum = max(1, -2+1) = max(1, -1) = 1
  (starting fresh at 1 is better than extending [-2,1] = -1)
  globalMax = max(-2, 1) = 1

i=2, nums[2]=-3:
  currentSum = max(-3, 1+(-3)) = max(-3, -2) = -2
  (starting fresh at -3 is worse than [1,-3]=-2, so we keep [1,-3])
  Wait — both options are negative. We pick the less negative: -2.
  globalMax = max(1, -2) = 1  (global max doesn't change)

i=3, nums[3]=4:
  currentSum = max(4, -2+4) = max(4, 2) = 4
  (starting fresh at 4 is better than extending [1,-3,4]=2)
  globalMax = max(1, 4) = 4

i=4, nums[4]=-1:
  currentSum = max(-1, 4+(-1)) = max(-1, 3) = 3
  (extending [4,-1]=3 is better than starting fresh at -1)
  globalMax = max(4, 3) = 4

i=5, nums[5]=2:
  currentSum = max(2, 3+2) = max(2, 5) = 5
  (extending [4,-1,2]=5 is better)
  globalMax = max(4, 5) = 5

i=6, nums[6]=1:
  currentSum = max(1, 5+1) = max(1, 6) = 6
  (extending [4,-1,2,1]=6 is better)
  globalMax = max(5, 6) = 6

i=7, nums[7]=-5:
  currentSum = max(-5, 6+(-5)) = max(-5, 1) = 1
  (extending [4,-1,2,1,-5]=1 is better than starting at -5)
  globalMax = max(6, 1) = 6

i=8, nums[8]=4:
  currentSum = max(4, 1+4) = max(4, 5) = 5
  (extending gives 5, starting fresh gives 4; extend wins)
  globalMax = max(6, 5) = 6

Final answer: 6 ✓

Why does this work?

At each index i, currentSum holds the maximum sum of any subarray that ends exactly at i. There are only two candidates: a subarray containing only nums[i] (fresh start), or any subarray ending at i-1 extended by nums[i]. The maximum of these two is max(nums[i], currentSum + nums[i]). Since we check every position and track the global best, we cannot miss the answer.

Complexity: O(n) time, O(1) space. One pass, two variables.

Problem 2: Best Time to Buy and Sell Stock (LeetCode 121)

Problem: You are given an array prices where prices[i] is the price of a stock on day i. You can buy once and sell once. Find the maximum profit. If no profit is possible, return 0.

Input:  [7, 1, 5, 3, 6, 4]
Output: 5
Reason: Buy on day 2 (price 1), sell on day 5 (price 6). Profit = 6 - 1 = 5.

Q1: What do I have? An array of n prices, all non-negative. Constraint: buy must happen before sell.

Q2: What do I want? Maximum prices[j] - prices[i] where j > i. Return 0 if no positive profit exists.

Q3: Brute force? Every pair (i, j) where j > i. Check prices[j] - prices[i].

function maxProfitBrute(prices) {
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      max = Math.max(max, prices[j] - prices[i]);
    }
  }
  return max;
}

O(n²). Waste.

Q4: Where is the waste?

To maximize prices[j] - prices[i], you want prices[i] to be as small as possible. For any given sell day j, the best buy day is the day with the lowest price before j.

So as you scan from left to right, track the minimum price seen so far. At each day, compute profit if you sold today: prices[j] - minSoFar. That is your best possible profit for selling on day j.

This is the same structure as Kadane's: a running local value (minSoFar) and a global best (maxProfit).

function maxProfit(prices) {
  let minSoFar = prices[0];
  let maxProfit = 0;

  for (let i = 1; i < prices.length; i++) {
    // Best profit if we sell today
    maxProfit = Math.max(maxProfit, prices[i] - minSoFar);
    // Update the cheapest buy price we've seen
    minSoFar = Math.min(minSoFar, prices[i]);
  }

  return maxProfit;
}

Full dry run on [7, 1, 5, 3, 6, 4]:

Start: minSoFar = 7, maxProfit = 0

i=1, price=1:
  profit if sell today = 1 - 7 = -6 → maxProfit = max(0, -6) = 0
  minSoFar = min(7, 1) = 1

i=2, price=5:
  profit if sell today = 5 - 1 = 4 → maxProfit = max(0, 4) = 4
  minSoFar = min(1, 5) = 1

i=3, price=3:
  profit if sell today = 3 - 1 = 2 → maxProfit = max(4, 2) = 4
  minSoFar = min(1, 3) = 1

i=4, price=6:
  profit if sell today = 6 - 1 = 5 → maxProfit = max(4, 5) = 5
  minSoFar = min(1, 6) = 1

i=5, price=4:
  profit if sell today = 4 - 1 = 3 → maxProfit = max(5, 3) = 5
  minSoFar = min(1, 4) = 1

Final answer: 5 ✓

Why does this work? At every index, the maximum profit achievable by selling on day i is prices[i] - (minimum price in prices[0..i-1]). By maintaining minSoFar, we compute this in O(1) instead of scanning backwards. The rest is tracking the global max.

Note the deeper connection to Kadane's: If you transform the prices array into a daily profit/loss array (differences: prices[i] - prices[i-1]), finding the best buy/sell becomes exactly finding the maximum subarray sum of that difference array. The problems are isomorphic. Recognizing this connection across different-looking problems is what makes you dangerous.

Complexity: O(n) time, O(1) space.

Pattern 2: Prefix Product — The "Left Pass Right Pass" Technique

Prefix sum computes cumulative sums going left to right. The same idea applies to any operation that is associative: multiplication, XOR, GCD. The key insight is that you can make two passes — one from the left, one from the right — and combine the results.

Problem 3: Product of Array Except Self (LeetCode 238)

Problem: Given an integer array nums, return an array answer such that answer[i] is the product of all elements in nums except nums[i]. You may not use the division operator. Solve in O(n) time with O(1) extra space (the output array does not count as extra space).

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Reason: answer[0] = 2×3×4 = 24
        answer[1] = 1×3×4 = 12
        answer[2] = 1×2×4 = 8
        answer[3] = 1×2×3 = 6

Q1: What do I have? Array of n integers. No division allowed. Must be O(n) time, O(1) extra space.

Q2: What do I want? Array where each position holds the product of everything except the element at that position.

Q3: Brute force? For each index i, loop through all elements except i and multiply. O(n²). Obvious waste.

Q4: Where is the waste?

Look at what each position needs:

answer[0] needs:          × nums[1] × nums[2] × nums[3]
answer[1] needs: nums[0] ×           nums[2] × nums[3]
answer[2] needs: nums[0] × nums[1] ×           nums[3]
answer[3] needs: nums[0] × nums[1] × nums[2]

Split each row into what is to the left of index i and what is to the right of index i:

answer[i] = (product of everything left of i) × (product of everything right of i)

Both halves can be precomputed in a single pass each.

Pass 1 — Left products: Scan left to right. left[i] = product of nums[0] through nums[i-1]. Pass 2 — Right products: Scan right to left. right[i] = product of nums[i+1] through nums[n-1]. Combine: answer[i] = left[i] × right[i].

But two extra arrays use O(n) space. The O(1) space trick: use the output array itself for the left pass, then fold the right product in on the way back with just a single variable.

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n);

  // Pass 1: fill answer[i] with product of everything LEFT of i
  answer[0] = 1;  // nothing to the left of index 0
  for (let i = 1; i < n; i++) {
    answer[i] = answer[i - 1] * nums[i - 1];
  }
  // After pass 1: answer = [1, 1, 2, 6] for input [1,2,3,4]

  // Pass 2: multiply each position by product of everything RIGHT of i
  let rightProduct = 1;  // nothing to the right of last index
  for (let i = n - 1; i >= 0; i--) {
    answer[i] = answer[i] * rightProduct;
    rightProduct *= nums[i];  // update right product before moving left
  }

  return answer;
}

Full dry run on [1, 2, 3, 4]:

Pass 1 (left products into answer):

answer[0] = 1                           (no elements to the left)
answer[1] = answer[0] × nums[0] = 1×1 = 1
answer[2] = answer[1] × nums[1] = 1×2 = 2
answer[3] = answer[2] × nums[2] = 2×3 = 6

answer after pass 1: [1, 1, 2, 6]

Pass 2 (multiply in right products from right to left):

rightProduct = 1

i=3: answer[3] = 6 × 1 = 6.   Then rightProduct = 1 × nums[3] = 1×4 = 4
i=2: answer[2] = 2 × 4 = 8.   Then rightProduct = 4 × nums[2] = 4×3 = 12
i=1: answer[1] = 1 × 12 = 12. Then rightProduct = 12 × nums[1] = 12×2 = 24
i=0: answer[0] = 1 × 24 = 24. Then rightProduct = 24 × nums[0] = 24×1 = 24

answer after pass 2: [24, 12, 8, 6] ✓

Why is answer[0] = 1 in pass 1? There are zero elements to the left of index 0. The product of zero elements is 1 (the multiplicative identity — the same reason 0! = 1 in mathematics). Any real element multiplied by 1 is unchanged, so this is the correct neutral starting value.

Why does rightProduct update AFTER we use it? At index i, we need the product of everything to the RIGHT of i — meaning nums[i+1] through nums[n-1]. The variable rightProduct holds that value when we arrive at i. After we use it, we incorporate nums[i] into rightProduct so it is ready for index i-1.

Complexity: O(n) time, O(1) extra space (output array excluded by problem statement).

Pattern 3: Prefix Sum + HashMap — Counting Subarrays

When you need to count subarrays with a specific sum, prefix sum alone is not enough — you need to look up previous prefix sums efficiently. A HashMap transforms the lookup from O(n) to O(1).

Problem 4: Subarray Sum Equals K (LeetCode 560)

Problem: Given an array of integers nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

Input:  nums = [1, 1, 1], k = 2
Output: 2
Reason: [1,1] at indices 0-1 and [1,1] at indices 1-2 both sum to 2.

Q1: What do I have? Array of integers (can be negative!). An integer k. n up to 2×10⁴.

Q2: What do I want? A count of subarrays summing exactly to k.

Q3: Brute force? Two loops: for every (i, j) pair, compute the sum and check if it equals k. O(n²). With prefix sum precomputation: O(n) build, then O(n²) queries. Still O(n²) total.

Q4: Where is the waste?

We established in Chapter 2 that sum(i, j) = prefix[j+1] - prefix[i]. We want sum(i, j) = k, so:

prefix[j+1] - prefix[i] = k
prefix[i] = prefix[j+1] - k

As we scan from left to right, at position j+1 we have computed prefix[j+1]. We need to know: how many previous prefix values equal prefix[j+1] - k?

If we store prefix sums in a HashMap as we go, this lookup is O(1). We do not need to scan backward — we just look up the complement in the map.

The critical detail — why {0: 1} as the starting state:

Before processing any element, the prefix sum is 0 (empty prefix). If prefix[j+1] - k = 0, it means the entire subarray from index 0 to j sums to k. Without the sentinel {0: 1}, we would miss these subarrays. The 1 means "the prefix sum of 0 has occurred once" — that once being before the array starts.

function subarraySum(nums, k) {
  const freq = new Map();
  freq.set(0, 1);  // sentinel: prefix sum 0 seen once before the array

  let prefixSum = 0;
  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    prefixSum += nums[i];

    // How many previous prefixes give us a valid subarray ending here?
    const complement = prefixSum - k;
    if (freq.has(complement)) {
      count += freq.get(complement);
    }

    // Record this prefix sum
    freq.set(prefixSum, (freq.get(prefixSum) || 0) + 1);
  }

  return count;
}

Full dry run on [1, 1, 1], k = 2:

freq = {0: 1},  prefixSum = 0,  count = 0

i=0, nums[0]=1:
  prefixSum = 0+1 = 1
  complement = 1-2 = -1 → not in freq → count unchanged (0)
  freq = {0:1, 1:1}

i=1, nums[1]=1:
  prefixSum = 1+1 = 2
  complement = 2-2 = 0 → in freq with count 1 → count = 0+1 = 1
  (This found the subarray [1,1] at indices 0-1)
  freq = {0:1, 1:1, 2:1}

i=2, nums[2]=1:
  prefixSum = 2+1 = 3
  complement = 3-2 = 1 → in freq with count 1 → count = 1+1 = 2
  (This found the subarray [1,1] at indices 1-2)
  freq = {0:1, 1:1, 2:1, 3:1}

Final answer: 2 ✓

Why does count += freq.get(complement) potentially add more than 1? If the same prefix sum has appeared three times, there are three different starting positions that would produce a valid subarray ending here. All three are distinct subarrays and all three must be counted. This is why we store frequency counts, not just "seen/not seen."

Handles negatives: Unlike a sliding window approach (which breaks with negatives because shrinking the window does not guarantee the sum decreases), this approach works for any integers. Prefix sums are cumulative — a negative number simply decreases the running sum. The HashMap lookup logic is unaffected.

Complexity: O(n) time, O(n) space for the HashMap.

Problem 5: Find Pivot Index (LeetCode 724)

Problem: Given an array nums, find the leftmost index where the sum of all elements to the left equals the sum of all elements to the right. Return -1 if no such index exists.

Input:  [1, 7, 3, 6, 5, 6]
Output: 3
Reason: Left of index 3: 1+7+3 = 11. Right of index 3: 5+6 = 11. Equal.

The elegant insight: At any index i, if we know totalSum and leftSum (sum of elements 0 to i-1), then rightSum = totalSum - leftSum - nums[i]. We just need to check if leftSum == rightSum.

function pivotIndex(nums) {
  const totalSum = nums.reduce((a, b) => a + b, 0);
  let leftSum = 0;

  for (let i = 0; i < nums.length; i++) {
    const rightSum = totalSum - leftSum - nums[i];
    if (leftSum === rightSum) return i;
    leftSum += nums[i];
  }

  return -1;
}

Dry run on [1, 7, 3, 6, 5, 6]:

totalSum = 1+7+3+6+5+6 = 28,  leftSum = 0

i=0: rightSum = 28-0-1 = 27.  leftSum(0) ≠ rightSum(27). leftSum → 1
i=1: rightSum = 28-1-7 = 20.  leftSum(1) ≠ rightSum(20). leftSum → 8
i=2: rightSum = 28-8-3 = 17.  leftSum(8) ≠ rightSum(17). leftSum → 11
i=3: rightSum = 28-11-6 = 11. leftSum(11) = rightSum(11). Return 3 ✓

Complexity: O(n) time for initial sum, O(n) for the scan = O(n) total. O(1) space.

Pattern 4: In-Place Read/Write — The Two-Index Crawl

When the problem says "in-place" or "O(1) extra space" and asks you to filter or rearrange elements, the technique is always the same: one index reads every element, a second index marks where the next "keeper" should be written. The read index advances every step. The write index advances only when it writes.

Problem 6: Remove Duplicates from Sorted Array (LeetCode 26)

Problem: Given an integer array nums sorted in non-decreasing order, remove duplicates in-place such that each unique element appears only once. Return the number of unique elements.

Input:  [1, 1, 2, 3, 3, 3, 4]
Output: 4  (and the first 4 elements of nums are [1, 2, 3, 4])

Why sorted matters: In a sorted array, all duplicates are adjacent. You never need to search for a duplicate across the whole array — you only need to compare with the previous element.

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;

  let writeIndex = 1;  // first element is always unique, start writing from index 1

  for (let readIndex = 1; readIndex < nums.length; readIndex++) {
    // Only write if current element differs from the previous unique element
    if (nums[readIndex] !== nums[writeIndex - 1]) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }

  return writeIndex;  // number of unique elements
}

Full dry run on [1, 1, 2, 3, 3, 3, 4]:

writeIndex = 1

readIndex=1: nums[1]=1, nums[writeIndex-1]=nums[0]=1. Same → skip.
readIndex=2: nums[2]=2, nums[writeIndex-1]=nums[0]=1. Different → nums[1]=2, writeIndex=2.
readIndex=3: nums[3]=3, nums[writeIndex-1]=nums[1]=2. Different → nums[2]=3, writeIndex=3.
readIndex=4: nums[4]=3, nums[writeIndex-1]=nums[2]=3. Same → skip.
readIndex=5: nums[5]=3, nums[writeIndex-1]=nums[2]=3. Same → skip.
readIndex=6: nums[6]=4, nums[writeIndex-1]=nums[2]=3. Different → nums[3]=4, writeIndex=4.

Array: [1, 2, 3, 4, 3, 3, 4]
       ↑ first 4 elements are correct ↑
Return: 4 ✓

Why nums[readIndex] !== nums[writeIndex - 1] and not nums[readIndex] !== nums[readIndex - 1]?

Because writeIndex - 1 points to the last element we confirmed as unique. readIndex - 1 points to the previously read element — which might be a duplicate that we skipped. Comparing against the last written element ensures we are comparing against the true previous unique value.

Complexity: O(n) time, O(1) space.

Pattern 5: Interval Problems — Sort First, Then Sweep

Interval problems look geometric but reduce to array problems after sorting. Once intervals are sorted by their start times, you can process them in a single sweep from left to right, maintaining only the current "active" interval.

Problem 7: Merge Intervals (LeetCode 56)

Problem: Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals.

Input:  [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Reason: [1,3] and [2,6] overlap (3 ≥ 2), so they merge to [1,6].

Q1: What do I have? An array of n intervals. Intervals may be in any order. Intervals may overlap.

Q2: What do I want? An array of merged intervals with no overlaps.

Q3: Brute force? For each interval, check all other intervals for overlap. Merge when overlap found. Repeat until stable. O(n²) or worse.

Q4: Where is the waste?

Overlapping intervals are not random — if we sort by start time, any interval that can merge with the current one must have a start time ≤ the current interval's end. Everything after the end cannot overlap. So the merge decision becomes local.

After sorting, you only ever compare each new interval against the last merged interval. One pass.

function merge(intervals) {
  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];  // start with the first interval

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];  // last merged interval

    if (current[0] <= last[1]) {
      // Overlap: extend the end of the last merged interval if needed
      last[1] = Math.max(last[1], current[i]);
      // BUG NOTE: should be current[1] not current[i] — see dry run below
    } else {
      // No overlap: start a new interval
      merged.push(current);
    }
  }

  return merged;
}

Let me write this correctly:

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const [currStart, currEnd] = intervals[i];
    const lastMerged = merged[merged.length - 1];

    if (currStart <= lastMerged[1]) {
      // Overlapping: expand the end if current interval extends further
      lastMerged[1] = Math.max(lastMerged[1], currEnd);
    } else {
      // No overlap: add as a new separate interval
      merged.push([currStart, currEnd]);
    }
  }

  return merged;
}

Full dry run on [[1,3], [2,6], [8,10], [15,18]]:

After sort by start: [[1,3], [2,6], [8,10], [15,18]] (already sorted)

merged = [[1,3]]

i=1: current=[2,6], lastMerged=[1,3]
  currStart(2) <= lastMerged[1](3)? YES → overlap
  lastMerged[1] = max(3, 6) = 6
  merged = [[1,6]]

i=2: current=[8,10], lastMerged=[1,6]
  currStart(8) <= lastMerged[1](6)? NO → no overlap
  push [8,10]
  merged = [[1,6], [8,10]]

i=3: current=[15,18], lastMerged=[8,10]
  currStart(15) <= lastMerged[1](10)? NO → no overlap
  push [15,18]
  merged = [[1,6], [8,10], [15,18]] ✓

What does Math.max(lastMerged[1], currEnd) handle? The case where one interval is completely contained inside another. Example: [1,10] and [2,5]. After sorting, [1,10] comes first. When we process [2,5], currStart(2) <= 10, so we try to merge. Math.max(10, 5) = 10 — correctly keeps [1,10]. Without the max, we would incorrectly shrink the interval to [1,5].

Complexity: O(n log n) for sort, O(n) for the sweep = O(n log n) total. O(n) space for output.

Pattern 6: Two Pointers from Ends — Preview

This pattern gets a full chapter (Chapter 5), but you will encounter it in array problems constantly. The idea: place one pointer at the leftmost position and one at the rightmost. Move them toward each other based on a condition. Each move provably eliminates at least one candidate.

This works only when the array has structure (usually sorted, or when the geometry of the problem guarantees what moving a pointer implies).

Problem 8: Trapping Rain Water (LeetCode 42)

This is a hard problem. It appears in interviews at Zepto, Razorpay, Amazon, and Google. It is covered here rather than Chapter 5a because it is the canonical two-pointer array problem and the reasoning is instructive even before the pattern is formalized.

Problem: Given an array height representing an elevation map, compute how much water can be trapped after raining.

Input:  [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Water at any position i is bounded by the shorter of:

• The tallest wall to its left (including itself)
• The tallest wall to its right (including itself)

Water at i = min(maxLeft[i], maxRight[i]) - height[i]

If that value is negative (the position itself is taller than one of the walls), it holds 0 water.

Brute force: For each position, scan left and right for the max. O(n²).

Better with prefix arrays: Precompute maxLeft and maxRight arrays. O(n) time, O(n) space.

Two pointer — O(n) time, O(1) space:

The key insight: if maxLeft < maxRight at any point, the water at the left pointer is determined entirely by maxLeft — because even though we do not know the exact right wall, we know it is at least as tall as maxRight, which is already taller than maxLeft. The left side is the binding constraint. Process the left pointer.

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] <= height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];    // new tallest left wall
      } else {
        water += leftMax - height[left];  // water trapped here
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];  // new tallest right wall
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

Dry run on [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

left=0, right=11, leftMax=0, rightMax=0, water=0

Step 1: h[left]=0, h[right]=1. h[left]<=h[right].
  h[0]=0 >= leftMax(0) → leftMax=0. left++.
  (Position 0: height equals leftMax, no water trapped, but leftMax stays 0)

Step 2: left=1, h[1]=1, h[right=11]=1. h[left]<=h[right].
  h[1]=1 >= leftMax(0) → leftMax=1. left++.

Step 3: left=2, h[2]=0, h[right=11]=1. h[left]<=h[right].
  h[2]=0 < leftMax(1) → water += 1-0 = 1. water=1. left++.
  (Position 2: trapped between wall of height 1 on left and wall ≥ 1 on right)

Step 4: left=3, h[3]=2, h[right=11]=1. h[left]>h[right].
  h[11]=1 >= rightMax(0) → rightMax=1. right--.

Step 5: left=3, h[3]=2, h[right=10]=2. h[left]<=h[right].
  h[3]=2 >= leftMax(1) → leftMax=2. left++.

Step 6: left=4, h[4]=1, h[right=10]=2. h[left]<=h[right].
  h[4]=1 < leftMax(2) → water += 2-1 = 1. water=2. left++.

Step 7: left=5, h[5]=0, h[right=10]=2. h[left]<=h[right].
  h[5]=0 < leftMax(2) → water += 2-0 = 2. water=4. left++.

Step 8: left=6, h[6]=1, h[right=10]=2. h[left]<=h[right].
  h[6]=1 < leftMax(2) → water += 2-1 = 1. water=5. left++.

Step 9: left=7, h[7]=3, h[right=10]=2. h[left]>h[right].
  h[10]=2 >= rightMax(1) → rightMax=2. right--.

Step 10: left=7, h[7]=3, h[right=9]=1. h[left]>h[right].
  h[9]=1 < rightMax(2) → water += 2-1 = 1. water=6. right--.

Step 11: left=7, right=8. h[7]=3, h[8]=2. h[left]>h[right].
  h[8]=2 >= rightMax(2) → rightMax=2. right--.

Step 12: left=7, right=7. left is not < right. Loop ends.

Final answer: 6 ✓

Why does processing the side with the smaller height guarantee correctness?

When height[left] <= height[right]: the water at position left is min(leftMax, rightMax_actual) - height[left]. We know height[right] >= height[left], and we know rightMax_actual >= height[right]. Therefore rightMax_actual >= height[right] >= height[left]. This means rightMax_actual >= leftMax is NOT guaranteed — but here is the critical point: if leftMax <= rightMax_actual, then min(leftMax, rightMax_actual) = leftMax, and we can compute water exactly. If leftMax > rightMax_actual... that contradicts nothing about what we assumed (rightMax_actual >= height[left]), but in that case we would have moved the right pointer in a different step. The algorithm self-corrects.

The proof is by induction on pointer positions, but the intuition is: we always process the side we can compute water for with certainty, and we only move past positions where we have definitively computed the answer.

Complexity: O(n) time, O(1) space. Each element is processed exactly once.

Pattern Recognition: Putting It All Together

Here is the decision process to run when you see an array problem:

Read the problem. Identify the signal:

1. "maximum sum / minimum sum of contiguous subarray"
   → Kadane's. Maintain local and global simultaneously.

2. "buy/sell stock", "best time to...", any "running min/max while scanning"
   → Kadane's variant. Track a running best alongside a running value.

3. "product/sum of everything except self"
   → Two-pass prefix (left pass then right pass with a single variable).

4. "count subarrays with sum = k" / "sum of range queries"
   → Prefix sum. If counting, add a HashMap.

5. "sorted array, remove duplicates, remove element, filter in-place"
   → Two-index read/write. readIndex visits all, writeIndex advances on keepers.

6. "merge/count overlapping intervals"
   → Sort by start, sweep with one variable tracking current end.

7. "sorted array, find pair/triplet summing to target"
   → Two pointers from ends (Chapter 5).

8. "longest/shortest contiguous subarray with constraint"
   → Sliding window (Chapter 6).

Vocabulary Map

Practice Problems

Solve all five on paper. No code until you have the full reasoning.

Problem 1 — Trace and Predict

Run Kadane's algorithm on this input by hand:

nums = [5, -4, 8, -10, 2, 3, -2, 6, -1]

For each index, write the exact values of currentSum and globalMax after processing that element. Show the decision at each step: did you start fresh or extend? State the final answer and identify which subarray it corresponds to.

Then answer: this array has two "competitive" subarrays. Which one does Kadane's pick, and why does it always pick the correct one even though it never explicitly tracks subarray boundaries?

Problem 2 — Find the Waste

A developer implements "maximum profit from multiple buy/sell transactions" (you can buy and sell as many times as you want, but you can only hold one share at a time):

function maxProfitMultiple(prices) {
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] > prices[i]) {
        maxProfit += prices[j] - prices[i];
        i = j;  // "move i forward to j after selling"
        break;
      }
    }
  }
  return maxProfit;
}

Part A: Run this on [7, 1, 5, 3, 6, 4]. What does it return? Is the answer correct?

Part B: Find an input where this function returns the wrong answer. Explain precisely why it fails.

Part C: The optimal insight for multiple transactions is: if prices[i+1] > prices[i], you should capture that profit. The sum of all positive day-to-day differences equals the maximum profit. Implement this in O(n) time and O(1) space, and prove it gives the same result as the optimal buy-sell strategy.

Problem 3 — Failure Analysis

A developer writes a function to count subarrays with sum equal to k, using a sliding window instead of prefix sum + HashMap:

function subarraySumSliding(nums, k) {
  let left = 0;
  let sum = 0;
  let count = 0;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while (sum > k && left <= right) {
      sum -= nums[left];
      left++;
    }

    if (sum === k) count++;
  }

  return count;
}

Part A: Run this on nums = [1, 1, 1], k = 2. Does it produce the correct answer?

Part B: Run this on nums = [1, -1, 1], k = 1. Walk through each step. What does it return? What is the correct answer? Why does the sliding window approach fail here?

Part C: The root cause is a fundamental limitation of sliding window. State it precisely. What property must the array satisfy for a sliding window to correctly count subarrays with a fixed sum? Why does the prefix sum + HashMap approach not share this limitation?

Problem 4 — Design Under Constraints

You are building the analytics backend for AttemptIQ. For every user, you need to answer these queries in real-time:

• "How many questions did User X attempt in the date range [day_a, day_b]?"
• "What was User X's accuracy (% correct) in date range [day_a, day_b]?"

The dates are stored as integers (day number since the user joined). Users can have up to 365 days of data.

Constraints:

• Each query must run in O(1) time
• You can precompute whatever you want when a new day's data arrives (O(n) preprocessing per update is acceptable)
• Memory per user must be O(n) where n = number of days the user has been active

Your task: Design the data structure(s) for a single user. State:

1. Exactly what arrays/objects you maintain.
2. The preprocessing step when a new day's attempts are recorded.
3. The algorithm for answering each query type in O(1).
4. Why accuracy requires two separate prefix arrays rather than one.
5. What breaks if the user has days with zero attempts — and how you handle it.

Problem 5 — Reach Beyond

This problem connects Chapter 2a to Chapter 1's complexity framework and asks you to reason about a problem class.

You have seen that:

• Kadane's algorithm converts O(n²) subarray enumeration into O(n) by maintaining running state
• Prefix sum + HashMap converts O(n²) subarray counting into O(n) by turning lookups into O(1) hash operations
• Two pointers converts O(n²) pair search into O(n) by exploiting sorted structure

All three techniques reduce an O(n²) problem to O(n). But not all O(n²) array problems can be reduced to O(n).

Part A: Argue why "find the longest subarray with at most K distinct elements" can be solved in O(n) but "find the longest subarray with exactly K distinct elements" seems harder at first glance. (Hint: think about what a sliding window can naturally track.)

Part B: Here is a trick: exactly(K) = atMost(K) - atMost(K-1). This converts an "exact" constraint into two "at most" constraints. If atMost(K) is solvable in O(n), then exactly(K) is also O(n) via two passes. This is the same decomposition used in "Count Subarrays with Bounded Maximum" from the research. Can you apply this trick to: "count subarrays where the number of odd numbers is exactly K"? Write the atMost(k) function for this specific problem and verify it on nums = [1, 1, 2, 1, 1], k = 3.

Part C: Reflect on the pattern: "if you can solve atMost(k) in O(n), you can solve exactly(k) in O(n) by subtraction." Under what conditions does this decomposition work? What property of atMost must hold for the subtraction atMost(K) - atMost(K-1) to give the correct count of subarrays with exactly K of something? (Think about what it means for a subarray to be "counted" in atMost(K) but not in atMost(K-1).)

What's Coming Next

Every problem in this chapter required looking up whether a value had been seen before — and right now, doing that lookup requires either scanning the array (O(n)) or pre-sorting it (O(n log n)). In Problem 4 of the Subarray Sum section, we sneaked in a Map to make that lookup O(1). That Map is a HashMap — the data structure that eliminates search cost entirely by turning any key into a direct index via a mathematical function. Chapter 3 builds a HashMap from scratch: the hash function, collision handling, why the average case is O(1) but the worst case is O(n), and how JavaScript's Map and {} differ under the hood. Once you understand it deeply, you will see why 40% of medium array problems that feel impossible become trivial the moment you ask "can a HashMap hold the state I need?"

Sources for problem selection: real interview reports from Zepto, Razorpay, Walmart, and Amazon India (2024–2026); LeetCode company-tagged problem frequency data; Neetcode blind 75 / 150 array section; interview pattern analysis from Sliding Window, Two Pointers, and Prefix Sums — Viewport.