02 - DSA: Arrays, Strings, DP & Tries

Why This Matters for Temple

Temple (ex-Zomato founding team) tests core algorithmic thinking hard. Arrays, strings, and DP are the bread and butter of coding rounds -- expect at least one per interview. Trie problems show up when they want to see you handle non-trivial data structures beyond hash maps.

Quick Reference

Scan this table in 5 minutes before your interview.

Topic	Pattern	Time Complexity	Key Problems
Two Pointers (sorted)	Opposite ends or same direction	O(n)	Two Sum II (167), 3Sum (15), Container With Most Water (11)
Sliding Window (fixed)	Maintain window of size k	O(n)	Max Subarray Sum of Size K
Sliding Window (variable)	Expand right, shrink left	O(n)	Longest Substring Without Repeating (3), Min Window Substring (76)
Prefix Sum	Precompute cumulative sums	O(n) build, O(1) query	Subarray Sum Equals K (560), Product Except Self (238)
Kadane's Algorithm	Track max ending here	O(n)	Maximum Subarray (53)
Merge Intervals	Sort by start, merge overlaps	O(n log n)	Merge Intervals (56), Insert Interval (57)
Anagram Detection	Frequency map / counter	O(n)	Valid Anagram (242), Group Anagrams (49)
Palindrome	Two pointers / expand from center	O(n) / O(n^2)	Valid Palindrome (125), Longest Palindromic Substring (5)
1D DP	Recurrence on single dimension	O(n)	Climbing Stairs (70), House Robber (198), Coin Change (322)
2D DP	Recurrence on two dimensions	O(n * m)	LCS (1143), Edit Distance (72)
0/1 Knapsack	Include/exclude items	O(n * W)	Partition Equal Subset Sum (416)
Trie	Prefix tree with Map children	O(L) per operation	Implement Trie (208), Word Search II (212)

1. Arrays

1.1 Two Pointers

Two pointers work on sorted arrays (or arrays where order gives structure). Two flavors: opposite ends (converging) and same direction (fast/slow).

Opposite Ends Template

function twoPointerOppositeEnds(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];

    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return null;
}

Same Direction Template

function removeDuplicatesSorted(nums: number[]): number {
  if (nums.length === 0) return 0;

  let slow = 0;

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }

  return slow + 1;
}

Practice Problems

Two Sum II (LC 167) -- Array is sorted. Use opposite-end two pointers. If sum is too small, move left pointer right. If too big, move right pointer left. O(n) time, O(1) space.

Container With Most Water (LC 11) -- Opposite-end pointers. Area = min(height[l], height[r]) * (r - l). Always move the pointer with the shorter height, since moving the taller one can never increase area.

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const water = Math.min(height[left], height[right]) * (right - left);
    maxWater = Math.max(maxWater, water);

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

3Sum (LC 15) -- Sort the array. Fix one element, then use two pointers on the remaining subarray to find pairs that sum to the negation. Skip duplicates at all three levels.

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate fixed element

    let left = i + 1;
    let right = nums.length - 1;
    const target = -nums[i];

    while (left < right) {
      const sum = nums[left] + nums[right];

      if (sum === target) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;   // skip duplicates
        while (left < right && nums[right] === nums[right - 1]) right--; // skip duplicates
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

1.2 Sliding Window

Use when you need to examine contiguous subarrays/substrings. Two variants based on whether the window size is fixed or variable.

Fixed-Size Window Template

function maxSumSubarrayOfSizeK(nums: number[], k: number): number {
  let windowSum = 0;
  let maxSum = -Infinity;

  for (let i = 0; i < nums.length; i++) {
    windowSum += nums[i]; // expand window

    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= nums[i - k + 1]; // shrink window from the left
    }
  }

  return maxSum;
}

Variable-Size Window Template

function variableSlidingWindow(s: string): number {
  const windowMap = new Map<string, number>(); // track window state
  let left = 0;
  let result = 0;

  for (let right = 0; right < s.length; right++) {
    // Expand: add s[right] to window state
    windowMap.set(s[right], (windowMap.get(s[right]) || 0) + 1);

    // Shrink: while window is invalid, remove s[left] and move left forward
    while (/* window is invalid */) {
      const leftChar = s[left];
      windowMap.set(leftChar, windowMap.get(leftChar)! - 1);
      if (windowMap.get(leftChar) === 0) windowMap.delete(leftChar);
      left++;
    }

    // Update result (depends on whether you want max or min window)
    result = Math.max(result, right - left + 1);
  }

  return result;
}

