What is the brute force approach and complexity for Find the Duplicate Number?

For each i, look for an equal value at some j > i with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Find the Duplicate Number?

Treat nums as a linked list; the start of its cycle is the duplicate with optimal time complexity O(N) and space complexity O(1).

Find the Duplicate Number

Q: How do you identify the pattern for Find the Duplicate Number?

Look for key signals in the prompt: "n + 1 values in 1..n" indicates Pigeonhole: something repeats, and every value is a valid index.; "must not modify the array" indicates No cyclic sort and no sign marking — those write into the array.; "O(1) extra space" indicates No seen array or hash set either.; "may appear more than twice" indicates Sum / XOR formulas break; the cycle view does not care how many copies there are..

Medium·LeetCode #287 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given an array nums with n + 1 integers. Every value is between 1 and n. Exactly one value is repeated — it may appear two times or more. Return that value.

You must not modify the array, and you may use only O(1) extra space.

Input

An integer array nums of length n + 1, with 1 ≤ nums[i] ≤ n.

Output

The repeated value.

Example 1

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

Output: 2

2 is the only value that appears more than once.

Example 2

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

Output: 3

3 appears twice.

Example 3

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

Output: 3

The repeated value can appear many times. Here it fills the whole array.

Constraints

• 1 ≤ n ≤ 10^5
• nums.length == n + 1
• 1 ≤ nums[i] ≤ n
• Exactly one value repeats (possibly more than twice).
• Do not modify nums. Use O(1) extra space.
• Follow-up: can you do it in O(N) time?

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“n + 1 values in 1..n”

→ Pigeonhole: something repeats, and every value is a valid index.

“must not modify the array”

→ No cyclic sort and no sign marking — those write into the array.

“O(1) extra space”

→ No seen array or hash set either.

“may appear more than twice”

→ Sum / XOR formulas break; the cycle view does not care how many copies there are.

Approach Complexity Ladder

Brute Force — compare every pairO(N²)O(1)

For each i, look for an equal value at some j > i

Better — binary search on the value (pigeonhole count)O(N log N)O(1)

Count elements ≤ mid; more than mid means the duplicate is ≤ mid

Optimal — Floyd's cycle detection on i → nums[i]O(N)O(1)

Treat nums as a linked list; the start of its cycle is the duplicate

Brute Force Intuition

Check every pair (i, j) with i < j. The first equal pair gives the duplicate. It only reads the array and uses no memory, so it follows the rules — it is just slow.

Recognition rule for this sub-pattern:

A repeated value finds its home already occupied. Cyclic sort, index marking, or Floyd's cycle all expose it.

Remember this · Cyclic Sort

Trigger

Numbers in range 1..n or 0..n, find missing / duplicate / both, O(1) extra space.

Think

Can value v live at index v−1? Then put everyone home and look for squatters.

Key question

Where does value v belong, and when do I stop swapping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Cyclic Sort translate into production architectures and low-level memory mechanics.

LLD Architecture