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

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

What is the optimal approach and complexity for Find Missing and Repeated Values?

Treat the grid as one list; swap value v into cell ((v − 1) / n, (v − 1) % n) with optimal time complexity O(N²) and space complexity O(1).

How do you identify the pattern for Find Missing and Repeated Values?

Look for key signals in the prompt: "values in 1..n² in an n × n grid" indicates n² values for n² cells — every value has a home cell.; "one appears twice, one is missing" indicates Same shape as Set Mismatch: one wrong slot gives both answers.; "grid" indicates Number the cells row by row; slot p is (p / n, p % n)..

Find Missing and Repeated Values

Easy·LeetCode #2965 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given an n × n grid. It was supposed to hold every number from 1 to n² exactly once. Instead, one number a appears twice and one number b is missing. Every other number appears exactly once.

Return [a, b] — the repeated value first, then the missing value.

Input

A square 2D integer array grid of size n × n, with values in 1..n².

Output

An array of two numbers: [a, b], where a is repeated and b is missing.

Example 1

Input: grid = [[1, 3], [2, 2]]

Output: [2, 4]

The values should be 1..4. 2 appears twice and 4 never appears.

Example 2

Input: grid = [[9, 1, 7], [8, 9, 2], [3, 4, 6]]

Output: [9, 5]

The values should be 1..9. 9 appears twice and 5 never appears.

Constraints

• 2 ≤ n == grid.length == grid[i].length ≤ 50
• 1 ≤ grid[i][j] ≤ n × n
• Exactly one value in 1..n² is repeated and exactly one is missing; all others appear once.

Pattern Recognition Clues

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

“values in 1..n² in an n × n grid”

→ n² values for n² cells — every value has a home cell.

“one appears twice, one is missing”

→ Same shape as Set Mismatch: one wrong slot gives both answers.

“grid”

→ Number the cells row by row; slot p is (p / n, p % n).

Approach Complexity Ladder

Brute Force — count each value by scanning the gridO(N⁴)O(1)

For each k in 1..n², scan the whole grid and count k

Better — count array of size n² + 1O(N²)O(N²)

Count every value once, then find counts 2 and 0

Optimal — cyclic sort on the grid, read row by rowO(N²)O(1)

Treat the grid as one list; swap value v into cell ((v − 1) / n, (v − 1) % n)

Brute Force Intuition

Go through k = 1, 2, …, n². For each k, look at every cell and count how often k appears. Count 2 means k is repeated; count 0 means k is missing.

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