Practice Problems

Longest Substring Without Repeating Characters (LC 3) -- Variable window. Expand right; if a duplicate is found, shrink from left until the duplicate is removed. Track characters with a Set or Map.

function lengthOfLongestSubstring(s: string): number {
  const charSet = new Set<string>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    charSet.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

Minimum Window Substring (LC 76) -- Variable window. Expand right to include characters; once all target characters are covered, shrink from left to find the minimum valid window. Use two frequency maps.

function minWindow(s: string, t: string): string {
  if (t.length > s.length) return "";

  const need = new Map<string, number>();
  for (const c of t) {
    need.set(c, (need.get(c) || 0) + 1);
  }

  let have = 0;
  const required = need.size; // number of unique characters we need to satisfy
  const window = new Map<string, number>();

  let left = 0;
  let minLen = Infinity;
  let minStart = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c) || 0) + 1);

    // Check if this character's count is now satisfied
    if (need.has(c) && window.get(c) === need.get(c)) {
      have++;
    }

    // Shrink from left while the window is valid
    while (have === required) {
      const windowSize = right - left + 1;
      if (windowSize < minLen) {
        minLen = windowSize;
        minStart = left;
      }

      const leftChar = s[left];
      window.set(leftChar, window.get(leftChar)! - 1);
      if (need.has(leftChar) && window.get(leftChar)! < need.get(leftChar)!) {
        have--;
      }
      left++;
    }
  }

  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

1.3 Prefix Sum

Precompute cumulative sums so you can answer range-sum queries in O(1). Sum of subarray [i, j] = prefix[j + 1] - prefix[i].

Build Prefix Array

function buildPrefixSum(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  return prefix;
  // rangeSum(i, j) = prefix[j + 1] - prefix[i]
}

Practice Problems

Subarray Sum Equals K (LC 560) -- Use a hash map of prefix sums. For each index, check if currentPrefix - k exists in the map. This counts subarrays that sum to k. O(n) time.

function subarraySum(nums: number[], k: number): number {
  const prefixCount = new Map<number, number>([[0, 1]]); // empty prefix sum = 0 appears once
  let currentSum = 0;
  let count = 0;

  for (const num of nums) {
    currentSum += num;

    // If (currentSum - k) was seen as a prefix sum, those subarrays sum to k
    if (prefixCount.has(currentSum - k)) {
      count += prefixCount.get(currentSum - k)!;
    }

    prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
  }

  return count;
}

Product of Array Except Self (LC 238) -- Build left-product and right-product arrays. result[i] = leftProduct[i] * rightProduct[i]. O(n) time, O(1) extra space if you reuse the output array.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(1);

  // Left pass: result[i] = product of everything to the left of i
  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    result[i] = leftProduct;
    leftProduct *= nums[i];
  }

  // Right pass: multiply by product of everything to the right of i
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= nums[i];
  }

  return result;
}

1.4 Kadane's Algorithm

Finds the maximum sum contiguous subarray in O(n).

Core idea: at each index, decide whether to extend the current subarray or start fresh.

function maxSubArray(nums: number[]): number {
  let maxEndingHere = nums[0];
  let maxSoFar = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Either extend the previous subarray or start a new one at nums[i]
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  return maxSoFar;
}

Maximum Subarray (LC 53) -- Direct application of Kadane's. To also track the subarray indices, store start/end whenever maxSoFar is updated.

Complexity: O(n) time, O(1) space.

1.5 Merge Intervals

Sort intervals by start time, then merge overlapping ones greedily.

Template

function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    const current = intervals[i];

    if (current[0] <= last[1]) {
      // Overlapping — merge by extending end
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
  }

  return merged;
}

Practice Problems

Merge Intervals (LC 56) -- Direct application of the template above. O(n log n) time for sorting.

Insert Interval (LC 57) -- Three phases: (1) add all intervals that end before newInterval starts, (2) merge all overlapping intervals with newInterval, (3) add remaining intervals.

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let i = 0;

  // Phase 1: intervals that end before newInterval starts
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Phase 2: merge overlapping intervals
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);

  // Phase 3: remaining intervals
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

2. Strings

2.1 Anagram Detection

Two strings are anagrams if they have the same character frequencies. Use a frequency map (or a fixed-size array for lowercase letters).

Frequency Map Template

function buildFrequencyMap(s: string): Map<string, number> {
  const freq = new Map<string, number>();
  for (const c of s) {
    freq.set(c, (freq.get(c) || 0) + 1);
  }
  return freq;
}

