Backend interview prep

Start Learning

Find Duplicate Number

Java coding interview problem for Array Logic: Find Duplicate Number.

Finding a duplicate number in an array is one of the most common interview problems.

This problem looks simple, but it tests important concepts:

  • Array traversal
  • Hashing
  • Sorting
  • Frequency counting
  • Cycle detection
  • Space optimization
  • Mathematical reasoning

This problem is a foundation for many advanced problems:

  • Find missing number
  • Find missing and duplicate number
  • Detect cycles
  • Data validation
  • Duplicate record detection

What is the Duplicate Number Problem?

Given an array containing n + 1 integers where each integer is in the range:

1 to n

find the duplicate number.

The array contains:

  • At least one duplicate.
  • Only one number is repeated.
  • The duplicate may appear multiple times.

Example 1

Input:

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

Numbers range:

1 to 4

Duplicate:

2

Output:

2

Example 2

Input:

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

Output:

3

Example 3

Input:

nums = [1,1]

Output:

1

Understanding the Problem

Consider:

[1,4,3,2,2]

Array size:

5

Valid numbers:

1,2,3,4

The value:

2

appears twice.

Therefore:

Duplicate = 2

Why Is This Question Asked in Interviews?

Interviewers ask this problem because it evaluates:

  • Efficient searching
  • Memory optimization
  • Data structure selection
  • Bit manipulation knowledge
  • Algorithm design

Common variations:

  • Find all duplicate numbers
  • Find duplicate without extra memory
  • Find first duplicate
  • Find duplicate and missing number
  • Find duplicate in a stream

Real-World Applications

Database Validation

Suppose customer IDs should be unique:

[101,102,103,104]

Database contains:

[101,102,103,102]

Duplicate:

102

User Registration Systems

Detect duplicate:

  • Email IDs
  • Usernames
  • Account numbers

Transaction Processing

Duplicate transaction IDs can cause:

  • Double payments
  • Incorrect balances
  • Data inconsistency

Log Processing

Detect repeated event IDs:

1001
1002
1003
1002

Duplicate:

1002

Problem Statement

Given an integer array:

nums

where:

  • Length is n + 1
  • Values are between 1 and n

find the duplicate number.

Constraints

Example:

1 <= n <= 100000

Rules:

  • Only one duplicate exists.
  • Duplicate may repeat multiple times.
  • Do not modify array if possible.

Understanding Duplicate Logic

Input:

[3,1,3,4,2]

Expected numbers:

1,2,3,4

Actual:

1,2,3,3,4

Extra occurrence:

3

Duplicate:

3

Array Visualization

Input:

Index:

0 1 2 3 4

3 1 3 4 2

Values:

3 appears twice

Visual:

3

↓

3 1 3 4 2
    ↑
   duplicate

Dry Run

Input:

[1,3,4,2,2]

Check:

1

Seen:

{1}

Check:

3

Seen:

{1,3}

Check:

4

Seen:

{1,3,4}

Check:

2

Seen:

{1,2,3,4}

Check:

2

Already exists.

Duplicate:

2

Approach 1 — Brute Force Comparison

The simplest approach is comparing every pair of elements.

For every element:

  • Compare with all other elements.
  • If two values are equal, return duplicate.

Algorithm

  1. Use two loops.
  2. Compare:
nums[i] == nums[j]
  1. Return duplicate.

Java Program

public class FindDuplicateBruteForce {


    public static int findDuplicate(
            int[] numbers) {


        for (int i = 0;
             i < numbers.length;
             i++) {


            for (int j = i + 1;
                 j < numbers.length;
                 j++) {


                if (numbers[i] == numbers[j]) {

                    return numbers[i];

                }

            }

        }


        return -1;

    }


    public static void main(String[] args) {


        int[] numbers =
                {1,3,4,2,2};


        System.out.println(
                findDuplicate(numbers));

    }

}

Output

2

Step-by-Step Explanation

Input:

[1,3,4,2,2]

Compare:

1 with 3,4,2,2

No match.

Compare:

3 with 4,2,2

No match.

Compare:

4 with 2,2

No match.

Compare:

