Arrays and Hashing
Have I seen this before?
The first and most useful trade in the course: spend memory to stop rescanning.
The question behind the pattern
A large family of problems reduces to one question asked repeatedly: have I already seen this value? The slow answer is to look back through everything processed so far. The fast answer is to have kept a record as you went.
Take a concrete task: report the first character in a string that has appeared before. Here is the slow version, written out so the waste is visible. For each character it scans everything before it.
Why it works
Where the repeated work is
The inner loop asks a membership question about the region to the left of i. It answers it by walking that region from scratch, every single time. The region only ever grows by one element per step, so almost all of that walking repeats work already done.
Remembering the region in a set answers the same question in constant time.
The fast version keeps a set of everything seen so far. Notice the shape: check, then record.
Gotcha
Check before you add
If you add first and check afterwards, every character looks like a repeat of itself and the function returns on the very first one. It is a one-line mistake with a confusing symptom, because the answer is always the first element.
Tip
What this shape gives you
That loop answers more than one question depending on what you do at the moment of the hit. Return the value and you get the first repeat. Return True and you get a yes-or-no. Return the index and you get a position. Count instead of returning and you get how many repeats there are.
So the interesting decision is never the loop. It is what the problem is actually asking for at the moment you find a member of the set.
Cost
The trade, stated plainly
Time drops from O(n squared) to O(n). Space rises from O(1) to O(n). In interviews this trade is almost always the one you want, and saying it out loud, rather than silently taking it, is part of what is being assessed.
Tip
When not to reach for the set
Sorting and checking neighbors is O(n log n) time and O(1) extra space if you can sort in place. That is the better answer when memory is tight, and the worse one when the input must keep its order or you need the duplicate's original position.
Now go do it
The problem below asks a simpler question than the example above: not which value repeats, just whether any value does. Decide what you want to happen at the moment you find a member of the set, and write it.
Predict the output: check versus add order
This version adds before it checks. Type exactly what it prints.
Contains Duplicate
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.