function areMapsEqual(a: Map<string, number>, b: Map<string, number>): boolean {
  if (a.size !== b.size) return false;
  for (const [key, val] of a) {
    if (b.get(key) !== val) return false;
  }
  return true;
}

Practice Problems

Valid Anagram (LC 242) -- Build frequency maps for both strings and compare. O(n) time. Alternatively, use a single array of 26 counts: increment for s, decrement for t, check all zeros.

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

  const counts = new Array(26).fill(0);
  const aCode = "a".charCodeAt(0);

  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - aCode]++;
    counts[t.charCodeAt(i) - aCode]--;
  }

  return counts.every((c) => c === 0);
}

Group Anagrams (LC 49) -- Group strings by their sorted form (or by a frequency key). Use a Map where the key is the sorted string and the value is the list of anagrams.

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();

  for (const s of strs) {
    const key = s.split("").sort().join("");
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(s);
  }

  return Array.from(map.values());
}

2.2 Palindrome

Two Pointer (Validation)

function isPalindrome(s: string): boolean {
  // Strip non-alphanumeric and lowercase
  const cleaned = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
  let left = 0;
  let right = cleaned.length - 1;

  while (left < right) {
    if (cleaned[left] !== cleaned[right]) return false;
    left++;
    right--;
  }

  return true;
}

Expand from Center (Finding Longest Palindrome)

For every possible center (2n - 1 centers: n single-char + n-1 between-char), expand outward while characters match.

function longestPalindrome(s: string): string {
  if (s.length < 2) return s;

  let start = 0;
  let maxLen = 1;

  function expandAroundCenter(left: number, right: number): void {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      const len = right - left + 1;
      if (len > maxLen) {
        start = left;
        maxLen = len;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // odd-length palindromes
    expandAroundCenter(i, i + 1); // even-length palindromes
  }

  return s.substring(start, start + maxLen);
}

Practice Problems

Valid Palindrome (LC 125) -- Two pointers after cleaning the string. O(n) time.

Longest Palindromic Substring (LC 5) -- Expand from center. O(n^2) time, O(1) space. Manacher's algorithm does it in O(n) but is rarely expected in interviews.

2.3 Substring Search

Sliding Window + Hash Map

Use sliding window with a frequency map to find substrings that match a pattern.

Find All Anagrams in a String (LC 438) -- Slide a window of size p.length over s. Maintain a frequency map of the window and compare against the frequency map of p.

function findAnagrams(s: string, p: string): number[] {
  if (p.length > s.length) return [];

  const result: number[] = [];
  const pCount = new Array(26).fill(0);
  const sCount = new Array(26).fill(0);
  const aCode = "a".charCodeAt(0);

  // Build frequency for p and the first window
  for (let i = 0; i < p.length; i++) {
    pCount[p.charCodeAt(i) - aCode]++;
    sCount[s.charCodeAt(i) - aCode]++;
  }

  // Helper to compare two count arrays
  function arraysEqual(a: number[], b: number[]): boolean {
    for (let i = 0; i < 26; i++) {
      if (a[i] !== b[i]) return false;
    }
    return true;
  }

  if (arraysEqual(pCount, sCount)) result.push(0);

  // Slide the window
  for (let i = p.length; i < s.length; i++) {
    sCount[s.charCodeAt(i) - aCode]++;              // add new right character
    sCount[s.charCodeAt(i - p.length) - aCode]--;   // remove old left character

    if (arraysEqual(pCount, sCount)) {
      result.push(i - p.length + 1);
    }
  }

  return result;
}

Optimization note: Instead of comparing arrays on every step, maintain a matches counter that tracks how many of the 26 characters have equal counts. When matches === 26, you have an anagram. This brings the per-step work from O(26) to O(1).

3. Dynamic Programming

DP Approach (How to Think About Any DP Problem)

Identify the subproblem: What is dp[i] (or dp[i][j])? Define it clearly in English.
Write the recurrence relation: How does dp[i] relate to smaller subproblems?
Determine base cases: What are the trivially solvable subproblems?
Choose direction: Bottom-up (tabulation) or top-down (memoization)?
Optimize space if possible (often you only need the previous row/value).

Bottom-up vs Top-down:

	Bottom-Up (Tabulation)	Top-Down (Memoization)
Style	Iterative, fill table	Recursive + cache
Ordering	Must figure out fill order	Automatic via recursion
Space optimization	Easier to apply	Harder
Stack overflow risk	None	Yes, for deep recursion
When to use	When subproblem ordering is clear	When only a subset of subproblems are needed

3.1 1D DP

Climbing Stairs (LC 70)

Subproblem: dp[i] = number of ways to reach step i. Recurrence: dp[i] = dp[i - 1] + dp[i - 2] (you can take 1 or 2 steps). Base cases: dp[0] = 1, dp[1] = 1.

// Top-down (memoization)
function climbStairsMemo(n: number): number {
  const memo = new Map<number, number>();

  function dp(i: number): number {
    if (i <= 1) return 1;
    if (memo.has(i)) return memo.get(i)!;

    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }

  return dp(n);
}

// Bottom-up (tabulation)
function climbStairsTab(n: number): number {
  if (n <= 1) return 1;

  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

// Space-optimized: O(1) space
function climbStairs(n: number): number {
  if (n <= 1) return 1;

  let prev2 = 1; // dp[i-2]
  let prev1 = 1; // dp[i-1]

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Complexity: O(n) time, O(1) space (optimized).

House Robber (LC 198)

Subproblem: dp[i] = max money you can rob from houses 0..i. Recurrence: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) -- skip house i, or rob it (and skip i-1). Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

// Top-down (memoization)
function robMemo(nums: number[]): number {
  const memo = new Map<number, number>();

  function dp(i: number): number {
    if (i < 0) return 0;
    if (memo.has(i)) return memo.get(i)!;

    const result = Math.max(dp(i - 1), dp(i - 2) + nums[i]);
    memo.set(i, result);
    return result;
  }

  return dp(nums.length - 1);
}

// Bottom-up (tabulation)
function robTab(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];

  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);

  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }

  return dp[n - 1];
}

