Arrays, Strings, and Hash Tables: Deep Dive

This section covers foundational data structures and patterns critical for Google technical interviews. The focus is on understanding why patterns work, not just memorizing solutions.

JavaScript arrays are objects at the language level, but V8 (Chrome’s engine) optimizes them aggressively. When you create an array with numeric indices in sequence, V8 stores it as contiguous memory—like a real array in C. This is crucial for interview performance.

Array Operations: The Real Costs

// O(1) amortized — push/pop
// Amortized: most of the time O(1), occasionally O(n) when capacity doubles
arr.push(5);    // Add to end
arr.pop();      // Remove from end

// O(n) — shift/unshift
// Shifts all elements, not O(1)!
arr.unshift(1); // Add to beginning (shift all right)
arr.shift();    // Remove from beginning (shift all left)

// O(n) — splice
arr.splice(3, 2, 7, 8); // Remove 2 at index 3, insert 7,8 — moves rest

// O(n) — slice
const copy = arr.slice(2, 5); // Creates new array, doesn't mutate

Interview Insight: When you need to remove from the beginning frequently, use a Queue with indices (see next section) or LinkedList instead of array.shift().

String Immutability: The O(n²) Trap

Strings in JavaScript are immutable. Every += operation creates a new string.

// ❌ O(n²) — Common mistake in interviews
let result = "";
for (let i = 0; i < n; i++) {
    result += "a"; // Creates new string each iteration
}
// Why: iteration 1 copies 1 char, iteration 2 copies 2 chars, ..., iteration n copies n chars
// Total: 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²)

// ✅ O(n) — Use array.join()
const chars = [];
for (let i = 0; i < n; i++) {
    chars.push("a");
}
const result = chars.join(""); // Single pass, O(n)

Say this in interview: "I’m avoiding string concatenation in a loop because each += creates a new string in memory. Instead, I’ll build an array and join it at the end—that’s O(n) instead of O(n²)."

2. Two Pointers Pattern

The Core Idea

Two pointers eliminate nested loops by maintaining an invariant about the data. Instead of checking all pairs, you move pointers strategically toward a solution.

Pattern 1: Opposite Ends (Start & End)

let left = 0, right = arr.length - 1;
while (left < right) {
    // Process arr[left] and arr[right]
    // Move based on some condition
    if (someCondition) left++;
    else right--;
}

Why it works: The search space shrinks monotonically. Once we move left past an index, we never need to check it again (given the problem’s invariant).

Pattern 2: Same Starting Point (Different Speeds)

let slow = 0, fast = 0;
while (fast < arr.length) {
    // Process with two pointers at different speeds
    fast++;
    // Maybe increment slow conditionally
}

Why it works: Fast pointer finds patterns (like repeated elements). Slow pointer tracks write position or valid region.

Problem: Two Sum (Sorted Array Version)

Problem: Given a sorted array, find two numbers that add up to target.

Brute Force: O(n²)

function twoSumBrute(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] === target) {
                return [arr[i], arr[j]];
            }
        }
    }
    return null;
}
// Time: O(n²), Space: O(1)

Optimal: Two Pointers O(n)

function twoSumSorted(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) {
            return [arr[left], arr[right]];
        }
        if (sum < target) {
            left++; // Need larger sum
        } else {
            right--; // Need smaller sum
        }
    }
    return null;
}
// Time: O(n), Space: O(1)

Why it works: - Array is sorted - If sum is too small, moving left right increases sum (all elements to right are larger) - If sum is too large, moving right left decreases sum - We explore exactly O(n) candidates

Say this: "Since the array is sorted, I use two pointers: one at each end. If the sum is too small, I move the left pointer right to get a larger sum. If too large, I move right pointer left. Each pointer moves at most n times, so it’s O(n)."

Problem: Container With Most Water

Problem: Given heights array, find two lines that contain the most water.

Heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]
         0  1  2  3  4  5  6  7  8

Water between indices 1 and 8:
- Width = 8 - 1 = 7
- Height = min(8, 7) = 7
- Area = 7 * 7 = 49

Brute Force: O(n²)

Check all pairs of indices.

Optimal: Two Pointers O(n)

