Sort the data first so equal or related items sit next to each other, which turns a hard problem into a simple scan.
Used for
sorting costs n log n
2 = 2: duplicate
After sorting [4, 1, 4, 3] you get 1, 3, 4, 4. Which neighbours show the duplicate?
Not quite. Equal numbers are adjacent after sorting, so comparing neighbours finds the pair 4 and 4.
Step 1 of 4
Goal: does the list contain a duplicate? Checking every pair works but is slow. Idea: sort first, so equal numbers end up side by side.
Step 2 of 4
After sorting: 2, 2, 5, 7, 9. Equal numbers are now neighbours.
Step 3 of 4
Now one pass comparing each number with the next: 2 and 2 match. Duplicate found. Sorting often turns a hard search into a simple neighbour check, and makes tricks like two pointers and interval merging possible.
Step 4 of 4
Your turn.
ArraysBubble SortSelection SortInsertion SortShellsortHeap SortCounting SortRadix SortBucket Sort
// Sorting turns "compare every pair" into "compare neighbours".const hasDuplicate = nums => { const s = [...nums].sort((a, b) => a - b); return s.some((v, i) => i > 0 && v === s[i - 1]);};