Arrays & Hashing

Trade memory for speed: remember what you have seen in a hash map or set.

Reach for it when

Find a pair / duplicate / complement in one pass
Group items by a computed key (anagrams, frequencies)
Count occurrences, or answer membership questions in O(1)

Core idea

Most brute-force array solutions re-scan the input for every element. A hash map turns that inner scan into an O(1) lookup: store each value (or a derived key such as a sorted string or a running sum) as you go, and ask the map whether the partner you need has already appeared.

Template · O(n) time, O(n) space

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:     # partner already seen?
            return [seen[target - x], i]
        seen[x] = i                # record AFTER checking (no self-pairing)
    return []

vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;              // value -> index
    for (int i = 0; i < (int)nums.size(); i++) {
        auto it = seen.find(target - nums[i]); // partner already seen?
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;                     // record AFTER checking
    }
    return {};
}

Common pitfalls

Inserting before checking lets an element pair with itself
Lists are unhashable: use a tuple (or a sorted string) as the key
Prefix-sum counting needs the base case count[0] = 1

Practice · 0 / 19 done

Contains DuplicateEasy
Majority ElementEasy
Maximum Product of Three NumbersEasy
Two SumEasy
Valid AnagramEasy
Analyze User Website Visit PatternMedium
Design Hit CounterMedium
Encode and Decode StringsMedium
Find First and Last Position of Element in Sorted ArrayMedium
Group AnagramsMedium
Insert Delete GetRandom O(1)Medium
Invalid TransactionsMedium
Longest Consecutive SequenceMedium
Product of Array Except SelfMedium
Rotate ArrayMedium
Snapshot ArrayMedium
Subarray Sum Equals KMedium
Top K Frequent ElementsMedium
Valid SudokuMedium