Arrays and hashing

When to reach for it

• The brute force compares every pair, and each comparison could be answered by looking something up instead.
• The problem talks about duplicates, counts, frequencies or whether a value has been seen before.
• Items need grouping by something they share: the same letters, the same day, the same account.
• You need positions as well as values, so sorting would throw away information you need.
• A question about a range of the array can be rewritten as a question about two running totals.

The core idea

A hash map gives you insertion and lookup in constant time on average. That changes what one pass over an array can do. As you walk the array, you ask a question of everything you have seen so far (is the partner of this number here? how often has this value appeared? which group does this belong to?) and the map answers it immediately instead of a second loop.

Most of the skill is choosing the key. For pairs, the key is the value and the stored item is its index or a count. For grouping, the key is a canonical form: a sorted string, a tuple of letter counts, a calendar date in the user's time zone. For ranges, the key is a prefix sum: a subarray that adds up to k is two prefix sums that differ by exactly k, so you look for prefix - k among the sums you have already seen.

A Python template

from collections import defaultdict

def pair_with_difference(nums, k):
    """True if two different elements differ by exactly k."""
    seen = set()
    for x in nums:
        if x - k in seen or x + k in seen:   # a lookup, not a second loop
            return True
        seen.add(x)                          # add after checking
    return False

def group_by(items, key):
    groups = defaultdict(list)
    for item in items:
        groups[key(item)].append(item)       # the key decides what "same" means
    return list(groups.values())

def longest_subarray_with_sum(nums, k):
    first = {0: -1}                          # prefix sum -> earliest index
    prefix = best = 0
    for i, x in enumerate(nums):
        prefix += x
        if prefix - k in first:              # an earlier prefix leaves exactly k
            best = max(best, i - first[prefix - k])
        first.setdefault(prefix, i)          # keep the earliest for the longest span
    return best

The three functions are the three shapes of the pattern: a membership question answered by a set, grouping by a computed key, and running totals stored by value so a range question becomes a lookup.

Time and space

One pass makes these O(n) time on average, with O(n) extra space for the set or map. Building the key can cost more than the lookup: sorting each word of length m to group anagrams makes the whole job O(n · m log m), while counting its letters makes it O(n · m). Hash operations are constant time on average and can degrade in the worst case, so say "on average" when you state the bound.

Common mistakes

• Adding the current element before checking for its partner, so a value pairs with itself.
• Forgetting the empty prefix ({0: -1} or a count of 1 for sum 0), which misses ranges that start at index 0.
• Using a list as a dictionary key; Python needs something immutable, such as a tuple or a string.
• Overwriting the earliest index of a prefix sum when the question wants the longest range.
• Claiming O(1) memory: the map grows with the input, and the interviewer will ask.

How to explain it out loud

Start with the brute force and its cost in one sentence ("checking every pair is O(n squared)"), then name the trade: "I'll spend O(n) memory on a hash map so each check is a constant-time lookup." Say what the key is and what you store under it before you write the loop. That decision is what the interviewer is listening for, and saying it before you code is what Devana's rubric counts as approach planning.

While you type, narrate the order of operations: "I check for the partner first, then add, so an element can't pair with itself." Finish by tracing a five-element example and naming the edge cases you handled: duplicates, an empty array, negative numbers in a prefix-sum question. Explaining why the order matters, rather than only that it works, is what Devana scores as logic explanation.