Find All Duplicates in an Array

Overview

An array is given in which all elements are in the range [1, n] where n is the length of the array. The objective is to find all duplicates in that given array

Examples

Input: [1, 2, 3, 2, 4, 3]
Output: [2, 3]

The idea here is to take advantage of the fact that numbers are in the range [1, n]. For every element in the array, increase the value at its index by n. So

• For getting a value at an index we value%n

• In the end, if the value at any index is greater than 2*n then it is duplicated.

Program

Here is the program for the same.

package main

import "fmt"

func findDuplicates(nums []int) []int {
	lenNums := len(nums)

	for i := 0; i < lenNums; i++ {
		index := (nums[i] - 1) % lenNums

		nums[index] = lenNums + nums[index]
	}

	k := 0

	for i := 0; i < lenNums; i++ {
		if nums[i] > 2*lenNums {
			nums[k] = i + 1
			k++
		}
	}

	return nums[0:k]

}

func main() {
	output := findDuplicates([]int{1, 2, 3, 2, 4, 3})
	fmt.Println(output)
}

Output

[2 3]