Hashing | One Hint Away

A hash map does two jobs. See "how many times does it appear?" in a problem: count. See "have I seen this before?": remember. Worked example: LeetCode 1, Two Sum (Easy). Each input has exactly one answer, and you can't use the same element twice.

The idea

A shoe shop customer asks for size 9. You can open every box until you find a 9, or walk straight to the shelf labelled 9. A hash map is labelled shelves for your data: the label is the key, and what sits on the shelf is the value. Asking the map "is it here?" takes one step on average, like walking to the right shelf.

Count: countLetters("banana") gives b → 1, a → 3, n → 2. Already in the map? Add 1 to its count. First time you see it? Set it to 1.
Remember (Two Sum): at each number, ask the map "have I seen the one I need?" (need = target - num). If not, store this number and where it was.

The walk

nums = [3, 8, 4, 6, 1], target = 10 returns [2, 3] (4 + 6).

i	num	need	seen it?	seen after
0	3	7	no	{3:0}
1	8	2	no	{3:0, 8:1}
2	4	6	no	{3:0, 8:1, 4:2}
3	6	4	yes	return [2, 3]

Pseudocode

Pseudocode · any language

function countLetters(word):
    counts = empty map
    for each ch in word:
        if ch in counts:
            counts[ch] = counts[ch] + 1
        else:
            counts[ch] = 1
    return counts

function twoSum(nums, target):
    seen = empty map          // value -> index
    for i from 0 to length(nums) - 1:
        need = target - nums[i]
        if need in seen:
            return [seen[need], i]
        seen[nums[i]] = i
    return none

The trap: store the number before checking and it can pair with itself. For nums = [3, 2, 4], target = 6, "store, then check" saves 3, looks for 3, finds the same 3 and returns [0, 0]. "Check, then store" returns the correct [1, 2].

Code

import java.util.HashMap;
import java.util.Map;

class Solution {
    // O(n) time, O(k) space for k different letters
    public Map<Character, Integer> countLetters(String word) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char ch : word.toCharArray()) {
            if (counts.containsKey(ch)) {
                counts.put(ch, counts.get(ch) + 1);
            } else {
                counts.put(ch, 1);
            }
        }
        return counts;
    }

    // Brute force: O(n^2) time, O(1) space
    public int[] twoSumBrute(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    // Hash map: O(n) time, O(n) space
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();   // value -> index
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            seen.put(nums[i], i);
        }
        return null;
    }
}

class Solution:
    # O(n) time, O(k) space for k different letters
    def countLetters(self, word: str) -> dict:
        counts = {}
        for ch in word:
            if ch in counts:
                counts[ch] = counts[ch] + 1
            else:
                counts[ch] = 1
        return counts

    # Brute force: O(n^2) time, O(1) space
    def twoSumBrute(self, nums: list[int], target: int) -> list[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return None

    # Hash map: O(n) time, O(n) space
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}                      # value -> index
        for i in range(len(nums)):
            need = target - nums[i]
            if need in seen:
                return [seen[need], i]
            seen[nums[i]] = i
        return None

class Solution {
public:
    // O(n) time, O(k) space for k different letters
    unordered_map<char, int> countLetters(const string& word) {
        unordered_map<char, int> counts;
        for (char ch : word) {
            if (counts.count(ch)) {
                counts[ch] = counts[ch] + 1;
            } else {
                counts[ch] = 1;
            }
        }
        return counts;
    }

    // Brute force: O(n^2) time, O(1) space
    vector<int> twoSumBrute(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }

    // Hash map: O(n) time, O(n) space
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;   // value -> index
        for (int i = 0; i < (int)nums.size(); i++) {
            int need = target - nums[i];
            if (seen.count(need)) {
                return {seen[need], i};
            }
            seen[nums[i]] = i;
        }
        return {};
    }
};

// O(n) time, O(k) space for k different letters
function countLetters(word) {
    const counts = new Map();
    for (const ch of word) {
        if (counts.has(ch)) {
            counts.set(ch, counts.get(ch) + 1);
        } else {
            counts.set(ch, 1);
        }
    }
    return counts;
}

// Brute force: O(n^2) time, O(1) space
function twoSumBrute(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return null;
}

// Hash map: O(n) time, O(n) space
function twoSum(nums, target) {
    const seen = new Map();   // value -> index
    for (let i = 0; i < nums.length; i++) {
        const need = target - nums[i];
        if (seen.has(need)) {
            return [seen.get(need), i];
        }
        seen.set(nums[i], i);
    }
    return null;
}

Complexity

Function	Time	Extra space
`countLetters`	O(n)	O(k), k = different letters
`twoSumBrute`	O(n²)	O(1)
`twoSum`	O(n) on average	O(n)

You spend a little memory to save a lot of time.

How it was tested

All four languages return [2, 3] on the example and [1, 2] on the trap input, and count "banana" as b 1, a 3, n 2. All three functions in all four languages were then run on 3,002 inputs (3,000 random words and random arrays that each have exactly one answer, plus the two examples) and matched an independent brute force on every one.