Find the Duplicate Number

Find the Duplicate Number is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Fast & Slow (Cycle Detection) subpattern.

Problem statement

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 <= 105

- 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:

- How can we prove that at least one duplicate number must exist in nums?

- Can you solve the problem in linear runtime complexity?

Topics and companies

Topics: Array, Two Pointers, Binary Search, Bit Manipulation.

Reported in interviews at Microsoft, Amazon, Apple, Google, Bloomberg, Paypal, Goldman Sachs.

How to practise Find the Duplicate Number on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Find the Duplicate Number in the code editor, or read the Find the Duplicate Number editorial for a worked solution with its approach and complexity analysis.

Where Find the Duplicate Number sits in the DSA pattern sheet

• Two Pointers pattern guide
• Fast & Slow (Cycle Detection) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find the Duplicate Number

Other problems that use the same Fast & Slow (Cycle Detection) and Two Pointers techniques:

• Happy Number — Easy, same subpattern
• Is Subsequence — Easy, same subpattern
• Linked List Cycle — Easy, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern