The most fundamental data structures — manipulation patterns, prefix sums, and Kadane's algorithm

Arrays & Strings

Arrays and strings are where most interview problems live. Not because they are complex data structures, but because they are the canvas for demonstrating algorithmic thinking. You need to be fluent with the manipulation patterns that recur across hundreds of problems.

Core Operations and Their Costs

Operation	Array	String (immutable)
Access by index	O(1)	O(1)
Search	O(n)	O(n)
Insert at end	O(1) amortized	O(n) -- creates new string
Insert at position	O(n)	O(n)
Delete	O(n)	O(n)
Concatenation	O(n)	O(n) -- watch out for loops

The string trap: In most languages, strings are immutable. Concatenating in a loop creates a new string each time, turning O(n) into O(n^2). Use an array/builder and join at the end.

// BAD: O(n^2) due to string concatenation in loop
function buildStringBad(n: number): string {
  let result = '';
  for (let i = 0; i < n; i++) {
    result += String(i);  // new string each time
  }
  return result;
}

// GOOD: O(n)
function buildStringGood(n: number): string {
  const parts: string[] = [];
  for (let i = 0; i < n; i++) {
    parts.push(String(i));
  }
  return parts.join('');
}

Prefix Sum

Prefix sum lets you answer "what is the sum of elements from index i to j?" in O(1) after O(n) preprocessing.

function buildPrefixSum(arr: number[]): number[] {
  const prefix = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  return prefix;
}

// Sum of elements from index i to j (inclusive)
function rangeSum(prefix: number[], i: number, j: number): number {
  return prefix[j + 1] - prefix[i];
}

// Example: arr = [1, 2, 3, 4, 5]
// prefix = [0, 1, 3, 6, 10, 15]
// rangeSum(1, 3) = prefix[4] - prefix[1] = 10 - 1 = 9  (2+3+4)

When to use prefix sum:

Subarray sum queries after preprocessing
Finding subarrays with a target sum (combine with hash map)
2D prefix sums for matrix region queries

Subarray Sum Equals K

A classic that combines prefix sum with hash map:

function subarraySum(nums: number[], k: number): number {
  const prefixCount = new Map<number, number>();
  prefixCount.set(0, 1);
  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;
    // If (sum - k) was a prefix sum before, then the subarray
    // between that prefix and current index sums to k
    count += prefixCount.get(sum - k) ?? 0;
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }

  return count;
}

Kadane's Algorithm

Find the maximum sum contiguous subarray in O(n). The idea: at each position, either extend the current subarray or start a new one.

function maxSubarraySum(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];

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

  return maxSum;
}

// Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// Answer: 6 (subarray [4, -1, 2, 1])

Variations:

Maximum product subarray: track both max and min (negative * negative = positive)
Maximum circular subarray: max(kadane(arr), totalSum - kadane_min(arr))
Return the actual subarray: track start/end indices

In-Place Array Manipulation

Many interview problems ask you to modify an array in-place with O(1) extra space.

Remove Duplicates from Sorted Array

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  let writePos = 1;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i - 1]) {
      nums[writePos] = nums[i];
      writePos++;
    }
  }

  return writePos;
}

Dutch National Flag (3-way partition)

Partition an array into three sections. Classic: sort colors (0s, 1s, 2s).

function sortColors(nums: number[]): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // don't increment mid -- need to check swapped element
    }
  }
}

String Patterns

Valid Anagram

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const count = new Map<string, number>();
  for (const c of s) {
    count.set(c, (count.get(c) ?? 0) + 1);
  }
  for (const c of t) {
    const val = (count.get(c) ?? 0) - 1;
    if (val < 0) return false;
    count.set(c, val);
  }

  return true;
}

Reverse Words in a String

function reverseWords(s: string): string {
  return s.trim().split(/\s+/).reverse().join(' ');
}

Longest Common Prefix

function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) return '';
  let prefix = strs[0];

  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);
      if (prefix === '') return '';
    }
  }

  return prefix;
}

Matrix as 2D Array

Spiral Order Traversal

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let j = left; j <= right; j++) result.push(matrix[top][j]);
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }

  return result;
}

Key Takeaways

Prefix sum turns range-sum queries from O(n) to O(1). Combine with hash map for subarray-sum problems.
Kadane's algorithm is the template for maximum subarray. Extend or restart at each position.
In-place manipulation usually means a write pointer that trails behind a read pointer.
String immutability means building strings in a loop is O(n^2). Always collect into an array and join.
Two pointers on sorted arrays is covered in its own article -- it deserves the space.

When an interview problem gives you an array or string, ask yourself: "Is this a prefix sum problem? A two-pointer problem? A hash map counting problem? A sliding window problem?" That question alone eliminates most of the solution space.

Arrays & Strings

On this page