Circling the Garage

Easyhash mapAlso known as Contains Duplicate II

A camera at the entrance of a parking garage reads the plate of every car that drives in and writes it to a log, in order. A driver who finds no free spot leaves by the exit ramp and often comes straight back in to try again.

The manager wants to know if that happened: the same plate coming in twice within a few entries of itself. The same car returning hours later is a normal visit, not circling.

Your task

Write circlingCar(plates, k). Return true if there are two positions i < j with plates[i] === plates[j] and j - i ≤ k. Otherwise return false.

An empty log returns false. With k = 0 no pair can qualify, so the answer is false.

circlingCar(plates: int[], k: int) → bool

Examples

Example 1

Input

plates = [512, 77, 903, 77, 640]
k = 2

Output

true

Why

Plate 77 came in at positions 1 and 3. 3 - 1 = 2, which is within k = 2, so the answer is true.

Example 2

Input

plates = [512, 77, 903, 640, 512]
k = 3

Output

false

Why

Plate 512 came in twice, at positions 0 and 4. 4 - 0 = 4 is more than k = 3, so that was a normal second visit. No other plate repeats. The answer is false.

Example 3

Input

plates = [8, 1, 2, 3, 8, 4, 8]
k = 2

Output

true

Why

Plate 8 came in at 0, 4 and 6. Comparing with its first visit gives gaps of 4 and 6, both too big. But visits 4 and 6 are only 2 apart, so the answer is true.

Constraints

0 ≤ plates.length ≤ 100,000
0 ≤ plates[i] ≤ 1,000,000,000
0 ≤ k ≤ 100,000

Start with brute force

For each entry, compare it with the next k entries and return true on a match.

That costs about n × k comparisons. With 100,000 entries and k = 100,000 it is billions of checks. The waste is that every entry looks forward again over cars the earlier entries already looked at.

Hints

0 of 4 shown

Hint 1
In [3, 9, 3] with k = 2, the 3s are at positions 0 and 2. When you reach position 2, what single fact about plate 3 do you need from the past?
Hint 2
Only the most recent earlier visit of a plate matters. If that visit is too far back, every older visit is even further back.
Hint 3
Keep one number per plate: the position where you last saw it. Which structure gives you that number in one step?
Hint 4
Walk the log with a map from plate to last position. At each position j, if the plate is in the map and j - last ≤ k, return true. Either way, update the map to j. Return false at the end.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

This is the duplicate check from Double-Scanned Tickets with a distance limit. A set is no longer enough, because you need to know where you last saw a plate. So store the position.

Trace [8, 1, 2, 3, 8, 4, 8] with k = 2:

Positions 0 to 3: plates 8, 1, 2, 3 are all new. Map: 8 → 0, 1 → 1, 2 → 2, 3 → 3.
Position 4, plate 8. Last seen at 0, gap 4 > 2. Not circling. Update 8 → 4.
Position 5, plate 4. New. Map gets 4 → 5.
Position 6, plate 8. Last seen at 4, gap 2 ≤ 2. Return true.

The update in step 2 is the important line. If you kept the first position, 8 → 0, the last visit would see a gap of 6 and you would wrongly answer false.

Reference solution

function circlingCar(plates, k) {
  const last = new Map(); // plate -> position of its latest entry
  for (let j = 0; j < plates.length; j++) {
    if (last.has(plates[j]) && j - last.get(plates[j]) <= k) return true;
    last.set(plates[j], j); // this is now the latest visit
  }
  return false;
}

def circling_car(plates, k):
    last = {}  # plate -> position of its latest entry
    for j, plate in enumerate(plates):
        if plate in last and j - last[plate] <= k:
            return True
        last[plate] = j  # this is now the latest visit
    return False

TimeO(n)One pass, and each map lookup or update is O(1) on average.

SpaceO(n)With no repeats the map ends up holding every plate. Keeping only the last k plates in a set would cut this to O(k).

Learn the idea: Hash Tables Arrays Sliding Window

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code