// Space-optimized: O(1) space
function rob(nums: number[]): number {
  let prev2 = 0; // dp[i-2]
  let prev1 = 0; // dp[i-1]

  for (const num of nums) {
    const current = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Complexity: O(n) time, O(1) space (optimized).

Coin Change (LC 322)

Subproblem: dp[amount] = minimum coins needed to make amount. Recurrence: dp[amount] = min(dp[amount - coin] + 1) for each coin. Base case: dp[0] = 0.

// Top-down (memoization)
function coinChangeMemo(coins: number[], amount: number): number {
  const memo = new Map<number, number>();

  function dp(remaining: number): number {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining)!;

    let minCoins = Infinity;
    for (const coin of coins) {
      const result = dp(remaining - coin);
      minCoins = Math.min(minCoins, result + 1);
    }

    memo.set(remaining, minCoins);
    return minCoins;
  }

  const result = dp(amount);
  return result === Infinity ? -1 : result;
}

// Bottom-up (tabulation)
function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] !== Infinity) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

Complexity: O(amount * coins.length) time, O(amount) space.

3.2 2D DP

Longest Common Subsequence (LC 1143)

Subproblem: dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1].

Recurrence:

If text1[i-1] === text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base cases: dp[0][j] = 0, dp[i][0] = 0 (empty string has LCS 0).

Grid visualization:

        ""  a  c  e
    ""   0  0  0  0
    a    0  1  1  1
    b    0  1  1  1
    c    0  1  2  2
    d    0  1  2  2
    e    0  1  2  3

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;

  // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

Complexity: O(m * n) time, O(m * n) space. Can be optimized to O(min(m, n)) space since each row only depends on the previous row.

Edit Distance (LC 72)

Subproblem: dp[i][j] = minimum edits to convert word1[0..i-1] to word2[0..j-1].

Recurrence:

If word1[i-1] === word2[j-1]: dp[i][j] = dp[i-1][j-1] (no edit needed)
Else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
- dp[i-1][j-1] = replace
- dp[i-1][j] = delete from word1
- dp[i][j-1] = insert into word1

Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all).

Grid visualization for "horse" -> "ros":

        ""  r  o  s
    ""   0  1  2  3
    h    1  1  2  3
    o    2  2  1  2
    r    3  2  2  2
    s    4  3  3  2
    e    5  4  4  3

function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;

  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );

  // Base cases
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1], // replace
          dp[i - 1][j],     // delete
          dp[i][j - 1]      // insert
        );
      }
    }
  }

  return dp[m][n];
}

Complexity: O(m * n) time, O(m * n) space. Can be optimized to O(n) space with rolling array.

3.3 Knapsack

