Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Arrays and hashing

What to remember about the past

Lesson · 10 min read · Arrays and hashing · Have I seen it before?

A single pass with a map of what has gone by. The design question is which fact about each earlier element the map should hold.

One pass, one question per element

All of the problems in this module are built the same way, and once you've seen it a couple of times you'll spot it in questions that don't look as if they're related. We walk along the array once from the left, and at position j we ask the map one question about the elements we've already passed. Only then do we tell it about nums[j] itself. The answer to the whole problem comes out of those n small questions.

One pass with a memory

scan(nums)

  1. memory = empty map or set.
  2. For j from 0 to n − 1: ask memory the question for nums[j]; stop or record if it answers.
  3. Then update memory with nums[j] and j.

So from one problem to the next, there are only two things that change: the question we ask, and what we keep under a key. When I teach this, I get students to say both of them out loud before they write any code. Once they've got those two right, the loop's about five lines long in any language you'd like to use.

Three things a map can hold

Here's how I'd pick what to store. Start from what you need to know about the earlier values, and keep the least that'll tell you it.

You need to knowStoreExample
whether a value occurreda set of valuesany duplicate at all; the longest run of consecutive integers
where it occurredvalue → an indextwo values summing to a target, returning their indices
how close the nearest copy isvalue → its latest index, overwrittena repeat within k positions
how often it occurredvalue → a countthe next module

Make sure you've got the right index. If you keep the first one when the problem needs the latest, you'll find your code passes the small examples you were given and then fails on the hidden tests.

The complement lookup

If you're looking for a pair that adds up to a target, the question we ask at j is about a value we can't see yet. We'd like to know whether target − nums[j] has already gone past. Since the map holds the values we've seen along with their indices, a hit hands us both halves of the answer at once.

A pair summing to 9 in [11, 2, 15, 7].

  1. Step 1 / 5
    nums
    1102115273
    target9map{}

    Empty map. Target 9. For each number, ask whether its partner has already gone past.

  2. Step 2 / 5
    nums
    110i2115273
    need-2map{}

    11 needs -2. Not in the map yet, so record 11 at index 0 and move on.

  3. Step 3 / 5
    nums
    11021i15273
    need7map{11:0}

    2 needs 7. Not in the map yet, so record 2 at index 1 and move on.

  4. Step 4 / 5
    nums
    11021152i73
    need-6map{11:0, 2:1}

    15 needs -6. Not in the map yet, so record 15 at index 2 and move on.

  5. Step 5 / 5
    nums
    1102115273i
    need2map{11:0, 2:1, 15:2}

    7 needs 2, and 2 was seen at index 1. Answer [1, 3].

Overwrite to keep the nearest copy

Now say the problem cares about how far apart two copies are. An earlier copy's only any use to us if it's the most recent one, so when a value comes round again we write over its entry. By the end, the map's holding the one index for that value that could still be close enough to matter.

TimeO(n) expected
SpaceO(n) for the map

If we keep a set of only the last k values, the memory drops to O(k), and what we've written is the fixed sliding window from chapter 3, with a set for its state.

A repeat within k = 2 positions in [1, 2, 3, 1, 2, 3]. All of the values come back three places later, so we find a copy every time we look, and it's always too far away.

  1. Step 1 / 7
    nums
    10j2132132435

    1 has not been seen. Record last[1] = 0.

  2. Step 2 / 7
    nums
    1021j32132435
    last[1]0

    2 has not been seen. Record last[2] = 1.

  3. Step 3 / 7
    nums
    102132j132435
    last[1]0last[2]1

    3 has not been seen. Record last[3] = 2.

  4. Step 4 / 7
    nums
    10i213213j2435
    last[1]0last[2]1last[3]2

    1 was last at 0, 3 back: more than k = 2. Overwrite with 3.

  5. Step 5 / 7
    nums
    1021i321324j35
    last[1]3last[2]1last[3]2

    2 was last at 1, 3 back: more than k = 2. Overwrite with 4.

  6. Step 6 / 7
    nums
    102132i132435j
    last[1]3last[2]4last[3]2

    3 was last at 2, 3 back: more than k = 2. Overwrite with 5.

  7. Step 7 / 7
    nums
    102132132435
    last[1]3last[2]4last[3]5

    No value repeats within 2 positions. Return false.

Problems in this module