Week 2: Arrays, Two Pointers & Sliding Window

1. Prefix Sums & In-Place Array Manipulation

A prefix sum array stores the running total of an array up to each index. Once built, it turns any range-sum query into a single subtraction — O(1) per query instead of re-summing the range every time. This is the single highest-leverage trick in array problems: whenever you see "answer many queries about a range," prefix sums are the first thing to consider.

#include <vector>
using namespace std;

// prefix[i] holds the sum of nums[0..i-1], so prefix[0] = 0
vector<int> buildPrefixSum(const vector<int>& nums) {
    vector<int> prefix(nums.size() + 1, 0);
    for (int i = 0; i < (int)nums.size(); i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// Sum of nums[l..r] inclusive, O(1) after the O(n) build above
int rangeSum(const vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Prefix sums are one flavor of a broader habit: manipulating an array in place with index bookkeeping instead of allocating new containers. A classic example is separating non-zero elements from zeroes using a single "write pointer" that trails a "read pointer":

#include <vector>
#include <algorithm>
using namespace std;

// Moves all zeroes to the end while preserving the relative order of non-zero elements.
// O(n) time, O(1) extra space.
void moveZeroesToEnd(vector<int>& nums) {
    int writePos = 0;
    for (int readPos = 0; readPos < (int)nums.size(); readPos++) {
        if (nums[readPos] != 0) {
            swap(nums[writePos], nums[readPos]);
            writePos++;
        }
    }
}

2. Two-Pointer Technique

The two-pointer technique replaces a nested loop with two indices that each move at most n times total, turning an O(n²) brute force into O(n). It comes in two distinct shapes, and recognizing which one a problem needs is half the battle.

Opposite-ends pointers

When the array is sorted, a pointer starting at each end can decide which side to move based on a comparison — no need to check every pair:

#include <vector>
using namespace std;

// nums is sorted ascending. Returns indices (i, j) with nums[i] + nums[j] == target,
// or (-1, -1) if no such pair exists. O(n) time, O(1) space.
pair<int, int> twoSumSorted(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return {left, right};
        else if (sum < target) left++;   // sum too small -- grow it
        else right--;                     // sum too big -- shrink it
    }
    return {-1, -1};
}

Fast/slow pointers (same direction)

Both pointers start together and move in the same direction, but at different rates or under different conditions. A common use is compacting an array in place — here, deduplicating a sorted array by letting a "slow" write pointer only advance when a genuinely new value is found:

#include <vector>
using namespace std;

// nums is sorted. Overwrites nums in place so the first k slots hold the unique
// values in order, and returns k. O(n) time, O(1) extra space.
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

3. Fixed-Size Sliding Window

When a problem asks about every contiguous subarray of a fixed length k, recomputing the sum (or max, or count) of each window from scratch is O(n·k). A sliding window instead updates the running value incrementally as the window slides one position at a time — drop the element leaving the window, add the element entering it:

#include <vector>
#include <algorithm>
using namespace std;

// Maximum sum of any contiguous subarray of length k. O(n) time, O(1) space.
int maxSumFixedWindow(const vector<int>& nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];

    int best = windowSum;
    for (int i = k; i < (int)nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];  // slide: add new, drop old
        best = max(best, windowSum);
    }
    return best;
}

Every element enters the window exactly once and leaves it exactly once, so the total work across the whole array is O(n) regardless of how large k is — a significant improvement over the O(n·k) brute force of resumming each window.

4. Variable-Size Sliding Window

Some problems don't fix the window length in advance — instead they ask for the smallest or largest window satisfying some condition. The pattern still uses two pointers, left and right, but now right always advances while left only advances when the window needs to shrink to restore a property:

#include <vector>
#include <climits>
using namespace std;

// Length of the smallest contiguous subarray whose sum is >= target, or 0 if none exists.
// All values in nums are assumed positive, so shrinking from the left is always safe.
int smallestSubarrayWithSumAtLeast(const vector<int>& nums, int target) {
    int left = 0;
    long long windowSum = 0;
    int best = INT_MAX;

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

The nested while loop looks like it might make this O(n²), but it isn't: left only ever moves forward, and across the entire run of the outer loop it can advance at most n times total. That gives an amortized O(n) time complexity — every index is visited by right once and by left at most once.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.