Arrays & Hashing

Back to DSA & Algorithms/00 - Roadmap Overview

What is an Array?

An array is a contiguous block of memory where elements are stored side by side. Think of it like a row of numbered lockers — you know exactly which locker to open if you know the number.

Index:   0    1    2    3    4
Value: [ 10 | 20 | 30 | 40 | 50 ]
         ^--- each takes same space in memory

Why it matters

Access by index is O(1): Jump directly to array[3] — no scanning needed
Insert/Delete in the middle is O(n): Every element after the insertion point must shift
Appending at the end is amortized O(1) in dynamic arrays (Java ArrayList)
Cache-friendly: Contiguous memory = CPU cache loves it = fast iteration

Things to Know

Operation	Time	Why
Access `arr[i]`	O(1)	Direct address calculation: `base + i * size`
Search (unsorted)	O(n)	Must check every element
Search (sorted)	O(log n)	Binary search
Insert at end	O(1) amortized	Occasionally needs resize (doubles capacity)
Insert at middle	O(n)	Shift everything right
Delete at middle	O(n)	Shift everything left

Java-Specific Tips

java
// Array vs ArrayList
// Plain arrays have fixed size; ArrayList is a dynamic array (auto-resizes)
int[] fixedArray = new int[5];            // fixed size, primitives
ArrayList<Integer> dynamicList = new ArrayList<>();  // dynamic, boxed

// 2D array initialization — each row is independent by default (no aliasing issue)
int[][] grid = new int[3][3];

// Arrays utility methods (java.util.Arrays)
Arrays.sort(fixedArray);                  // sort in place
Arrays.fill(fixedArray, 0);              // fill all slots
Arrays.copyOfRange(fixedArray, 1, 3);    // subarray copy (O(n) time and space)
Arrays.equals(arr1, arr2);              // element-wise comparison
Arrays.toString(fixedArray);            // "[0, 0, 0, 0, 0]" for printing

// ArrayList common operations
dynamicList.add(10);                     // append O(1) amortized
dynamicList.get(0);                      // access by index O(1)
dynamicList.set(0, 20);                  // replace at index O(1)
dynamicList.remove(0);                   // remove by index O(n)
dynamicList.size();                      // length
dynamicList.contains(10);               // O(n) linear search

// Autoboxing: Java auto-converts between int <-> Integer, but beware:
// == on Integer compares references, not values (for values > 127)!
Integer a = 200;
Integer b = 200;
a == b;        // FALSE (reference comparison)
a.equals(b);   // TRUE (value comparison)

// Convert between array and ArrayList
Integer[] boxedArr = dynamicList.toArray(new Integer[0]);
List<Integer> fromArr = Arrays.asList(boxedArr);  // fixed-size wrapper
List<Integer> mutable = new ArrayList<>(Arrays.asList(boxedArr));  // truly mutable

What is a Hash Map (Dictionary)?

A hash map stores key-value pairs. It uses a hash function to convert the key into an array index. Think of it like a phone book — give me a name, I'll find the number instantly.

How Hashing Works (Simplified)

key "apple" → hash function → integer 42 → index 42 % array_size → store at index 7

Step 1: Take the key ("apple")
Step 2: Run it through a hash function → big number (e.g., 2314539)
Step 3: Modulo by table size → 2314539 % 16 = 7
Step 4: Store the value at index 7

Collision Handling

Two keys can map to the same index. Two common solutions:

Chaining: Each bucket holds a linked list. Multiple entries share the same index.
Open addressing: If the slot is taken, probe the next slot (linear probing).

Java's HashMap uses chaining (linked lists that convert to red-black trees at high load). You don't need to implement this — just know it exists.

Time Complexity

Operation	Average	Worst (many collisions)
Get	O(1)	O(n)
Put	O(1)	O(n)
Delete	O(1)	O(n)
Contains	O(1)	O(n)

Worst case is extremely rare with good hash functions. Treat all operations as O(1).

Hash Set vs Hash Map

java
// HashSet: Only keys, no values. "Is this element in the set?"
Set<Integer> seen = new HashSet<>();
seen.add(5);
seen.contains(5);  // true, O(1)

// HashMap: Key-value pairs. "What's the value for this key?"
Map<Character, Integer> freq = new HashMap<>();
freq.put('a', 3);
freq.getOrDefault('b', 0);  // 0 (default if key missing)

Java-Specific Tips

java
import java.util.*;

// getOrDefault: safely read missing keys
Map<String, List<String>> graph = new HashMap<>();
graph.computeIfAbsent("a", k -> new ArrayList<>()).add("b");
// No NullPointerException even if "a" didn't exist — creates the list automatically

// Counting frequency in one pass
int[] nums = {1, 1, 2, 3, 3, 3};
Map<Integer, Integer> freqMap = new HashMap<>();
for (int n : nums) {
    freqMap.merge(n, 1, Integer::sum);  // increment count
}
// {1=2, 2=1, 3=3}

// Find the most common element
Map.Entry<Integer, Integer> mostCommon = Collections.max(
    freqMap.entrySet(), Map.Entry.comparingByValue()
);
// 3=3

// Iterating over a HashMap
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
    int key = entry.getKey();
    int value = entry.getValue();
}

// GOTCHA: Don't modify map size during iteration with for-each
// This will throw ConcurrentModificationException:
// for (int k : map.keySet()) {
//     if (condition) map.remove(k);
// }
// Instead: use an Iterator explicitly
Iterator<Map.Entry<Integer, Integer>> it = freqMap.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<Integer, Integer> entry = it.next();
    if (entry.getValue() < 2) it.remove();
}

// GOTCHA: HashMap keys must implement hashCode() and equals()
// Primitives arrays (int[]) do NOT work as keys — use List<Integer> or a String key

Pattern 1: Frequency Counting

What it is

Count how many times each element appears. Use a hash map where keys are elements and values are counts.

When to use it

"Are these two things made of the same elements?" (anagrams)
"Find duplicates"
"Find the most/least frequent element"
"Group elements by some property"

The Mental Model

Imagine you have a bag of colored marbles. You dump them on a table and sort them into piles by color. The "pile" is your frequency map.

Input:  [🔴, 🔵, 🔴, 🟢, 🔵, 🔴]
Map:    {🔴: 3, 🔵: 2, 🟢: 1}

Step-by-Step

java
// APPROACH 1: Manual counting
public Map<Integer, Integer> countFreq(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) {
        freq.put(n, freq.getOrDefault(n, 0) + 1);  // getOrDefault avoids null
    }
    return freq;
}

// APPROACH 2: Using merge (does the same thing more concisely)
public Map<Integer, Integer> countFreq2(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) {
        freq.merge(n, 1, Integer::sum);
    }
    return freq;
}

Example: Valid Anagram

Problem: Are two strings anagrams? (same letters, same counts, different order)

java
public boolean isAnagram(String s, String t) {
    // If lengths differ, can't be anagrams
    if (s.length() != t.length()) return false;

    // Count characters in both strings and compare
    int[] count = new int[26];  // fixed array for lowercase letters
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

// "listen" → {l:1, i:1, s:1, t:1, e:1, n:1}
// "silent" → {s:1, i:1, l:1, e:1, n:1, t:1}
// Same maps! → true

Example: Group Anagrams

Problem: Group words that are anagrams of each other.

Key insight: Two anagrams, when sorted, produce the same string. "eat" → "aet", "tea" → "aet". Use the sorted string as the map key.

java
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);  // "eat" → "aet"
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

// Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
// Groups: {"aet": ["eat","tea","ate"], "ant": ["tan","nat"], "abt": ["bat"]}

Problems

Pattern 2: Complement Lookup (Two Sum Pattern)

What it is

Instead of checking every pair (O(n²)), use a map to instantly check if the "other half" of what you need exists.

When to use it

"Find two elements that sum/multiply/XOR to a target"
Any time you're about to write two nested loops to find a pair

The Mental Model

You're at a party looking for your dance partner. Instead of asking every person "Are you person X?", you write your name on a board. When person X arrives, they check the board and find you instantly.

The board = the hash map.

Step-by-Step Walkthrough

java
// Problem: Find two numbers that add up to target
// Input: nums = [2, 7, 11, 15], target = 9
// Output: [0, 1]  (because nums[0] + nums[1] = 2 + 7 = 9)

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];  // "What do I need to reach the target?"

        if (seen.containsKey(complement)) {  // "Have I seen my complement before?"
            return new int[]{seen.get(complement), i};
        }

        seen.put(nums[i], i);  // "I haven't found my pair yet, register myself"
    }

    return new int[]{};
}

// Walkthrough:
// i=0, num=2:  complement = 9-2 = 7.  seen={}.      7 not in seen. Add {2:0}
// i=1, num=7:  complement = 9-7 = 2.  seen={2:0}.   2 IS in seen! Return [0, 1]

Why This Works

For each number, we ask: "Is there a number I've already seen that completes the pair?"
If yes → we found the answer
If no → we store this number for future lookups
Each number is visited exactly once → O(n)

The Brute Force (Don't Do This)

java
// O(n²) - checks every pair
public int[] twoSumSlow(int[] nums, int target) {
    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};
            }
        }
    }
    return new int[]{};
}

Problems

1. Two Sum - Easy
128. Longest Consecutive Sequence - Medium
560. Subarray Sum Equals K - Medium

Pattern 3: Prefix Sum

What it is

A running total. prefix[i] = sum of all elements from index 0 to i-1. This lets you compute the sum of ANY subarray in O(1).

When to use it

"Find the sum of elements between index i and j"
"Find a subarray with sum equal to K"
"Product of array except self"
Any time you need range sums repeatedly

The Mental Model

Imagine you're tracking your bank balance over time:

Deposits:    [100, 200, 50, 300, 150]
Balance:  [0, 100, 300, 350, 650, 800]
              ^--- prefix sum array (starts with 0)

"How much did I deposit between day 2 and day 4?"
Balance[5] - Balance[2] = 800 - 300 = 500

That's just prefix[j] - prefix[i] = sum of elements from i to j-1

Step-by-Step

java
// Building a prefix sum array
int[] nums = {1, 2, 3, 4, 5};
int[] prefix = new int[nums.length + 1];  // Start with 0 (sum of nothing)
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// prefix = [0, 1, 3, 6, 10, 15]

// Sum of subarray nums[1..3] = nums[1] + nums[2] + nums[3] = 2 + 3 + 4 = 9
// Using prefix: prefix[4] - prefix[1] = 10 - 1 = 9  ✓

// The formula:
// sum(nums[i..j-1]) = prefix[j] - prefix[i]

Example: Subarray Sum Equals K

Problem: Count subarrays whose sum equals K.

Key insight: If prefix[j] - prefix[i] = K, then the subarray from i to j-1 sums to K. Rearranging: prefix[i] = prefix[j] - K. So for each j, we ask: "How many previous prefix sums equal current_prefix - K?"

This is the complement lookup pattern applied to prefix sums!

java
public int subarraySum(int[] nums, int k) {
    int count = 0;
    int currentSum = 0;
    Map<Integer, Integer> prefixCounts = new HashMap<>();
    prefixCounts.put(0, 1);  // empty prefix (sum=0) occurs once

    for (int num : nums) {
        currentSum += num;
        int complement = currentSum - k;

        // How many previous prefix sums equal the complement?
        count += prefixCounts.getOrDefault(complement, 0);

        // Record this prefix sum
        prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);
    }

    return count;
}

// Walkthrough with nums=[1,1,1], k=2:
// i=0: sum=1, need 1-2=-1, count+=0, record {0:1, 1:1}
// i=1: sum=2, need 2-2=0,  count+=1 (found!), record {0:1, 1:1, 2:1}
// i=2: sum=3, need 3-2=1,  count+=1 (found!), record {0:1, 1:1, 2:1, 3:1}
// Answer: 2 → subarrays [1,1] and [1,1]

Example: Product of Array Except Self

Problem: For each index, return the product of all other elements. No division allowed.

Key insight: result[i] = (product of everything left of i) × (product of everything right of i). Build left products and right products separately.

java
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, 1);

    // Pass 1: Left products
    // result[i] = product of nums[0..i-1]
    int left = 1;
    for (int i = 0; i < n; i++) {
        result[i] = left;
        left *= nums[i];
    }

    // Pass 2: Right products (multiply into result)
    // result[i] *= product of nums[i+1..n-1]
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }

    return result;
}

// nums   = [1,  2,  3,  4]
// left   = [1,  1,  2,  6]   ← product of everything to the left
// right  = [24, 12, 4,  1]   ← product of everything to the right
// result = [24, 12, 8,  6]   ← left × right

Problems

238. Product of Array Except Self - Medium
560. Subarray Sum Equals K - Medium
303. Range Sum Query - Immutable - Easy

Pattern 4: In-Place Hashing (Array as HashMap)

What it is