2 with 2

Match found.

Return:

2

Complexity Analysis

Time:

O(n²)

Space:

O(1)

Advantages

  • Very easy to understand.
  • No additional memory.
  • Good for small arrays.

Drawbacks

  • Extremely slow for large inputs.
  • Too many comparisons.
  • Not suitable for production.

Approach 2 — Sorting Approach

The sorting approach finds duplicates by placing equal numbers next to each other.

Example

Input:

[3,1,4,2,2]

Sort:

[1,2,2,3,4]

Adjacent values:

2 == 2

Duplicate:

2

Algorithm

  1. Sort the array.
  2. Compare adjacent elements.
  3. If:
numbers[i] == numbers[i-1]

return duplicate.

Java Program

import java.util.Arrays;

public class FindDuplicateSorting {


    public static int findDuplicate(
            int[] numbers) {


        Arrays.sort(numbers);


        for (int i = 1;
             i < numbers.length;
             i++) {


            if (numbers[i] ==
                    numbers[i - 1]) {


                return numbers[i];

            }

        }


        return -1;

    }


    public static void main(String[] args) {


        int[] numbers =
                {3,1,4,2,2};


        System.out.println(
                findDuplicate(numbers));

    }

}

Output

2

Step-by-Step Explanation

Original:

[3,1,4,2,2]

Sort:

[1,2,2,3,4]

Compare:

1 and 2

Different.

Compare:

2 and 2

Same.

Return:

2

Complexity Analysis

Sorting:

O(n log n)

Traversal:

O(n)

Overall:

O(n log n)

Space:

O(1)

(ignoring sorting implementation)

Advantages

  • Simple implementation.
  • Better than brute force.
  • Easy to explain.

Drawbacks

  • Modifies original array.
  • Sorting is unnecessary overhead.
  • Not optimal.

Approach 3 — Using HashSet

HashSet is one of the most common solutions.

The idea:

  • Store visited numbers.
  • If number already exists, it is duplicate.

Algorithm

  1. Create HashSet.
  2. Traverse array.
  3. Check:
set.contains(number)
  1. If true, return number.
  2. Otherwise add it.

Java Program

import java.util.HashSet;
import java.util.Set;

public class FindDuplicateHashSet {


    public static int findDuplicate(
            int[] numbers) {


        Set<Integer> seen =
                new HashSet<>();


        for (int number : numbers) {


            if (seen.contains(number)) {

                return number;

            }


            seen.add(number);

        }


        return -1;

    }


    public static void main(String[] args) {


        int[] numbers =
                {1,3,4,2,2};


        System.out.println(
                findDuplicate(numbers));

    }

}

Output

2

Step-by-Step Explanation

Input:

[1,3,4,2,2]

Add:

1

Set:

{1}

Add:

3

Set:

{1,3}

Add:

4

Set:

{1,3,4}

Add:

2

Set:

{1,2,3,4}

Read:

2

Already exists.

Return:

2

Complexity Analysis

Time:

O(n)

Space:

O(n)

Advantages

  • Very simple.
  • Linear time.
  • Easy to maintain.

Drawbacks

  • Requires extra memory.
  • Not allowed in some interview constraints.

Approach 4 — Using HashMap Frequency

The HashSet approach finds whether a number exists.

But sometimes interviewers ask:

How many times does each number appear?

For this scenario, we use a HashMap.

HashMap stores:

Number → Frequency

Example

Input:

[1,3,4,2,2,3]

Frequency Map:

1 → 1

2 → 2

3 → 2

4 → 1

Duplicate numbers:

2

3

Algorithm

  1. Create a HashMap.
  2. Traverse the array.
  3. Store count of each number.
  4. Find number whose count is greater than one.
  5. Return duplicate.

Java Program

import java.util.HashMap;
import java.util.Map;

public class FindDuplicateHashMap {


    public static int findDuplicate(
            int[] numbers) {


        Map<Integer, Integer> frequency =
                new HashMap<>();


        for (int number : numbers) {


            frequency.put(
                    number,
                    frequency.getOrDefault(
                            number, 0) + 1);


            if (frequency.get(number) > 1) {

                return number;

            }

        }


        return -1;

    }


