Has Duplicate

Write a function that takes a slice of integers and returns true if any number appears more than once, false otherwise.

hasDuplicate(nums)

This is a classic problem that demonstrates the power of choosing the right data structure. A naive approach uses nested loops (O(n²)); a better approach uses a set (O(n)).

Examples

hasDuplicate([]int{3, 5, 3})     // → true
hasDuplicate([]int{1, 2, 3, 4})  // → false
hasDuplicate([]int{5, 5})        // → true
hasDuplicate([]int{})            // → false

Walkthrough

Starting with the obvious approach

The first idea most people reach for: compare every element to every other element, and if any two match, you've found a duplicate. For a list of length n, that's roughly n comparisons for each of the n elements — the total work grows with the square of the list size. Double the input, and the work roughly quadruples.

Why the nested loop is wasteful

By the time you're looking at the fifth element, you already know everything about the first four — but a nested loop throws that away and rescans from scratch every time. What you actually want is a fast way to ask "have I already seen this value?" without rescanning.

The key idea: remember what you've seen

This is where a set earns its keep. A set lets you record a value and later check "is this value in the set?" in roughly constant time, no matter how many values are already stored. That turns an expensive rescan into a quick lookup.

Building the one-pass solution

Start with an empty set: "values seen so far."
Walk through the list once. For each number, first check: is it already in the set?
If it is, you've found a duplicate — stop and return true.
If it isn't, add it to the set and move on.
If you finish the list without a match, there are no duplicates — return false.

Why order matters and why this is correct

Checking membership before adding the current value matters: you're always asking "did some earlier element already have this value?" rather than matching an element against itself. Because the set gives near-constant-time lookups and inserts, the total work is proportional to the list length — one pass, one lookup, one possible insert per element. That's O(n) instead of O(n²).

The tradeoff worth naming

This is a classic memory-for-speed trade: the nested-loop version uses no extra memory but is slow (O(n²) time, O(1) space); the set-based version spends memory to remember what it's seen (O(n) space) for dramatically less time (O(n)). Spotting when a bit of extra memory kills redundant rescanning is one of the most useful skills in algorithm design — it shows up again and again in different disguises.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.