0/1 Knapsack Template

Given n items, each with a weight and value, and a capacity W, maximize total value without exceeding capacity. Each item can be used at most once.

Subproblem: dp[i][w] = max value using items 0..i-1 with capacity w. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]) if weight[i-1] <= w.

// Standard 2D
function knapsack01(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () =>
    new Array(capacity + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // don't take item i

      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1] // take item i
        );
      }
    }
  }

  return dp[n][capacity];
}

Space Optimization Trick

Since each row only depends on the previous row, use a 1D array. Iterate capacity in reverse to avoid using an item twice (this is the key trick for 0/1 knapsack).

function knapsack01Optimized(weights: number[], values: number[], capacity: number): number {
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // Iterate in REVERSE to ensure each item is used at most once
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

Why reverse? If you iterate forward, dp[w - weights[i]] might already include item i from this iteration, effectively allowing unlimited use. Reverse iteration ensures you reference values from the previous iteration (without item i).

Unbounded Knapsack

Each item can be used unlimited times. Same as 0/1 but iterate capacity forward instead of reverse (or use dp[i][w - weight[i-1]] instead of dp[i-1][w - weight[i-1]]).

function knapsackUnbounded(weights: number[], values: number[], capacity: number): number {
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // Iterate FORWARD — allows reusing the same item
    for (let w = weights[i]; w <= capacity; w++) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

Complexity (both variants): O(n * W) time, O(W) space (optimized).

Note: Coin Change (LC 322) is an unbounded knapsack problem where you minimize count instead of maximizing value. Partition Equal Subset Sum (LC 416) is a 0/1 knapsack where the target is half the total sum.

4. Trie (Prefix Tree)

A trie is a tree where each node represents a character, and paths from root to nodes represent prefixes. Essential for efficient prefix lookups, autocomplete, and word search problems.

Full Trie Implementation

class TrieNode {
  children: Map<string, TrieNode>;
  isEnd: boolean;

  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  /** Insert a word into the trie. O(L) time where L = word length. */
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  /** Check if the exact word exists in the trie. O(L) time. */
  search(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.isEnd;
  }

  /** Check if any word in the trie starts with the given prefix. O(L) time. */
  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }

  /** Traverse to the node at the end of the given prefix, or return null. */
  private findNode(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return null;
      }
      node = node.children.get(char)!;
    }
    return node;
  }
}

Complexity Analysis

Operation	Time	Space
insert	O(L)	O(L) worst case (new nodes)
search	O(L)	O(1)
startsWith	O(L)	O(1)
Total space	--	O(N * L) where N = number of words

L = length of the word/prefix. The Map-based approach uses more memory per node than an array of 26, but handles arbitrary character sets (not just lowercase).

Word Search II (LC 212): Trie + Backtracking

Given an m x n board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontal/vertical). Each cell can be used at most once per word.

Approach:

Build a trie from all target words.
DFS/backtrack from every cell on the board.
At each cell, follow the trie. If you reach isEnd, you found a word.
Prune: if the current trie node has no children matching the current cell, backtrack immediately.

function findWords(board: string[][], words: string[]): string[] {
  const root = new TrieNode();

  // Build trie from word list
  for (const word of words) {
    let node = root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  const rows = board.length;
  const cols = board[0].length;
  const result: string[] = [];
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function backtrack(r: number, c: number, node: TrieNode, path: string): void {
    const char = board[r][c];
    const childNode = node.children.get(char);

    if (!childNode) return; // no matching trie path — prune

    const currentPath = path + char;

    if (childNode.isEnd) {
      result.push(currentPath);
      childNode.isEnd = false; // avoid duplicate results
    }

    // Mark as visited
    board[r][c] = "#";

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== "#") {
        backtrack(nr, nc, childNode, currentPath);
      }
    }

    // Restore
    board[r][c] = char;

    // Optimization: remove leaf nodes to speed up future searches
    if (childNode.children.size === 0) {
      node.children.delete(char);
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      backtrack(r, c, root, "");
    }
  }

  return result;
}

Complexity:

Time: O(M * N * 4^L) worst case, but trie pruning makes it much faster in practice. M*N = board cells, L = max word length.
Space: O(W * L) for the trie, where W = number of words.

Key optimizations:

Set isEnd = false after finding a word to avoid duplicate results.
Delete leaf trie nodes after backtracking (progressive pruning).
Using the board itself for visited tracking (board[r][c] = "#") saves space over a separate visited set.

Practice Problem Summary

