287. Find the Duplicate Number

Problem

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:

• You must not modify the array (assume the array is read only).
• You must use only constant, O(1) extra space.
• Your runtime complexity should be less than O(n^2).
• There is only one duplicate number in the array, but it could be repeated more than once.

Problem Summary

Given n + 1 numbers, each of which takes a value from 1 to n, and the same number may appear multiple times. Find the duplicate number among these numbers. The time complexity should preferably be lower than O(n^2), and the space complexity should be O(1).

Solution Approach

• A clever idea for this problem is to imagine these numbers as nodes in a linked list, where the number in the array represents the array index of the next node. Finding the duplicate number is equivalent to finding the point where the linked list forms a cycle. Since the problem guarantees that there must be a duplicate number, a cycle must exist. So use the fast and slow pointer method: the fast pointer moves 2 steps at a time, and the slow pointer moves 1 step at a time. After they meet, let the fast pointer start from the beginning and move one step at a time; when they meet again, that is the entry point of the cycle, which is also where the duplicate number is located.
• There are multiple ways to solve this problem. It can be solved with fast and slow pointers. It can also be solved with binary search: (Thanks to @imageslr for pointing out an error in this solution):
  1. Suppose there are n+1 numbers, then the possible duplicate number lies in the interval [1, n]. Denote the minimum, maximum, and middle values of this interval as low, high, and mid
  2. Traverse the entire array and count the number of integers less than or equal to mid, which is at most mid
  3. If it exceeds mid, it means the duplicate number exists in the interval [low,mid] (closed interval); otherwise, the duplicate number exists in the interval (mid, high] (left-open, right-closed)
  4. Narrow the interval and continue repeating steps 2 and 3 until the interval becomes a single integer, i.e., low == high
  5. The integer low is the duplicate number to find
• Another approach is to sort the array first. According to the property that indices increase starting from 0, the difference between the number in the array and its index should become larger and larger. If the same number appears, the index increases, and the difference should be smaller than that of the previous number. When this happens, it means the duplicate number has been found.

Code

package leetcode

import "sort"

// Solution 1: Fast and slow pointers
func findDuplicate(nums []int) int {
	slow := nums[0]
	fast := nums[nums[0]]
	for fast != slow {
		slow = nums[slow]
		fast = nums[nums[fast]]
	}
	walker := 0
	for walker != slow {
		walker = nums[walker]
		slow = nums[slow]
	}
	return walker
}

// Solution 2: Binary search
func findDuplicate1(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid, count := low+(high-low)>>1, 0
		for _, num := range nums {
			if num <= mid {
				count++
			}
		}
		if count > mid {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

// Solution 3
func findDuplicate2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	diff := -1
	for i := 0; i < len(nums); i++ {
		if nums[i]-i-1 >= diff {
			diff = nums[i] - i - 1
		} else {
			return nums[i]
		}
	}
	return 0
}