DSAMonth 4 · Week 13

Day 61: Advanced Array & String Manipulations

Consolidate array/string techniques (prefix sums, in-place rotation, frequency counting) into a fast pattern-recognition toolkit for interviews.

Mark this day complete

Study

Concepts

Prefix sums: O(1) range-sum queries after O(n) setup

A prefix sum array where `prefix[i] = arr[0] + ... + arr[i-1]` lets you answer "what is the sum of elements from index i to j" in O(1) via `prefix[j+1] - prefix[i]`, after a one-time O(n) build — this converts any problem with MANY repeated range-sum queries from O(n) per query to O(1) per query, a huge win when queries vastly outnumber array size.

The same idea extends to "subarray sum equals K" style problems (Day 11 revisited): track a running sum and a hash map of `{sum-so-far: count-of-times-seen}` — if `currentSum - k` has been seen before, every occurrence marks a valid subarray ending here, combining prefix sums with the hash-map pattern.

In-place array tricks: rotation and reversal

Rotating an array by k positions in O(1) extra space uses the "reverse three times" trick: reverse the whole array, then reverse the first k elements, then reverse the remaining n-k elements — each reversal is O(n), total still O(n) time but crucially O(1) space instead of allocating a new array.

This reversal trick generalizes to any "cyclic shift" problem, and understanding WHY it works (reversal is its own inverse, and composing the right reversals produces exactly the rotated order) is more valuable than memorizing the steps — you can rederive it under interview pressure if you understand the underlying reasoning.

See It

Visualizations

Visualization

Prefix sum array for [3, 1, 4, 1, 5]

range sum(1,3) = prefix[4] - prefix[1] = 14 - 3 = 11 (1+4+1... wait, indices 1..3 = 1+4+1=6)

prefix[0]

prefix[1]

prefix[2]

prefix[3]

prefix[4]

prefix[5]

Build It

Code Examples

Prefix sums for O(1) range queries

function buildPrefixSums(arr) {
  const prefix = [0];
  for (const num of arr) prefix.push(prefix[prefix.length - 1] + num);
  return prefix;
}

function rangeSum(prefix, i, j) { // sum of arr[i..j] inclusive
  return prefix[j + 1] - prefix[i];
}

const prefix = buildPrefixSums([3, 1, 4, 1, 5]);
console.log(rangeSum(prefix, 1, 3)); // 1 + 4 + 1 = 6, O(1) per query

In-place array rotation via triple reversal

function reverse(arr, start, end) {
  while (start < end) {
    [arr[start], arr[end]] = [arr[end], arr[start]];
    start++; end--;
  }
}

function rotateRight(arr, k) {
  const n = arr.length;
  k = k % n;
  reverse(arr, 0, n - 1);      // reverse everything
  reverse(arr, 0, k - 1);      // reverse the first k (now-correct-position) elements
  reverse(arr, k, n - 1);      // reverse the rest
  return arr;
}

console.log(rotateRight([1, 2, 3, 4, 5, 6, 7], 3)); // [5, 6, 7, 1, 2, 3, 4]

Remember

Key Takeaways

Prefix sums trade O(n) upfront build cost for O(1) range-sum queries — worth it whenever queries repeat.
Combine prefix sums with a hash map (running sum seen-count) for "subarray sums to K" style problems, including negative numbers.
Triple reversal rotates an array in O(n) time, O(1) space — understand WHY it works, not just the steps.
Always ask "how many queries will run against this array" — it determines whether preprocessing (like prefix sums) pays off.
These are building blocks, not standalone answers — expect them to combine with sliding window, two pointers, or hash maps in a single problem.

Do It

Practice

1Solve "Subarray Sum Equals K" using running sum + hash map, and trace through a case with negative numbers.
2Implement rotateLeft using the same triple-reversal idea, adjusting which segments get reversed.
3Solve "Product of Array Except Self" using two passes of running prefix/suffix products, in O(1) extra space (excluding the output array).