Arrays and Hashing
Retrieval: telling these apart
Two problems from this unit, cold, plus the discriminations that decide whether the pattern actually transfers.
You solved these problems days or hours ago with the pattern freshly explained above them. That is the easy condition. The interview condition is meeting a problem with no label attached and having to work out which idea applies.
So this lesson does two things. It asks you to rebuild two problems from scratch without looking at your earlier submissions, and it drills the specific confusions that show up when these patterns arrive with no label on them.
Tip
The confusion this unit sets up
Several problems here ask you to find a partner for each element, and the right structure differs each time. Two-sum wants a map from value to index, because you need to report where. Contains-duplicate wants a bare set, because you only need whether. Group-anagrams wants a map from key to a list, because many things share a key.
Picking the wrong one of those three is the most common way a solved pattern fails to transfer.
Which structure does the job?
You need to return every pair of indices (i, j) with i less than j whose values are equal. Which structure fits best?
Where does a prefix array help?
Select every problem below that a precomputed prefix array makes meaningfully faster.
Two Sum, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Top K Frequent Elements, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.