Skip to content

Hash

Table of Contents

1. Two Sum

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Hash Map: O(n) time, O(n) space.
        Store seen values so each number can find its complement in one pass.
        """
        hashmap = {}  # val: idx

        for idx, val in enumerate(nums):
            comp = target - val
            if comp in hashmap:
                return [hashmap[comp], idx]

            hashmap[val] = idx

        return []


def test_two_sum():
    s = Solution()
    assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
    assert s.twoSum([3, 2, 4], 6) == [1, 2]
    assert s.twoSum([3, 3], 6) == [0, 1]
    assert s.twoSum([1, 2, 3, 4, 5], 10) == []
    assert s.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]

#include <cassert>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;

        for (size_t i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (map.find(diff) != map.end()) {
                return {map[diff], (int)i};
            }
            map[nums[i]] = (int)i;
        }
        return {-1, -1};
    }
};

int main() {
    Solution solution;
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = solution.twoSum(nums, target);
    assert((result == vector<int>{0, 1}));
    return 0;
}

49. Group Anagrams

from collections import defaultdict
from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """Counting Hash Map: O(n * k) time, O(n) space.
        Words with the same 26-letter frequency tuple are anagrams.
        """
        groups = defaultdict(list)

        for word in strs:
            counts = [0] * 26
            for ch in word:
                counts[ord(ch) - ord("a")] += 1
            groups[tuple(counts)].append(word)

        return list(groups.values())


def test_group_anagrams():
    def normalized(groups):
        return sorted(sorted(group) for group in groups)

    s = Solution()
    result = s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    assert normalized(result) == [
        ["ate", "eat", "tea"],
        ["bat"],
        ["nat", "tan"],
    ]
    assert normalized(s.groupAnagrams([""])) == [[""]]
    assert normalized(s.groupAnagrams(["a"])) == [["a"]]

#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;

        for (string& s : strs) {
            string sorted = s;
            ranges::sort(sorted);
            map[sorted].push_back(s);
        }

        vector<vector<string>> res;

        for (auto& kv : map) {
            res.push_back(kv.second);
        }
        return res;
    }
};

int main() {
    Solution solution;
    vector<string> strs = {"eat", "tea", "tan"};
    vector<vector<string>> res = solution.groupAnagrams(strs);
    assert((res == vector<vector<string>>{{"eat", "tea"}, {"tan"}} ||
            res == vector<vector<string>>{{"tan"}, {"eat", "tea"}}));

    return 0;
}

128. Longest Consecutive Sequence

from typing import List


# Set
def longestConsecutiveSet(nums: List[int]) -> int:
    num_set = set(nums)  # O(n)
    longest = 0

    for n in nums:
        if (n - 1) not in num_set:  # left boundary
            length = 1

            while (n + length) in num_set:
                length += 1

            longest = max(longest, length)

    return longest


# Union Find
def longestConsecutiveUF(nums: List[int]) -> int:
    if not nums:
        return 0

    par = {num: num for num in nums}
    rank = {num: 1 for num in nums}

    def find(num):
        p = par[num]
        while p != par[p]:
            p = par[p]
        return p

    def union(num1, num2):
        p1, p2 = find(num1), find(num2)
        if p1 == p2:
            return

        if rank[p1] < rank[p2]:
            par[p1] = p2
            rank[p2] += rank[p1]
        else:
            par[p2] = p1
            rank[p1] += rank[p2]

    for num in nums:
        if num - 1 in par:
            union(num, num - 1)

    return max(rank.values())


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |  Set       |  O(N)  |  O(N)   |
# | Union Find |  O(N)  |  O(N)   |
# |------------|--------|---------|


nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutiveSet(nums))  # 4
print(longestConsecutiveUF(nums))  # 4