Is Find the Duplicate Number easy or hard?

Find the Duplicate Number is rated Medium difficulty. The brute reasoning is straightforward, but recognizing that the array forms a cycle and applying Floyd's algorithm requires deeper algorithmic insight.

Find the Duplicate Number Python/Java solution

Python and Java implementations usually follow Floyd's cycle detection pattern: run a slow and fast pointer until they meet, then reset one pointer to the start and move both step by step to locate the duplicate. The algorithm uses constant space and runs in linear time.

How to solve Find the Duplicate Number in O(n)?

Use Floyd's Tortoise and Hare algorithm. Move a slow pointer by one step and a fast pointer by two steps through indices defined by array values until they meet. Reset one pointer to the start and move both one step at a time; the meeting point identifies the duplicate number.

What is the best approach for Find the Duplicate Number?

Floyd's Tortoise and Hare cycle detection algorithm is the optimal approach. It runs in O(n) time and O(1) space while keeping the array unchanged. The trick is modeling the array as a linked list where each value points to the next index, which naturally forms a cycle at the duplicate.

Is Find the Duplicate Number asked at Google/Amazon/Meta?

Find the Duplicate Number frequently appears in interviews at companies like Google, Amazon, and Meta. It tests understanding of cycle detection, pointer techniques, and reasoning about constraints such as not modifying the input array and using constant extra space.

What data structure is used in Find the Duplicate Number?

The problem uses an array as the input structure, but the optimal solution conceptually treats it like a linked list. Each index points to another index based on its value, allowing cycle detection techniques with two pointers to identify the duplicate.

What is the time complexity of Find the Duplicate Number?

The optimal solution using Floyd's cycle detection runs in O(n) time with O(1) extra space. Another common method uses binary search on the value range, which takes O(n log n) time because each binary search step requires scanning the entire array.

Description Solution Video 17:34

287. Find the Duplicate Number

Medium64.7% acceptance22 companies

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

1 <= n <= 10⁵
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up: