Arrays & Hashing

Step 1 Understand it

Remember it by

Seen it before? Ask the hash map — one step, not a second loop.

Watch it happen

The idea

A hash map (dict) or hash set answers 'have I seen this?' or 'where is it?' in one step. Instead of a nested loop that compares every pair, you walk the array once and remember what you've seen.

Picture it

flowchart LR
  X["next item x"] --> Q{"is what x needs<br/>already in the map?"}
  Q -->|"yes"| A["answer found ✓"]
  Q -->|"no"| S["store x in the map"] --> X

Analogy

A cloakroom. You hand over your coat and get ticket 47. Later, ticket 47 takes the attendant straight to your coat — no searching every hook.

Where the analogy breaks

A real cloakroom can run out of hooks. A hash map just grows, but it costs memory: you trade O(n) extra space for speed.

Step 2 Recognise it

Words that signal it

• 'Find a pair / two numbers that…' in an unsorted array
• 'Duplicate', 'seen before', 'unique', 'missing'
• 'Count how many times' or 'most frequent'
• 'Group things that are the same in some way' (anagrams)
• You catch yourself writing a nested loop to look something up

Don't confuse it with

• Two Pointers: If the array is sorted (or you may sort it) and they want O(1) extra space, walk two pointers instead of storing a map.
• Sorting: If you need the items in order, or the k-th position, sort. If you only need 'does it exist / how many', hash it.

Gut check

Am I looking something up again and again? → put it in a hash map.

How to recognise it in an interview

The prompt mentions 'pairs', 'duplicates', or 'frequency/counting'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def solve(nums):
    seen = {}                      # value -> what you need to remember (index, count…)
    for i, x in enumerate(nums):
        need = ...                 # what x is looking for (e.g. target - x)
        if need in seen:           # O(1) lookup instead of a second loop
            return ...             # found the answer
        seen[x] = i                # remember x AFTER checking, so x can't pair with itself
    return ...                     # nothing found

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

Common mistakes

• Storing the item before checking for its pair, so an item pairs with itself (Two Sum with 3 + 3 = 6 on [3]).
• Using a list for 'in' checks: x in list is O(n), x in set is O(1).
• Forgetting a dict key must be hashable: use a tuple, not a list, as a key (Group Anagrams).
• Forgetting that Hash Maps use more memory (Space Complexity becomes O(N)).

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for n in s:
        if n - 1 not in s:             # n starts a sequence
            length = 1
            while n + length in s:
                length += 1
            best = max(best, length)
    return best

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

1. Mark "Contains Duplicate" as solved Contains Duplicate Easy

   Return true if any value appears at least twice in an array.

   Show answer

   Technique: Hash set

   The clue: 'Appears twice' = 'have I seen this before?'

   The trick: Add each number to a set; if it's already there, return true.

2. Mark "Valid Anagram" as solved Valid Anagram Easy

   Decide whether two strings use exactly the same letters the same number of times.

   Show answer

   Technique: Counting with a hash map

   The clue: 'Same letters, same counts' = frequency counting.

   The trick: Count letters in both strings and compare the counts (or one counter: +1 for s, −1 for t).

3. Mark "Two Sum" as solved Two Sum Easy

   Return the indexes of the two numbers in an unsorted array that add up to a target.

   Show answer

   Technique: Hash map (complement lookup)

   The clue: A pair that sums to a target, unsorted, and you need the original indexes.

   The trick: For each x, look up target − x in a map of values already seen.

Medium

1. Mark "Group Anagrams" as solved Group Anagrams Medium

   Group a list of words so that words made of the same letters end up together.

   Show answer

   Technique: Hash map with a signature key

   The clue: 'Group things that are the same in some way' = one key per group.

   The trick: Key each word by its sorted letters (or a 26-count tuple); words with the same key go in the same list.

2. Mark "Top K Frequent Elements" as solved Top K Frequent Elements Medium

   Return the k numbers that appear most often.

   Show answer

   Technique: Counting + bucket sort (or heap)

   The clue: 'K most frequent' = count, then pick the top k.

   The trick: Count with a map, then put numbers into buckets indexed by count and read from the highest bucket: O(n).

3. Mark "Encode and Decode Strings" as solved Encode and Decode Strings Medium

   Turn a list of strings into one string and back again, even if the strings contain any characters.

   Show answer

   Technique: Length-prefix encoding

   The clue: Any character can appear, so you can't rely on a separator alone.

   The trick: Write each string as length + '#' + string; when decoding, read the number up to '#', then take exactly that many characters.

4. Mark "Product of Array Except Self" as solved Product of Array Except Self Medium

   For every index, return the product of all the other numbers, without using division.

   Show answer

   Technique: Prefix and suffix products

   The clue: 'Everything except me' without division = everything left of me × everything right of me.

   The trick: One pass left-to-right stores the product before each index; a second pass right-to-left multiplies in the product after it.

5. Mark "Valid Sudoku" as solved Valid Sudoku Medium

   Check whether a partly filled 9 × 9 Sudoku board breaks any rule so far.

   Show answer

   Technique: Hash sets per row, column and box

   The clue: 'No repeats in each row, column and 3 × 3 box' = seen-before checks in three groups.

   The trick: Keep a set for every row, column and box; the box index is (r // 3, c // 3).

6. Mark "Longest Consecutive Sequence" as solved Longest Consecutive Sequence Medium

   Find the length of the longest run of consecutive integers (in any order) in O(n).

   Show answer

   Technique: Hash set, start only at sequence starts

   The clue: O(n) required, and order in the array doesn't matter.

   The trick: Put all numbers in a set; only count upwards from n when n − 1 is missing.

What to say in the interview

'I can immediately optimize the O(N^2) brute force solution to O(N) by trading space for time using a HashMap.'

Follow-up prep

Be ready to explain how Hash Collisions work.