mediumArraysPattern: Cyclic Sort / Index Hashing
Duplicate Element Identification Solution
Problem Statement
You are given an array of integers `arr` containing elements from 1 to `n`, where `n` is the length of the array. Identify all elements that appear exactly twice in the array and return them in a list.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= n
Time: O(N) Space: O(1)
Iterate array. For each num, take absolute value as index. If value at that index is negative, num is a duplicate. Else, negate the value at that index. Time O(N), Space O(1).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.