Chapter 1 · Intermediate · Prereq: Chapter 0

Arrays & Strings

Two Pointers · Sliding Window · Prefix Sum — three universal patterns that reduce O(n²) brute-force solutions to O(n). Mastering this chapter unlocks solutions to hundreds of problems.

11 Sections 26 Practice Problems Intermediate ← Back to Roadmap

Section 1 — What Are Arrays & Strings?

Arrays and strings are the most common data structures in coding interviews. Nearly every problem — regardless of topic — involves manipulating sequences of elements.

1.1 — Arrays

An array is a contiguous block of memory storing elements of the same type. The key property is O(1) random access — given an index, computing the memory address is a single arithmetic operation.

Array Complexity Summary

Access by index: O(1)
Search (unsorted): O(n)
Search (sorted + binary search): O(log n)
Insert/Delete at end: O(1) amortized
Insert/Delete at middle: O(n) — elements must shift

1.2 — Strings in C++

C++ strings are mutable arrays of characters with O(1) random access. Key operations to know:

string s = "hello world";
s.length();         // O(1) — size cached
s.substr(2, 4);     // O(k) — creates new string of length k
s[i];               // O(1) — direct access
s += "!";           // O(n) amortized — appending
sort(s.begin(), s.end()); // O(n log n)
// Reverse a string in-place O(n)
reverse(s.begin(), s.end());
// Convert int ↔ string
int n = stoi("42");   // string to int
string t = to_string(99); // int to string

Section 2 — Pattern: Two Pointers

Two Pointers eliminates an inner loop by maintaining two indices that together cover the search space. Result: O(n²) → O(n).

2.1 — Opposite-End Pointers

Start with left=0 and right=n-1. Move inward based on a condition. Converge in O(n).

When to Use Opposite-End

Array is sorted (or can be sorted without losing information)
Looking for a pair (two-sum, palindrome check, container with most water)
Need to squeeze from both ends (trapping rain water)

// Palindrome check — O(n) time, O(1) space
int left = 0, right = s.size()-1;
while (left < right) {
    if (s[left] != s[right]) return false;
    left++; right--;
}
return true;
// Two-sum on sorted array — O(n) time, O(1) space
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return {left, right};
    else if (sum < target) left++;
    else right--;
}

2.2 — Fast/Slow Pointers (Same Direction)

Both pointers move right, but at different speeds or with different conditions. Used to filter or compact arrays in-place.

// Remove duplicates from sorted array — slow tracks write head
int slow = 0;
for (int fast = 1; fast < nums.size(); fast++) {
    if (nums[fast] != nums[slow]) nums[++slow] = nums[fast];
}
return slow + 1; // new length

// Move zeroes to end — preserve relative order
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++)
    if (nums[fast]) nums[slow++] = nums[fast];
while (slow < nums.size()) nums[slow++] = 0;

// Is Subsequence — two pointers on two arrays
int i = 0, j = 0;
while (i < s.size() && j < t.size())
    if (s[i] == t[j++]) i++;
return i == s.size();

TimeO(n) SpaceO(1)

#	Problem	Pattern	Diff
1	125. Valid Palindrome	Opposite-end	Easy
2	167. Two Sum II	Opposite-end (sorted)	Medium
3	344. Reverse String	Opposite-end swap	Easy
4	977. Squares of a Sorted Array	Opposite-end merge	Easy
5	283. Move Zeroes	Fast/Slow (same dir)	Easy
6	26. Remove Duplicates from Sorted Array	Fast/Slow (write head)	Easy
7	392. Is Subsequence	Two-array pointers	Easy
8	15. 3Sum	Sort + opposite-end	Medium
9	11. Container With Most Water	Opposite-end (greedy)	Medium
10	42. Trapping Rain Water	Two-pointer + max tracking	Hard

Section 3 — Pattern: Sliding Window

A window is a contiguous subarray [left, right]. Sliding Window maintains and updates a window as right expands — avoiding recompution by only adding/removing boundary elements.

Two Sliding Window Variants

Variable size window: expand right always, shrink left while a constraint is violated. Used for 'longest subarray satisfying condition'.
Fixed size window (size k): slide — add nums[right], subtract nums[right-k] each step. Used for 'average/max/sum over every window of size k'.

3.1 — Variable-Size Window

// Longest subarray with sum ≤ k
int left = 0, curr = 0, ans = 0;
for (int right = 0; right < nums.size(); right++) {
    curr += nums[right];                 // expand
    while (curr > k) curr -= nums[left++]; // shrink
    ans = max(ans, right - left + 1);
}
// Longest substring with at most k distinct chars
unordered_map<char,int> freq;
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
    freq[s[right]]++;
    while (freq.size() > k) {
        if (--freq[s[left]] == 0) freq.erase(s[left]);
        left++;
    }
    ans = max(ans, right - left + 1);
}

3.2 — Fixed-Size Window

// Max sum subarray of size k — O(n)
int curr = 0;
for (int i = 0; i < k; i++) curr += nums[i]; // init window
int ans = curr;
for (int i = k; i < nums.size(); i++) {
    curr += nums[i] - nums[i-k];             // slide
    ans = max(ans, curr);
}

TimeO(n) amortized SpaceO(1) or O(k)

#	Problem	Type	Diff
11	643. Maximum Average Subarray I	Fixed window	Easy
12	1004. Max Consecutive Ones III	Variable window	Medium
13	3. Longest Substring Without Repeating Characters	Variable + set	Medium
14	713. Subarray Product Less Than K	Variable (count valid)	Medium
15	209. Minimum Size Subarray Sum	Variable (min length)	Medium
16	904. Fruit Into Baskets	Variable (≤2 distinct)	Medium
17	239. Sliding Window Maximum	Fixed + deque	Hard
18	76. Minimum Window Substring	Variable + freq map	Hard

Section 4 — Pattern: Prefix Sum

Prefix Sum pre-computes cumulative sums so that any range sum query [l,r] takes O(1) instead of O(n).

Key Formula prefix[i] = prefix[i-1] + nums[i-1]
Range sum nums[l..r] = prefix[r+1] - prefix[l]

Prefix + HashMap trick: Store how many times each prefix sum has appeared. For every curr, ans += freq[curr - target]. This counts subarrays summing to target in O(n).

// Build 1D prefix sum — O(n)
vector<int> prefix(nums.size()+1, 0);
for (int i = 0; i < nums.size(); i++) prefix[i+1] = prefix[i] + nums[i];
// Query range sum [l,r] — O(1)
int rangeSum = prefix[r+1] - prefix[l];

// Count subarrays summing to k — O(n), O(n) space
unordered_map<int,int> freq; freq[0] = 1;
int curr = 0, ans = 0;
for (int x : nums) {
    curr += x;
    ans += freq[curr - k];
    freq[curr]++;
}

BuildO(n) QueryO(1) SpaceO(n)

#	Problem	Pattern	Diff
19	1480. Running Sum of 1d Array	Build prefix sum	Easy
20	1413. Minimum Value to Get Positive Step by Step Sum	Prefix + min	Easy
21	2090. K Radius Subarray Averages	Prefix + range query	Medium
22	303. Range Sum Query - Immutable	Classic prefix query	Easy
23	560. Subarray Sum Equals K	Prefix + HashMap	Medium
24	525. Contiguous Array	Transformed prefix + HashMap	Medium
25	238. Product of Array Except Self	Prefix/suffix product	Medium
26	724. Find Pivot Index	Prefix = suffix check	Easy