Use the array indices themselves as hash keys. Place each value v at index v (or v-1). This gives O(1) space instead of using a separate hash map.

When to use it

"Find the missing number in [0, n]"
"Find the first missing positive"
"Find duplicates in [1, n] range"
The values are bounded by the array size

The Mental Model

Imagine 100 students in a class, each with a seat number from 1-100. To find who's missing, just walk through the seats and see which one is empty. You don't need a separate list — the seats ARE your lookup structure.

Step-by-Step

java
// Missing Number: nums contains n numbers from [0, n], one is missing
// Approach 1: Math (Gauss formula)
public int missingNumber(int[] nums) {
    int n = nums.length;
    int expectedSum = n * (n + 1) / 2;  // sum of 0..n
    int actualSum = 0;
    for (int num : nums) actualSum += num;
    return expectedSum - actualSum;
}

// Approach 2: XOR (every number cancels its pair)
public int missingNumberXor(int[] nums) {
    int result = nums.length;
    for (int i = 0; i < nums.length; i++) {
        result ^= i ^ nums[i];
    }
    return result;
}
// Why: XOR of [0,1,2,...,n] XOR [nums] → everything cancels except missing

// First Missing Positive: Find smallest positive integer not in array
public int firstMissingPositive(int[] nums) {
    int n = nums.length;

    // Step 1: Place each number at its "correct" index
    // number 1 goes to index 0, number 2 goes to index 1, etc.
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            // Swap nums[i] to its correct position
            int correct = nums[i] - 1;
            int temp = nums[i];
            nums[i] = nums[correct];
            nums[correct] = temp;
        }
    }

    // Step 2: Find first index where nums[i] != i + 1
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return n + 1;
}

// Walkthrough: nums = [3, 4, -1, 1]
// After placement: [1, -1, 3, 4]
// Index 0: nums[0]=1 ✓
// Index 1: nums[1]=-1 ✗ → missing is 2

Problems

41. First Missing Positive - Hard
268. Missing Number - Easy
448. Find All Numbers Disappeared in an Array - Easy
442. Find All Duplicates in an Array - Medium

Things You MUST Be Aware Of

1. Integer Overflow

java
// Java uses fixed-size integers (int = 32-bit, long = 64-bit)
// sum of two ints CAN overflow!
// Always think: "Can my sum/product exceed 2^31 - 1?"
// Use long when sums or products might overflow int range
long safeSum = (long) a + b;

2. Negative Numbers

java
// Negative numbers can break assumptions
// Example: "subarray sum equals K" — prefix sums can decrease!
// That's why we need a map, not just a pointer approach

3. Duplicates

java
// Always ask: "Can the input have duplicates?"
// If yes, your approach might need adjustment
// HashMap handles this naturally, but HashSet loses duplicates

4. Empty Input

java
// Always handle: what if nums.length == 0?
// What if the string is empty?
// Many people forget this edge case

5. Hash Collision in Custom Objects

java
// If you use custom objects as HashMap keys, you must override:
// hashCode() and equals()
// int[] does NOT work as a key (uses reference identity)
Map<String, String> d = new HashMap<>();
// d.put(new int[]{1,2}, "x");  // Compiles but BROKEN: uses reference as key
// Instead, use a List<Integer> or convert to a String key
d.put(List.of(1, 2).toString(), "x");  // OK: String has proper hashCode/equals

6. Sorting Changes Indices

java
// If the problem asks for original indices, don't sort!
// Use a hash map (like Two Sum) instead
// If it asks for values only, sorting might help

Complexity Summary

Pattern	Time	Space	When to Use
Frequency Count	O(n)	O(n)	Count, group, or compare compositions
Complement Lookup	O(n)	O(n)	Find pairs matching a target
Prefix Sum	O(n) build, O(1) query	O(n)	Range sum queries, subarray sums
In-Place Hash	O(n)	O(1)	Missing/duplicate in bounded range

Pattern Recognition Cheat Sheet

"Find if duplicate exists"        → HashSet (add and check)
"Count occurrences"               → HashMap frequency map
"Group by property"               → HashMap with computed key
"Find pair with target sum"       → Complement lookup
"Subarray sum equals K"           → Prefix sum + complement lookup
"Range sum queries"               → Prefix sum array
"Missing/duplicate in [1,n]"     → In-place hashing or math
"Product except self"             → Left and right prefix products