Hash Tables | DSA Prep

Core Concepts

O(1) Time Complexity: Average case time complexity for access, making them perfect for optimizing array problems.
Frequency Counting: Using a map to count occurrences of elements.
Sets: A variation that only stores unique keys without mapping them to values.

graph LR A["Key: 'apple'"] -->|Hash Function| B["Index 2"] C["Key: 'banana'"] -->|Hash Function| D["Index 5"] B -.-> E[("Value: 12")] D -.-> F[("Value: 7")]

Cheatsheet Formulas

Frequency Counter: for val in arr: count[val] = count.get(val, 0) + 1.
Two Sum Pattern: Store {value: index}. Check if target - curr_value exists in map.
Sliding Window with Hash Map: Track character frequencies in the current window to check valid states (e.g., longest substring without repeating characters).

Classic Problem: Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)