    public static void main(String[] args) {


        int[] numbers =
                {1,3,4,2,2};


        System.out.println(
                findDuplicate(numbers));

    }

}

Output

2

Step-by-Step Explanation

Input:

[1,3,4,2,2]

Process:

1

Map:

1 → 1

Process:

3

Map:

1 → 1

3 → 1

Process:

4

Map:

4 → 1

Process:

2

Map:

2 → 1

Process:

2

Update:

2 → 2

Duplicate found:

2

Complexity Analysis

Time:

O(n)

Space:

O(n)

Advantages

  • Provides frequency information.
  • Useful when multiple duplicates exist.
  • Easy to extend.

Drawbacks

  • Extra memory required.
  • More overhead than HashSet.

Approach 5 — Floyd's Cycle Detection Algorithm (Best Interview Solution)

Floyd's Cycle Detection algorithm is the optimal solution when:

  • Array cannot be modified.
  • Extra space is not allowed.

Complexity:

Time: O(n)

Space: O(1)

Core Idea

Treat the array as a linked list.

Each value points to the next index.

Example:

Array:

[1,3,4,2,2]

Index mapping:

index → value

0 → 1

1 → 3

2 → 4

3 → 2

4 → 2

Following values creates a cycle.

Visualization

Start:

0

Move:

0 → 1

1 → 3

3 → 2

2 → 4

4 → 2

2 → 4

Cycle:

2 ↔ 4

The cycle entry is the duplicate number.

Floyd Algorithm Has Two Phases

Phase 1 — Detect Cycle

Use:

slow pointer

fast pointer

Slow moves:

one step

Fast moves:

two steps

They meet inside the cycle.

Phase 2 — Find Cycle Entry

Reset one pointer to start.

Move both one step.

The meeting point is duplicate number.

Example

Input:

[1,3,4,2,2]

Initialize:

slow = nums[0]

fast = nums[0]

Move:

Slow:

1

Fast:

3

Continue:

Slow:

3

Fast:

4

Continue:

Slow:

2

Fast:

4

Eventually:

slow == fast

Cycle detected.

Java Program

public class FindDuplicateFloyd {


    public static int findDuplicate(
            int[] numbers) {


        int slow = numbers[0];

        int fast = numbers[0];


        // Phase 1: Detect cycle

        do {

            slow = numbers[slow];

            fast = numbers[numbers[fast]];


        } while (slow != fast);



        // Phase 2: Find cycle entry

        slow = numbers[0];


        while (slow != fast) {


            slow = numbers[slow];

            fast = numbers[fast];

        }


        return slow;

    }


    public static void main(String[] args) {


        int[] numbers =
                {1,3,4,2,2};


        System.out.println(
                findDuplicate(numbers));

    }

}

Output

2

Step-by-Step Explanation

Input:

[1,3,4,2,2]

Phase 1

Pointers move:

slow → 1

fast → 1

Slow:

nums[1] = 3

Fast:

nums[nums[1]]

nums[3]

= 2

Continue until:

slow == fast

Cycle found.

Phase 2

Reset:

slow = numbers[0];

Move both:

slow → duplicate

fast → duplicate

Meeting point:

2

Complexity Analysis

Time:

O(n)

Space:

O(1)

Advantages

  • Optimal solution.
  • No extra memory.
  • Does not modify array.
  • Preferred advanced interview solution.

Drawbacks

  • Harder to understand.
  • Requires cycle detection knowledge.

Mathematical Proof of Floyd's Algorithm

The array behaves like a linked list:

index → next index

Because:

next = nums[index]

Since duplicate values create multiple incoming paths,

a cycle must exist.

Example:

1 → 3 → 2 → 4
        ↑   ↓
        └───┘

The duplicate number is the cycle entry.

Approach 6 — Using Java Streams

Java Streams can detect duplicates using grouping.

Java Program