function containerWithMostWater(heights) {
    let left = 0, right = heights.length - 1;
    let maxArea = 0;

    while (left < right) {
        const width = right - left;
        const height = Math.min(heights[left], heights[right]);
        const area = width * height;
        maxArea = Math.max(maxArea, area);

        // Move the shorter line — it's the bottleneck
        // Moving the taller line can only decrease area
        if (heights[left] < heights[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}
// Time: O(n), Space: O(1)

Why it works: - Start with widest container (0 to n-1) - Area = width × min(heights) - As we shrink width, we can only increase area if height increases - The shorter line is the bottleneck—moving it might help - Moving the taller line can only decrease area (width decreases, height can’t increase beyond shorter line)

Problem: Valid Palindrome

Problem: Check if string is palindrome (ignore non-alphanumeric, case-insensitive).

Approach: Two Pointers O(n)

function validPalindrome(s) {
    let left = 0, right = s.length - 1;

    while (left < right) {
        // Skip non-alphanumeric
        while (left < right && !isAlphanumeric(s[left])) left++;
        while (left < right && !isAlphanumeric(s[right])) right--;

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

function isAlphanumeric(c) {
    return /[a-zA-Z0-9]/.test(c);
}
// Time: O(n), Space: O(1)

Problem: Remove Duplicates from Sorted Array

Problem: Remove duplicates in-place, return length of array without duplicates.

Approach: Two Pointers (Write & Read)

function removeDuplicates(arr) {
    if (arr.length === 0) return 0;

    let write = 0; // Position to write next unique element

    for (let read = 1; read < arr.length; read++) {
        if (arr[read] !== arr[write]) {
            write++;
            arr[write] = arr[read];
        }
    }

    return write + 1;
}
// Time: O(n), Space: O(1)
// Array: [1, 1, 1, 2, 2, 3]
// After: [1, 2, 3, 2, 2, 3] (first 3 elements are unique)

Why it works: Slow pointer (write) is in the "valid" region. Fast pointer (read) finds the next unique element.

3. Sliding Window Pattern

The Core Idea

Sliding Window maintains aggregate information over a range, updating it incrementally as the window moves. This converts O(n²) problems to O(n).

Fixed-Size Window

function maxSumFixedWindow(arr, k) {
    // Calculate sum of first window
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    let maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k]; // Add right, remove left
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}
// Time: O(n), Space: O(1)

Why it works: - First window: O(k) to compute - Each subsequent window: O(1) — just add new element, remove old element - Total: O(n)

Variable-Size Window (Two Pointers + Sliding Window)

let left = 0;
for (let right = 0; right < arr.length; right++) {
    // Expand window: add arr[right]
    // While condition violated: shrink from left
    while (condition) {
        left++;
    }
    // Process window [left, right]
}

Key insight: Both pointers only move right (never backtrack). So it’s still O(n) total movement.

Problem: Maximum Sum Subarray of Size K

Problem: Find contiguous subarray of length k with max sum.

function maxSubarraySum(arr, k) {
    // Edge case
    if (k > arr.length) return null;

    // First window
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    let maxSum = windowSum;

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

    return maxSum;
}
// Time: O(n), Space: O(1)

Problem: Longest Substring Without Repeating Characters

Problem: Find length of longest substring with all unique characters.

Brute Force: O(n³)

Check all substrings.

Optimal: Sliding Window with Hash Map O(n)

function longestSubstringWithoutRepeating(s) {
    const charIndex = new Map(); // char -> last seen index
    let maxLength = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        // If char seen and in current window, move left
        if (charIndex.has(char) && charIndex.get(char) >= left) {
            left = charIndex.get(char) + 1;
        }

        // Record position and check length
        charIndex.set(char, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}
// Example: "abcabcbb"
// At 'a'(0): left=0, max=1
// At 'b'(1): left=0, max=2
// At 'c'(2): left=0, max=3
// At 'a'(3): 'a' at 0, left=1, max=3
// At 'b'(4): 'b' at 1, left=2, max=3
// At 'c'(5): 'c' at 2, left=3, max=3
// At 'b'(6): 'b' at 4, left=5, max=3
// At 'b'(7): 'b' at 6, left=7, max=3
// Answer: 3 ("abc")
// Time: O(n), Space: O(min(n, charset_size))

Say this: "I use a sliding window with a hash map to track the last seen position of each character. When I encounter a duplicate in my current window, I move the left pointer past the previous occurrence. Since each character is visited twice at most (add and remove from window), it’s O(n)."

Problem: Minimum Window Substring

Problem: Find smallest substring that contains all characters from target string.

function minWindowSubstring(s, t) {
    if (t.length > s.length) return "";

    const targetCount = new Map();
    for (const char of t) {
        targetCount.set(char, (targetCount.get(char) || 0) + 1);
    }

    let required = targetCount.size; // Unique chars needed
    let formed = 0; // Unique chars with desired frequency

    const windowCount = new Map();
    let left = 0;
    let result = [Number.MAX_VALUE, 0, 0]; // [length, left, right]

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

        // If frequency of char matches target
        if (targetCount.has(char) &&
            windowCount.get(char) === targetCount.get(char)) {
            formed++;
        }

        // Try to shrink from left
        while (left <= right && formed === required) {
            const leftChar = s[left];

            // Update result if current window is smaller
            if (right - left + 1 < result[0]) {
                result = [right - left + 1, left, right];
            }

            // Remove left character
            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            if (targetCount.has(leftChar) &&
                windowCount.get(leftChar) < targetCount.get(leftChar)) {
                formed--;
            }

            left++;
        }
    }

    return result[0] === Number.MAX_VALUE ? "" : s.slice(result[1], result[2] + 1);
}
// Example: s = "ADOBECODEBANC", t = "ABC"
// Answer: "BANC"
// Time: O(|s| + |t|), Space: O(|s| + |t|)

4. Binary Search

The Generalized Pattern

Binary search is not just "find element in sorted array." The real power: binary search on the answer space when there’s a monotonic property.

Key Insight: Monotonic Property

Binary search works when: - There’s a property P that’s monotonic (either all true then false, or false then true) - You want to find the boundary

// Template: Find first/smallest X where P(X) is true
function binarySearch(left, right, predicate) {
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (predicate(mid)) {
            right = mid; // Answer is at mid or left of mid
        } else {
            left = mid + 1; // Answer is right of mid
        }
    }
    return left;
}

Critical Details: - left < right (not ⇐): We converge to a single point - right = mid: Could be the answer, don’t exclude - left = mid + 1: Already tested mid, not the answer - Always returns the leftmost position where predicate is true

Alternative Template: Find Last X Where P(X) is True

function binarySearchLast(left, right, predicate) {
    while (left < right) {
        const mid = Math.floor((left + right + 1) / 2); // Ceiling
        if (predicate(mid)) {
            left = mid; // Answer is at mid or right of mid
        } else {
            right = mid - 1; // Answer is left of mid
        }
    }
    return left;
}

Why This Matters

left < right vs left ⇐ right: The latter can infinite loop if you’re not careful
When to use ceiling (Math.floor((left + right + 1) / 2)): When moving left, to avoid infinite loop with 2 elements

Problem: Search in Rotated Sorted Array

Problem: Find target in array that was sorted then rotated.

Original: [1, 2, 3, 4, 5, 6, 7]
Rotated:  [4, 5, 6, 7, 1, 2, 3]

Find 1: Answer is index 4

Approach: Binary Search with Rotation Handling

function searchRotatedArray(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) return mid;

        // Determine which side is sorted
        if (arr[left] <= arr[mid]) {
            // Left side is sorted
            if (arr[left] <= target && target < arr[mid]) {
                right = mid - 1; // Target in left side
            } else {
                left = mid + 1; // Target in right side
            }
        } else {
            // Right side is sorted
            if (arr[mid] < target && target <= arr[right]) {
                left = mid + 1; // Target in right side
            } else {
                right = mid - 1; // Target in left side
            }
        }
    }

    return -1;
}
// Time: O(log n), Space: O(1)

Why it works: - At least one side of the pivot is always sorted - Use that sorted side to narrow search space - Check if target is in the sorted side (using start/end values) - If yes, search that side; if no, search the other side

Problem: Find Minimum in Rotated Sorted Array

Problem: Find minimum value in rotated sorted array.

function findMinRotated(arr) {
    let left = 0, right = arr.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] > arr[right]) {
            // Minimum is to the right of mid
            left = mid + 1;
        } else {
            // Minimum is at mid or to the left (including mid)
            right = mid;
        }
    }

    return arr[left];
}
// Time: O(log n), Space: O(1)

Key insight: Compare mid to right (not left): - If arr[mid] > arr[right]: rotation point is to the right, min is to the right - If arr[mid] ⇐ arr[right]: min is at mid or to the left

Problem: Koko Eating Bananas

Problem: Koko eats bananas from piles at a fixed speed (bananas per hour). Find minimum speed to finish all piles in h hours.

Piles: [1, 1, 1, 1, 1, 1, 1, 1, 1, 9], h = 10
At speed 1: 1+1+1+1+1+1+1+1+1+9 = 18 hours (too slow)
At speed 9: 1+1+1+1+1+1+1+1+1+1 = 10 hours (exactly!)
Answer: 1

Approach: Binary Search on Speed

function kokoBananas(piles, h) {
    // Binary search on speed: 1 to max(piles)
    let left = 1, right = Math.max(...piles);

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const hoursNeeded = hoursToFinish(piles, mid);

        if (hoursNeeded <= h) {
            // Speed is enough, try slower
            right = mid;
        } else {
            // Speed is too slow, try faster
            left = mid + 1;
        }
    }

    return left;
}

function hoursToFinish(piles, speed) {
    let hours = 0;
    for (const pile of piles) {
        hours += Math.ceil(pile / speed);
    }
    return hours;
}
// Time: O(n * log(max_pile)), Space: O(1)

