Posts Find the Duplicate Number
Post
Cancel

Find the Duplicate Number

PROBLEM DESCRIPTION

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

leetcode

SOLUTION

APPROACH 1

The simplest way using O(N) space is by using a HashSet. Keep adding numbers in the list to the HashSet and keep a check if it was already present. If it was already present, that number must be the duplicate.

APPROACH 2

One observation is that the range of numbers is [1-N]. So, for each number, we can make the number at index (i-1) to negative. This will mark that the number has been “visited”. When we encounter the duplicate number, the corresponding index will already have a negative number. So, we can return the current number as the duplicate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public int findDuplicate(int[] nums) {

        for(int i=0; i<nums.length; i++){
            
            int x = Math.abs(nums[i]);

            if(nums[x-1] < 0) return x;

            nums[x-1] = nums[x-1] * -1;

        }

        //restore
        for(int i=0; i<nums.length; i++){
            nums[i] = Math.abs(nums[i]);
        }

        return 0;
        
    }

}

Example: [4,3,4,5,2,4,1]

Since the numbers are in the range of [1-N], where N+1 is the size of the array, we have one important observation:

  • If we pick 3, there are exactly 3 numbers less than or equal to 3.
  • If we pick 4, there are more than 4 numbers which are less than or equal to 4.
  • If we pick any number after 4, it will be more than that number

So, if we consider our search space as [1-N], we can apply binary search and look for possible answers based on the above condition. If the number of numbers which are >= X is equal to X, then it must not be a duplicate. Otherwise, that is a possible answer, look for better answer which are lower. The lowest number which satisfies this condition will be our answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    
    public int findDuplicate(int[] nums) {

        int l=1;
        int r=nums.length-1;

        int ans = 0;

        while(l<=r){
            
            int m = (l+r)/2;

            if(check(m, nums)){
                ans = m;
                r=m-1;
            }else{
                l=m+1;
            }

        }

        return ans;
        
    }

    //how many numbers in nums array are >= m
    public boolean check(int m, int[] nums){
        
        int count = 0;

        for(int i=0; i<nums.length; i++) if(nums[i] <= m) count++;

        if(count > m) return true;

        return false;
    }

}

APPROACH 4

This problem can be converted into: Find the start of the cycle in a LinkedList.
Linked List Cycle II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public int findDuplicate(int[] nums) {

        int slow = nums[0];
        int fast = nums[0];

        do{
            slow = nums[slow];
            fast = nums[nums[fast]]; //move two steps ahead
        }while(slow != fast);

        slow = nums[0];

        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow; //or fast

    }
    
}
This post is licensed under CC BY 4.0 by the author.