Data Structures

Arrays and Strings

Master array manipulation, two-pointer technique, and sliding window patterns.

Arrays

The most fundamental data structure. A contiguous block of memory holding elements of the same type.

Operations:

  • Access by index: O(1)
  • Search: O(n) unsorted, O(log n) sorted
  • Insert/Delete at end: O(1) amortized
  • Insert/Delete in middle: O(n)

Common Techniques

Two Pointers

Use two pointers (left and right) moving toward each other or in the same direction. Great for:

  • Finding pairs that sum to a target
  • Removing duplicates
  • Palindrome checking

Sliding Window

Maintain a window of elements as you move through the array. Great for:

  • Subarray problems (maximum sum, min length, etc.)
  • String permutation problems

Prefix Sum

Precompute cumulative sums for fast range queries.

Example

javascript
// Two Pointers - find pair with target sum in sorted array
function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

// Two Pointers - reverse an array in-place
function reverse(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++; right--;
  }
  return arr;
}

// Sliding Window - maximum sum subarray of size k
function maxSumSubarray(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;

  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];  // slide window
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Prefix Sum - range sum queries in O(1)
class PrefixSum {
  constructor(nums) {
    this.prefix = [0];
    for (const n of nums) {
      this.prefix.push(this.prefix.at(-1) + n);
    }
  }

  query(left, right) {  // sum of nums[left..right]
    return this.prefix[right + 1] - this.prefix[left];
  }
}

const ps = new PrefixSum([1, 2, 3, 4, 5]);
console.log(ps.query(1, 3));  // 2+3+4 = 9
Try it yourself — JAVASCRIPT