What is the brute force approach and complexity for Find Missing and Repeating?

For each k in 1..n, scan the array and count k with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Find Missing and Repeating?

Swap each value v into index v − 1; the one wrong slot gives {A, B} with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Find Missing and Repeating?

Look for key signals in the prompt: "values 1..n, size n" indicates Each value has a home at index v − 1.; "one repeats, one is missing" indicates One wrong slot after placement gives both numbers.; "n up to 10^6" indicates Only O(N) works, and any sum of values or squares needs `long long`.; "O(1) auxiliary space" indicates No count array: either rearrange the array in place, or use sum + sum of squares if it is read-only..

Find Missing and Repeating

Medium·GeeksforGeeks Pro OnlyMedium

GeeksforGeeks

Problem Statement

You are given an array arr of size n. It should contain each number from 1 to n exactly once. Instead, one number A appears twice and one number B is missing.

Write findTwoElement(arr) that returns {A, B} — the repeating number first, then the missing number.

The array can be very large (up to 10^6 elements), so the solution should be O(N) time with O(1) extra space.

Input

An integer array arr of size n, with values in 1..n.

Output

A vector of two numbers: {A, B}, where A repeats and B is missing.

Example 1

Input: arr = [2, 2]

Output: [2, 1]

2 appears twice, so 1 is missing.

Example 2

Input: arr = [1, 3, 3]

Output: [3, 2]

3 appears twice and 2 is missing.

Example 3

Input: arr = [4, 3, 6, 2, 1, 1]

Output: [1, 5]

1 appears twice and 5 is missing.

Constraints

• 2 ≤ n ≤ 10^6
• 1 ≤ arr[i] ≤ n
• Expected: O(N) time, O(1) auxiliary space.
• Sums of the values (and of their squares) do not fit in `int` — use `long long` if you add them up.

Pattern Recognition Clues

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

“values 1..n, size n”

→ Each value has a home at index v − 1.

“one repeats, one is missing”

→ One wrong slot after placement gives both numbers.

“n up to 10^6”

→ Only O(N) works, and any sum of values or squares needs `long long`.

“O(1) auxiliary space”

→ No count array: either rearrange the array in place, or use sum + sum of squares if it is read-only.

Approach Complexity Ladder

Brute Force — count each value by scanningO(N²)O(1)

For each k in 1..n, scan the array and count k

Better — count arrayO(N)O(N)

Count every value once in an array of size n + 1

Optimal — cyclic sort, then find the one wrong slotO(N)O(1)

Swap each value v into index v − 1; the one wrong slot gives {A, B}

Brute Force Intuition

For k = 1, 2, …, n, count how often k appears by scanning the whole array. Count 2 is A; count 0 is B.

Recognition rule for this sub-pattern:

One value appears twice and one is missing. After placement, the bad index gives both at once.

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