FastPrepFind All Duplicates by Swapping

Find All Duplicates by Swapping

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

You are given a mutable integer array nums of length n. Every value is in [0,n-1], and every value appears once or twice.

Rearrange the array only by swapping elements, then return every value that appears twice. List duplicates in the order in which their extra occurrences appear during a final left-to-right scan.

Your algorithm must run in O(n) time and use O(1) auxiliary space excluding the returned array. Do not use arithmetic marking, recursion, helper data structures, or additional function calls from the primary method.

Function

findAllDuplicatesBySwapping(nums: int[]) → int[]

Examples

Example 1

nums = [2,3,1,0,2,3]return = [2,3]

Cyclic swaps place 0 through 3 at their matching indices; the remaining positions hold the extra 2 and 3.

Example 2

nums = [0,1,2,3]return = []

Every value already occupies its own index, so there is no duplicate.

Example 3

nums = [1,1,0]return = [1]

One copy of 1 reaches index 1; the other remains as the extra occurrence.

Constraints

  • 1 <= nums.length <= 200000.
  • 0 <= nums[i] < nums.length.
  • Every value appears once or twice.

More Google problems

See Google hiring insights
public int[] findAllDuplicatesBySwapping(int[] nums) {
    // Write your code here.
}
nums[2,3,1,0,2,3]
expected[2,3]
Checking account…