Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Problem: Find the Duplicate Number

Explore how to find the duplicate number in an integer array without modifying it and using constant extra space. Learn to apply binary search on the value range and utilize the pigeonhole principle for an efficient O(n log n) time solution while maintaining O(1) space complexity.

We'll cover the following...

Statement

You are given an integer array nums of length n + 1, where every element lies in the range [1,n][1, n] inclusive.

Exactly one number in nums is repeated (it may appear more than once), while all other numbers appear exactly once. Return the repeated number.

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

Note:
How can we prove that at least one duplicate number must exist in nums? Can you solve the problem in linear time?

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • nums.length ==== n +1+ 1 ...