Arrays & Hashing

Why This Pattern Matters

The core insight: trading space for time. Almost every O(n^2) brute force involving "find something in the array" can be reduced to O(n) by pre-storing values in a HashMap.

Core Concepts

Array Internals

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
block-beta
    columns 8
    block:header:8
        A["Array: int[] nums = {4, 2, 7, 1, 9}"]
    end
    space:8
    I0["idx 0"] I1["idx 1"] I2["idx 2"] I3["idx 3"] I4["idx 4"] space space space
    V0["4"] V1["2"] V2["7"] V3["1"] V4["9"] space space space
    block:mem:8
        M["Contiguous memory: base_addr + (index × 4 bytes) = O(1) access"]
    end

Key properties:

• Contiguous memory — elements stored sequentially, enabling O(1) random access via pointer arithmetic
• Fixed size (in Java, int[]) — once allocated, cannot grow. Use ArrayList for dynamic sizing (amortized O(1) append via doubling)
• Cache-friendly — sequential access patterns are fast because the CPU prefetcher loads adjacent memory into L1 cache

HashMap Internals (Java)

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    subgraph HashMap["HashMap<K, V> — Java 8+"]
        direction TB
        PUT["put(key, value)"] --> HASH["hash = key.hashCode() ^ (hash >>> 16)"]
        HASH --> BUCKET["index = hash & (capacity - 1)"]
        BUCKET --> CHECK{Bucket empty?}
        CHECK -->|Yes| INSERT["Store as Node"]
        CHECK -->|No| CHAIN{Linked list length?}
        CHAIN -->|"< 8 nodes"| LINKED["Append to linked list — O(n) worst"]
        CHAIN -->|">= 8 nodes"| TREE["Treeify to Red-Black Tree — O(log n)"]
    end

    style HashMap fill:#f8f9fa,stroke:#333
    style TREE fill:#FEE2E2,stroke:#DC2626
    style INSERT fill:#DCFCE7,stroke:#16A34A

HashSet for Dedup

HashSet<T> is internally just a HashMap<T, Object> where all values are a dummy constant (PRESENT). Use it when you only care about existence, not key-value mapping.

// O(n) dedup check — "does this element already exist?"
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (!seen.add(num)) {
        // duplicate found
    }
}

Prefix Sum

The prefix sum converts any "sum of subarray [i, j]" query from O(n) to O(1) after an O(n) precomputation.

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Original["nums[]"]
        A0["2"] --> A1["4"] --> A2["1"] --> A3["3"] --> A4["5"]
    end

    subgraph Prefix["prefix[]"]
        P0["0"] --> P1["2"] --> P2["6"] --> P3["7"] --> P4["10"] --> P5["15"]
    end

    subgraph Query["Sum of nums[1..3] = prefix[4] - prefix[1] = 10 - 2 = 8"]
        Q["sum(i, j) = prefix[j+1] - prefix[i]"]
    end

    Original --> Prefix --> Query

    style Query fill:#DBEAFE,stroke:#2563EB

Formula: sum(i, j) = prefix[j + 1] - prefix[i] where prefix[0] = 0 and prefix[k] = prefix[k-1] + nums[k-1].

Subarray vs Subsequence vs Subset

Pattern Recognition

Reusable Java Templates

/**
 * Pattern: Count occurrences of each element.
 * Use when: top-K, majority element, anagram checks.
 */
public Map<Integer, Integer> frequencyCount(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.merge(num, 1, Integer::sum);
    }
    return freq;
}

// Alternative with getOrDefault:
// freq.put(num, freq.getOrDefault(num, 0) + 1);

/**
 * Pattern: Store value->index in first pass, query in second.
 * Use when: finding pairs, checking complements.
 * Optimization: single-pass variant checks BEFORE inserting.
 */
public int[] twoPassLookup(int[] nums, int target) {
    Map<Integer, Integer> valToIndex = new HashMap<>();

    // Single-pass variant (preferred for Two Sum):
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (valToIndex.containsKey(complement)) {
            return new int[]{valToIndex.get(complement), i};
        }
        valToIndex.put(nums[i], i);
    }
    return new int[]{};
}

/**
 * Pattern: Precompute cumulative sums for O(1) range queries.
 * Use when: subarray sum problems, range sum queries.
 */
public int[] buildPrefixSum(int[] nums) {
    int[] prefix = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
    // rangeSum(i, j) = prefix[j + 1] - prefix[i]
}

/**
 * Prefix sum + HashMap: count subarrays with sum == k
 */
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1); // empty prefix
    int sum = 0, count = 0;

    for (int num : nums) {
        sum += num;
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

/**
 * Pattern: Group elements by a computed canonical key.
 * Use when: grouping anagrams, categorizing strings.
 */
public List<List<String>> groupByKey(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();

    for (String s : strs) {
        // Compute canonical key (sorted chars for anagrams)
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

// Alternative key: frequency array as string
// "eat" -> "1a0b0c0d1e..." (avoids O(k log k) sort)
private String charCountKey(String s) {
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    return Arrays.toString(count);
}

Solved Walkthroughs

1. Two Sum (LC #1)

Problem: Given array nums and integer target, return indices of two numbers that sum to target. Exactly one solution exists.

Thought Process

Dead end — Brute Force O(n^2):

// Check every pair — works but too slow for n = 10^4+
for (int i = 0; i < nums.length; i++)
    for (int j = i + 1; j < nums.length; j++)
        if (nums[i] + nums[j] == target)
            return new int[]{i, j};

The HashMap Insight: For each element nums[i], I need target - nums[i] to exist somewhere else. Instead of scanning the whole array, store what I've already seen in a HashMap. Each lookup is O(1).

Solution

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // value -> index

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(nums[i], i);
    }
    throw new IllegalArgumentException("No solution");
}

Complexity: Time O(n), Space O(n)

Common mistake: Putting the element in the map BEFORE checking the complement. This causes the element to match with itself (e.g., target=6, nums=[3,3] would incorrectly return index 0 twice).

2. Subarray Sum Equals K (LC #560)

Problem: Given array nums and integer k, return the total number of contiguous subarrays whose sum equals k.

Why This Is Tricky

• Negative numbers exist, so sliding window does NOT work (window sum is not monotonic)
• Brute force: try all O(n^2) subarrays, compute each sum in O(n) = O(n^3). Or precompute prefix sums for O(n^2). Neither is good enough.

The Insight: Prefix Sum + HashMap

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Key Insight
        direction TB
        A["If prefix[j] - prefix[i] == k"] --> B["Then subarray (i, j] sums to k"]
        B --> C["For each j, count how many i's have prefix[i] == prefix[j] - k"]
        C --> D["Store prefix sum frequencies in a HashMap"]
    end
    style A fill:#DCFCE7,stroke:#16A34A
    style D fill:#DBEAFE,stroke:#2563EB

Visual example: nums = [1, 2, 3, -1, 1], k = 3

Answer: 3 subarrays — [1,2], [3], [2,3,-1,1]

Solution

public int subarraySum(int[] nums, int k) {
    // Key: prefix sum value. Value: how many times we've seen it.
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1); // empty subarray has sum 0

    int runningSum = 0;
    int count = 0;

    for (int num : nums) {
        runningSum += num;
        // How many previous prefixes give us exactly k?
        count += prefixCount.getOrDefault(runningSum - k, 0);
        prefixCount.merge(runningSum, 1, Integer::sum);
    }
    return count;
}

Complexity: Time O(n), Space O(n)

Why prefixCount.put(0, 1)? Without it, you'd miss subarrays starting at index 0. If runningSum == k at some point, you need to count that as one valid subarray — which requires a "prefix sum of 0" to exist.

3. Group Anagrams (LC #49)

Problem: Given an array of strings, group anagrams together. Return the groups in any order.

Example: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]

The Key Insight

Two strings are anagrams if and only if they have the same characters in the same frequencies. So we need a canonical form — a "fingerprint" — that is identical for all anagrams.

Option A: Sort each string. "eat" → "aet", "tea" → "aet". Same key = same group. Cost: O(k log k) per string where k = string length.

Option B: Character frequency count as key. "eat" → [1,0,0,0,1,0,...,1,0,0]. Cost: O(k) per string, but key is a 26-element array (constant overhead for short strings).

Solution (Sorted Key — Cleaner for Interviews)

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();

    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

Complexity: Time O(n * k log k) where n = number of strings, k = max string length. Space O(n * k).

Follow-up the interviewer might ask: "Can you do it without sorting?" — use the frequency count key:

private String buildKey(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    // "1#0#0#...#1#0#1" — use delimiter to avoid collisions
    StringBuilder sb = new StringBuilder();
    for (int f : freq) sb.append(f).append('#');
    return sb.toString();
}

This gives O(n * k) time but in practice the constant factor makes it roughly equal for typical interview inputs.

Common Mistakes

Practice Problems

Interview Tips

Was this helpful?

Yes Needs more

Thanks for your feedback!

Discussion

Markdown supported Post

Sign in to join the discussion Sign In

Loading comments...