import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class FindDuplicateStreams {


    public static int findDuplicate(
            int[] numbers) {


        Map<Integer, Long> frequency =
                Arrays.stream(numbers)
                .boxed()
                .collect(
                    Collectors.groupingBy(
                        Function.identity(),
                        Collectors.counting()
                    ));


        return frequency.entrySet()
                .stream()
                .filter(entry ->
                    entry.getValue() > 1)
                .map(Map.Entry::getKey)
                .findFirst()
                .orElse(-1);

    }

}

Complexity Analysis

Time:

O(n)

Space:

O(n)

Advantages

  • Clean functional style.
  • Good for analytics.
  • Less manual code.

Drawbacks

  • Uses extra memory.
  • Stream overhead.
  • Not preferred for algorithm interviews.

Comparison of All Approaches

Approach Time Space Interview Rating
Brute Force O(n²) O(1) ⭐⭐
Sorting O(n log n) O(1) ⭐⭐⭐
HashSet O(n) O(n) ⭐⭐⭐⭐
HashMap O(n) O(n) ⭐⭐⭐⭐
Floyd Cycle Detection O(n) O(1) ⭐⭐⭐⭐⭐
Streams O(n) O(n) ⭐⭐⭐

Handling Multiple Duplicates

Example:

[1,2,3,2,3]

Duplicates:

2

3

Solutions:

Use:

  • HashMap
  • HashSet
  • Streams

Floyd's algorithm does not apply because it assumes:

  • One duplicate number.
  • Specific array constraints.

Primitive vs Object Arrays

Primitive Array

Example:

int[]

Advantages:

  • Faster.
  • Less memory.
  • Better performance.

Object Array

Example:

Integer[]

Advantages:

  • Works with Collections.
  • Supports Streams easily.

Common Interview Mistakes

Mistake 1

Using Floyd's algorithm without understanding constraints.

It requires:

Numbers range 1 to n

and:

One duplicate

Mistake 2

Modifying the array when not allowed.

Example:

Arrays.sort(numbers);

Mistake 3

Ignoring multiple duplicates.

Example:

[1,2,2,3,3]

Needs different handling.

Mistake 4

Using nested loops for large inputs.

Complexity:

O(n²)

Edge Cases

Input Output
[1,1] 1
[1,2,3,3] 3
[2,2,2] 2
Large array Use Floyd
Multiple duplicates Use HashMap

Interview Follow-up Questions

Q1. Find duplicate without extra memory.

Q2. Find all duplicates.

Q3. Find missing and duplicate number.

Q4. Why does Floyd work?

Q5. Explain array as linked list.

Q6. Detect duplicate in a stream.

Q7. Find first duplicate occurrence.

Q8. Remove duplicates from array.

Related Problems

  • Missing Number
  • Find All Duplicates
  • First Missing Positive
  • Linked List Cycle Detection
  • Single Number
  • Frequency Counting

Key Takeaways

  • Duplicate detection has multiple solutions.
  • HashSet is the simplest O(n) approach.
  • HashMap helps when frequency matters.
  • Floyd Cycle Detection is the optimal interview solution.

Remember:

Brute Force
    ↓
Sorting
    ↓
HashSet
    ↓
HashMap
    ↓
Floyd Cycle Detection

For senior-level interviews:

Explain:

Floyd Algorithm

Time: O(n)

Space: O(1)

Frequently Asked Interview Questions

Q1. What is the optimal solution?

Floyd Cycle Detection.

Complexity:

Time: O(n)

Space: O(1)

Q2. Why does duplicate create a cycle?

Because two indexes point to the same value.

That creates multiple paths into the same node.

Q3. Why not use HashSet?

HashSet works but requires:

O(n)

extra memory.

Q4. When should we use HashMap?

When we need:

  • Counts
  • Multiple duplicates
  • Frequency information

Interview Tip

When asked:

"Find duplicate number."

Clarify:

  1. Is there only one duplicate?
  2. Can the array be modified?
  3. Is extra space allowed?

Then explain:

  1. Brute Force
  2. Sorting
  3. HashSet
  4. HashMap
  5. Floyd Cycle Detection

The ability to explain the transition from simple solutions to the optimal O(n) time and O(1) space solution demonstrates strong understanding of Java, algorithms, and memory optimization.