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

For each i, scan indices before i for the same value with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Find the Two Repeating Elements?

Make arr[x − 1] negative the first time x is seen; already negative means repeat with optimal time complexity O(N) and space complexity O(1).

Find the Two Repeating Elements

Q: How do you identify the pattern for Find the Two Repeating Elements?

Look for key signals in the prompt: "values between 1 and n" indicates Each value has a home slot x − 1 that can store a flag.; "size n + 2" indicates Two more slots than values — full cyclic placement leaves two slots with no home value.; "order of second occurrence" indicates The answer depends on scan order, so detect repeats while walking left to right — don't rearrange first.; "O(1) extra space" indicates No seen array — hide the flag in the sign of arr[x − 1]..

Medium·GeeksforGeeks Pro OnlySlight Variation

GeeksforGeeks

Problem Statement

You are given an array arr of size n + 2. Every value is between 1 and n. Each value 1..n appears once, except two values that appear twice.

Return those two repeated values in the order of their second occurrence: the value whose second copy comes first (from the left) goes first. This is the order the GFG practice problem "Two Repeated Elements" expects.

The function here is vector<int> twoRepeated(vector<int>& arr), where n = arr.size() − 2. Aim for O(N) time and O(1) extra space.

Input

An integer array arr of size n + 2, with 1 ≤ arr[i] ≤ n.

Output

The two repeated values, ordered by where their second copy appears.

Example 1

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

Output: 1 3

1 repeats at index 2, and 3 repeats at index 5. Index 2 comes first, so 1 is listed first.

Example 2

Input: n = 2, arr = [1, 2, 2, 1]

Output: 2 1

1 appears first in the array, but its second copy is at index 3. The second copy of 2 is at index 2, so 2 comes first.

Example 3

Input: n = 5, arr = [3, 1, 5, 1, 3, 2, 4]

Output: 1 3

3 appears first, but 1 repeats first (index 3), then 3 (index 4).

Constraints

• 2 ≤ n ≤ 10^5
• arr.length == n + 2
• 1 ≤ arr[i] ≤ n
• Exactly two values appear twice; every other value 1..n appears once.
• Expected: O(N) time, O(1) extra space.

Pattern Recognition Clues

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

“values between 1 and n”

→ Each value has a home slot x − 1 that can store a flag.

“size n + 2”

→ Two more slots than values — full cyclic placement leaves two slots with no home value.

“order of second occurrence”

→ The answer depends on scan order, so detect repeats while walking left to right — don't rearrange first.

“O(1) extra space”

→ No seen array — hide the flag in the sign of arr[x − 1].

Approach Complexity Ladder

Brute Force — look back for an earlier copyO(N²)O(1)

For each i, scan indices before i for the same value

Better — seen arrayO(N)O(N)

Remember each value in a bool array; report on the second sighting

Optimal — sign markingO(N)O(1)

Make arr[x − 1] negative the first time x is seen; already negative means repeat

Brute Force Intuition

Walk left to right. For each arr[i], scan arr[0 … i−1]. If an equal value is there, i is that value's second occurrence, so push it. Stop after two.

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