Why it works: - Speed is monotonic: if speed K finishes in time, any speed > K also finishes - Binary search on speed from 1 to max(piles) - For each speed, calculate hours needed (O(n)) - Find the minimum speed where hours ⇐ h

Say this: "I binary search on the speed. For each candidate speed, I calculate how many hours Koko needs and check if it’s ⇐ h. The key insight is monotonicity: if a speed works, all faster speeds work. So I find the minimum speed that works."

Hash Tables

5. How Hash Tables Actually Work

The Mechanism

A hash table is a key-value store that achieves O(1) average-case lookups through hashing.

Hash Table Internal Structure (with Chaining):

Hash function: hash(key) -> bucket index

buckets:
[0] -> null
[1] -> key1:value1 -> key8:value8 -> null  (chain due to collision)
[2] -> key5:value5 -> null
[3] -> null
[4] -> key2:value2 -> key7:value7 -> null  (collision)
...

Lookup key8:
1. hash(key8) = 1
2. Navigate to bucket[1]
3. Linear search through chain (linked list)
4. Find key8, return value8

Analysis

Hash function requirements: - Deterministic: same key always hashes to same bucket - Uniform distribution: minimizes collisions - Fast to compute: O(1)

Time Complexity:

| Operation | Average | Worst Case | |-----------|---------|-----------| | Insert | O(1) | O(n) | | Lookup | O(1) | O(n) | | Delete | O(1) | O(n) |

When is it O(n) worst case?

All keys hash to the same bucket (all collisions). This is rare with a good hash function and reasonable load factor.

Load Factor: size / capacity

Good hash tables maintain load factor ~0.75
When load factor exceeds threshold, hash table resizes (doubles capacity)
Rehashing is O(n) but amortized over O(n) insertions

Real-World Implementation Detail

JavaScript Maps use hash tables internally with sophisticated collision handling (not just simple chaining). The performance is optimized across VM implementations.

6. JS Map vs Object

Map: The Better Choice for Interviews

// Creation
const map = new Map();

// Methods
map.set(key, value);           // Insert/update
map.get(key);                  // Lookup
map.has(key);                  // Check existence
map.delete(key);               // Remove
map.clear();                   // Remove all
map.size;                       // Number of entries

// Iteration
for (const [key, value] of map) { }
for (const key of map.keys()) { }
for (const value of map.values()) { }
for (const [key, value] of map.entries()) { }

// Example: Frequency counting
const freq = new Map();
for (const char of "hello") {
    freq.set(char, (freq.get(char) || 0) + 1);
}
// freq: Map { 'h' => 1, 'e' => 1, 'l' => 2, 'o' => 1 }

Advantages:

| Feature | Map | Object | |---------|-----|--------| | Key type | Any (objects, primitives) | Only strings (auto-converted) | | Iteration | Insertion order | No guaranteed order (in practice insertion, but not spec) | | .size | Native property | Must use Object.keys().length | | Performance | Optimized for frequent add/delete | Optimized for property access | | API | clear(), delete(), has() | Manual deletion, manual has() |

Why use Map for interviews: - Any key type (useful for custom objects, arrays as keys) - .size property (cleaner than Object.keys().length) - .delete() and .has() methods - No confusion with prototype chain

JS Set: For Membership Testing

const set = new Set();

set.add(value);        // Insert
set.has(value);        // Check (O(1) average)
set.delete(value);     // Remove
set.size;              // Cardinality
set.clear();           // Remove all

// Iteration
for (const value of set) { }

// Deduplication
const unique = new Set([1, 2, 2, 3, 3, 3]);
// Set { 1, 2, 3 }
const arr = Array.from(unique); // [1, 2, 3]

When to use: - Checking if value exists: O(1) instead of O(n) array search - Removing duplicates - Intersection/union of arrays

7. Hash Table Patterns for Interviews

Pattern 1: Frequency Counting

Count occurrences of elements.

Problem: Anagram Detection

Problem: Determine if two strings are anagrams.

function isAnagram(s1, s2) {
    if (s1.length !== s2.length) return false;

    const freq = new Map();
    for (const char of s1) {
        freq.set(char, (freq.get(char) || 0) + 1);
    }

    for (const char of s2) {
        if (!freq.has(char)) return false;
        freq.set(char, freq.get(char) - 1);
        if (freq.get(char) === 0) {
            freq.delete(char);
        }
    }

    return freq.size === 0;
}
// Time: O(n), Space: O(1) (at most 26 letters)

Alternative: Sort both strings and compare.

function isAnagramSort(s1, s2) {
    return s1.split('').sort().join('') === s2.split('').sort().join('');
}
// Time: O(n log n), Space: O(n)

For interviews: frequency counting is better (O(n) vs O(n log n)).

Problem: Top K Frequent Elements

Problem: Given array and k, return k most frequent elements.

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]

function topKFrequent(nums, k) {
    // Step 1: Count frequencies
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    // Step 2: Min-heap of size k
    // OR: Sort by frequency and take top k

    // Using sort (simpler, O(n log n)):
    const sorted = Array.from(freq)
        .sort((a, b) => b[1] - a[1]) // Sort by frequency descending
        .slice(0, k)
        .map(entry => entry[0]);

    return sorted;
}
// Time: O(n log n), Space: O(n)

// Optimized with bucket sort (O(n)):
function topKFrequentOptimal(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    // Bucket: index = frequency, value = list of numbers
    const buckets = Array(nums.length + 1).fill(null).map(() => []);

    for (const [num, count] of freq) {
        buckets[count].push(num);
    }

    // Collect from highest frequency down
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        result.push(...buckets[i]);
    }

    return result;
}
// Time: O(n), Space: O(n)

Interview approach: 1. Start with frequency map + sort (O(n log n)) — safe 2. Mention bucket sort optimization (O(n)) — shows optimization thinking 3. Implement the one you’re confident in

Pattern 2: Two Sum with Hash Map

Problem: Given unsorted array, find two numbers that sum to target.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (indices of 2 and 7)

function twoSum(nums, target) {
    const seen = new Map(); // value -> index

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (seen.has(complement)) {
            return [seen.get(complement), i];
        }

        seen.set(nums[i], i);
    }

    return null;
}
// Time: O(n), Space: O(n)

Why it works: - For each element, check if complement exists in hash map - If yes, we found a pair - If no, add current element to map for future lookups

Say this: "I iterate through the array once. For each number, I check if I’ve seen the complement (target - number) before. If yes, I found the pair. If no, I add the current number to the hash map. This is O(n) with one pass."

Pattern 3: Group Anagrams