#	Problem	Category	Pattern	Complexity
167	Two Sum II	Array	Two pointers (opposite)	O(n)
11	Container With Most Water	Array	Two pointers (opposite)	O(n)
15	3Sum	Array	Sort + two pointers	O(n^2)
3	Longest Substring Without Repeating	String	Sliding window (variable)	O(n)
76	Minimum Window Substring	String	Sliding window (variable)	O(n)
560	Subarray Sum Equals K	Array	Prefix sum + hash map	O(n)
238	Product of Array Except Self	Array	Left/right product	O(n)
53	Maximum Subarray	Array	Kadane's	O(n)
56	Merge Intervals	Array	Sort + merge	O(n log n)
57	Insert Interval	Array	Three-phase merge	O(n)
242	Valid Anagram	String	Frequency count	O(n)
49	Group Anagrams	String	Sorted key grouping	O(n * k log k)
125	Valid Palindrome	String	Two pointers	O(n)
5	Longest Palindromic Substring	String	Expand from center	O(n^2)
438	Find All Anagrams in a String	String	Sliding window + freq count	O(n)
70	Climbing Stairs	DP	1D DP (Fibonacci)	O(n)
198	House Robber	DP	1D DP (skip/take)	O(n)
322	Coin Change	DP	Unbounded knapsack	O(n * amount)
1143	Longest Common Subsequence	DP	2D DP	O(m * n)
72	Edit Distance	DP	2D DP	O(m * n)
208	Implement Trie	Trie	Prefix tree	O(L) per op
212	Word Search II	Trie	Trie + backtracking	O(MN 4^L)

02 - DSA: Arrays, Strings, DP & Tries ​

Why This Matters for Temple ​

Quick Reference ​

1. Arrays ​

1.1 Two Pointers ​

Opposite Ends Template ​

Same Direction Template ​

Practice Problems ​

1.2 Sliding Window ​

Fixed-Size Window Template ​

Variable-Size Window Template ​

Practice Problems ​

1.3 Prefix Sum ​

Build Prefix Array ​

Practice Problems ​

1.4 Kadane's Algorithm ​

1.5 Merge Intervals ​

Template ​

Practice Problems ​

2. Strings ​

2.1 Anagram Detection ​

Frequency Map Template ​

Practice Problems ​

2.2 Palindrome ​

Two Pointer (Validation) ​

Expand from Center (Finding Longest Palindrome) ​

Practice Problems ​

2.3 Substring Search ​

Sliding Window + Hash Map ​

3. Dynamic Programming ​

DP Approach (How to Think About Any DP Problem) ​

3.1 1D DP ​

Climbing Stairs (LC 70) ​

House Robber (LC 198) ​

Coin Change (LC 322) ​

3.2 2D DP ​

Longest Common Subsequence (LC 1143) ​

Edit Distance (LC 72) ​

3.3 Knapsack ​

0/1 Knapsack Template ​

Space Optimization Trick ​

Unbounded Knapsack ​

4. Trie (Prefix Tree) ​

Full Trie Implementation ​

Complexity Analysis ​

Word Search II (LC 212): Trie + Backtracking ​

Practice Problem Summary ​

02 - DSA: Arrays, Strings, DP & Tries

Why This Matters for Temple

Quick Reference

1. Arrays

1.1 Two Pointers

Opposite Ends Template

Same Direction Template

Practice Problems

1.2 Sliding Window

Fixed-Size Window Template

Variable-Size Window Template

Practice Problems

1.3 Prefix Sum

Build Prefix Array

Practice Problems

1.4 Kadane's Algorithm

1.5 Merge Intervals

Template

Practice Problems

2. Strings

2.1 Anagram Detection

Frequency Map Template

Practice Problems

2.2 Palindrome

Two Pointer (Validation)

Expand from Center (Finding Longest Palindrome)

Practice Problems

2.3 Substring Search

Sliding Window + Hash Map

3. Dynamic Programming

DP Approach (How to Think About Any DP Problem)

3.1 1D DP

Climbing Stairs (LC 70)

House Robber (LC 198)

Coin Change (LC 322)

3.2 2D DP

Longest Common Subsequence (LC 1143)

Edit Distance (LC 72)

3.3 Knapsack

0/1 Knapsack Template

Space Optimization Trick

Unbounded Knapsack

4. Trie (Prefix Tree)

Full Trie Implementation

Complexity Analysis

Word Search II (LC 212): Trie + Backtracking

Practice Problem Summary