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:

```cpp 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)

```cpp // 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.

```cpp // 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();

</div>
<div class="ch-cplx-row">
  <span class="ch-cplx"><span>Time</span>O(n)</span>
  <span class="ch-cplx"><span>Space</span>O(1)</span>
</div>
<div class="ch-ed-problems">
<table>
  <thead><tr><th>#</th><th>Problem</th><th>Pattern</th><th>Diff</th></tr></thead>
  <tbody>
<tr><td>1</td><td><a href="https://leetcode.com/problems/valid-palindrome/" target="_blank">125. Valid Palindrome</a></td><td>Opposite-end</td><td class="diff-easy">Easy</td></tr>
<tr><td>2</td><td><a href="https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/" target="_blank">167. Two Sum II</a></td><td>Opposite-end (sorted)</td><td class="diff-medium">Medium</td></tr>
<tr><td>3</td><td><a href="https://leetcode.com/problems/reverse-string/" target="_blank">344. Reverse String</a></td><td>Opposite-end swap</td><td class="diff-easy">Easy</td></tr>
<tr><td>4</td><td><a href="https://leetcode.com/problems/squares-of-a-sorted-array/" target="_blank">977. Squares of a Sorted Array</a></td><td>Opposite-end merge</td><td class="diff-easy">Easy</td></tr>
<tr><td>5</td><td><a href="https://leetcode.com/problems/move-zeroes/" target="_blank">283. Move Zeroes</a></td><td>Fast/Slow (same dir)</td><td class="diff-easy">Easy</td></tr>
<tr><td>6</td><td><a href="https://leetcode.com/problems/remove-duplicates-from-sorted-array/" target="_blank">26. Remove Duplicates from Sorted Array</a></td><td>Fast/Slow (write head)</td><td class="diff-easy">Easy</td></tr>
<tr><td>7</td><td><a href="https://leetcode.com/problems/is-subsequence/" target="_blank">392. Is Subsequence</a></td><td>Two-array pointers</td><td class="diff-easy">Easy</td></tr>
<tr><td>8</td><td><a href="https://leetcode.com/problems/3sum/" target="_blank">15. 3Sum</a></td><td>Sort + opposite-end</td><td class="diff-medium">Medium</td></tr>
<tr><td>9</td><td><a href="https://leetcode.com/problems/container-with-most-water/" target="_blank">11. Container With Most Water</a></td><td>Opposite-end (greedy)</td><td class="diff-medium">Medium</td></tr>
<tr><td>10</td><td><a href="https://leetcode.com/problems/trapping-rain-water/" target="_blank">42. Trapping Rain Water</a></td><td>Two-pointer + max tracking</td><td class="diff-hard">Hard</td></tr>
  </tbody>
</table>
</div>
</div>
<div class="chapter-section">
<h2 class="section-heading">Section 3 — Pattern: Sliding Window</h2>
<p>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.</p>
<div class="insight-box">
  <span class="insight-label">Two Sliding Window Variants</span>
  <ul>
<li><strong>Variable size window:</strong> expand right always, shrink left while a constraint is violated. Used for 'longest subarray satisfying condition'.</li>
<li><strong>Fixed size window (size k):</strong> slide — add nums[right], subtract nums[right-k] each step. Used for 'average/max/sum over every window of size k'.</li>
  </ul>
</div>
<h3 class="section-subheading">3.1 — Variable-Size Window</h3>
<div class="ch-code-wrap">
```cpp
// 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

```cpp // 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).

```cpp // Build 1D prefix sum — O(n) vector 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]++; }

</div>
<div class="ch-cplx-row">
  <span class="ch-cplx"><span>Build</span>O(n)</span>
  <span class="ch-cplx"><span>Query</span>O(1)</span>
  <span class="ch-cplx"><span>Space</span>O(n)</span>
</div>
<div class="ch-ed-problems">
<table>
  <thead><tr><th>#</th><th>Problem</th><th>Pattern</th><th>Diff</th></tr></thead>
  <tbody>
<tr><td>19</td><td><a href="https://leetcode.com/problems/running-sum-of-1d-array/" target="_blank">1480. Running Sum of 1d Array</a></td><td>Build prefix sum</td><td class="diff-easy">Easy</td></tr>
<tr><td>20</td><td><a href="https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/" target="_blank">1413. Minimum Value to Get Positive Step by Step Sum</a></td><td>Prefix + min</td><td class="diff-easy">Easy</td></tr>
<tr><td>21</td><td><a href="https://leetcode.com/problems/k-radius-subarray-averages/" target="_blank">2090. K Radius Subarray Averages</a></td><td>Prefix + range query</td><td class="diff-medium">Medium</td></tr>
<tr><td>22</td><td><a href="https://leetcode.com/problems/range-sum-query-immutable/" target="_blank">303. Range Sum Query - Immutable</a></td><td>Classic prefix query</td><td class="diff-easy">Easy</td></tr>
<tr><td>23</td><td><a href="https://leetcode.com/problems/subarray-sum-equals-k/" target="_blank">560. Subarray Sum Equals K</a></td><td>Prefix + HashMap</td><td class="diff-medium">Medium</td></tr>
<tr><td>24</td><td><a href="https://leetcode.com/problems/contiguous-array/" target="_blank">525. Contiguous Array</a></td><td>Transformed prefix + HashMap</td><td class="diff-medium">Medium</td></tr>
<tr><td>25</td><td><a href="https://leetcode.com/problems/product-of-array-except-self/" target="_blank">238. Product of Array Except Self</a></td><td>Prefix/suffix product</td><td class="diff-medium">Medium</td></tr>
<tr><td>26</td><td><a href="https://leetcode.com/problems/find-pivot-index/" target="_blank">724. Find Pivot Index</a></td><td>Prefix = suffix check</td><td class="diff-easy">Easy</td></tr>
  </tbody>
</table>
</div>
</div>
</div><!-- end .chapter-content -->
<div class="chapter-nav-footer">
  <a href="/learning/dsa/recursion/ch0-bigo-recursion/" class="ch-nav-footer-btn">← Ch0: Big O & Recursion</a>
  <a href="/learning/dsa/hashing/ch2-hashing/" class="ch-nav-footer-btn primary">Next: Ch2 — Hashing →</a>
</div>