Problem: Group strings that are anagrams of each other.

Input: ["eat", "tea", "ate", "bat", "tab"]
Output: [["eat", "tea", "ate"], ["bat", "tab"]]

Approach: Sort Each Word as Key

function groupAnagrams(words) {
    const groups = new Map();

    for (const word of words) {
        // Sort letters to get canonical form
        const key = word.split('').sort().join('');

        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}
// Time: O(n * k log k) where k = word length
// Space: O(n * k)
// Explanation: Sorting each word is O(k log k), do this n times

Alternative: Count Each Character

function groupAnagramsCount(words) {
    const groups = new Map();

    for (const word of words) {
        // Count characters, create key
        const freq = Array(26).fill(0);
        for (const char of word) {
            freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = freq.join(','); // "1,0,0,1,..."

        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}
// Time: O(n * k) where k = word length (linear scan, no sort)
// Space: O(n * k)

For interviews: The sort approach is clearer and fast enough. Mention the character count approach as optimization if you have time.

Pattern 4: Subarray Sum Equals K

Problem: Count number of subarrays that sum to k.

Input: nums = [1, 2, 2, 1, 1], k = 2
Subarrays: [2] at [1], [2] at [2], [1,1] at [3,4]
Output: 3

Approach: Prefix Sum + Hash Map

Key insight: If prefixSum[j] - prefixSum[i-1] = k, then subarray [i, j] sums to k.

Rearranged: prefixSum[i-1] = prefixSum[j] - k

function subarraySumEqualsK(nums, k) {
    let count = 0;
    let prefixSum = 0;
    const sumFreq = new Map();
    sumFreq.set(0, 1); // Base case: empty prefix sums to 0

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

        // How many times did we see (prefixSum - k)?
        const complement = prefixSum - k;
        if (sumFreq.has(complement)) {
            count += sumFreq.get(complement);
        }

        // Add current prefixSum to map
        sumFreq.set(prefixSum, (sumFreq.get(prefixSum) || 0) + 1);
    }

    return count;
}
// Example: nums = [1, 2, 2, 1, 1], k = 2
// prefixSum: 0 -> 1 -> 3 -> 5 -> 6 -> 7
// At index 1 (val 2): prefix=3, need 1, have 0 (no match)
// At index 2 (val 2): prefix=5, need 3, have 1 (match), count=1
// At index 3 (val 1): prefix=6, need 4, have 0 (no match)
// At index 4 (val 1): prefix=7, need 5, have 1 (match), count=2
// But answer is 3? Let me recalculate...
// Actually at index 1: [2] sums to 2 ✓
// At index 2: [2] sums to 2 ✓
// At index 3,4: [1,1] sums to 2 ✓
// Time: O(n), Space: O(n)

Key insight: - Build prefix sums as you go - For each prefix, ask: "How many previous prefixes, when subtracted from current, give k?" - Use hash map to track frequency of each prefix sum

Complete Solution Files

See the companion files for full, runnable implementations: - src/arrays-strings.js — All array/string problems with test cases - src/hash-tables.js — Hash table implementation + all hash problems

Run them to verify all solutions work and edge cases are handled.

Interview Tips

Restate the problem: Confirm your understanding before coding
Discuss complexity: Explain time and space before implementing
Start simple, optimize: Brute force first, then optimize with patterns
Test with examples: Walk through your code with the examples
Handle edge cases: Empty input, single element, duplicates, etc.
Explain trade-offs: "This is O(n) time but O(n) space. Alternative is O(n log n) time, O(1) space."
Use correct data structures: Map > Object, Set for membership, arrays for order
Avoid common mistakes:
- String concatenation in loops (use array.join())
- shift() and unshift() are O(n)
- Off-by-one errors in two pointers
- Forgetting edge cases (empty, single element)

Final Checklist Before Interview

Understand why two pointers works (maintaining invariant)
Know the sliding window template (both fixed and variable)
Binary search template and when to use each variant
When to use Map vs Object
Prefix sum + hash map pattern
Frequency counting pattern
Can explain hash table collisions
Can code all patterns without IDE autocomplete
Test code in your head before writing
Can explain space-time tradeoffs