Leetcode 287) Find the Duplicate Number

20 Sep 2021 in Algorithms

• I used negative marking approach,

  • “We can track each number that has been seen before, by flipping the sign of the number located at index

    num

    , where

    (Two vertical bars) denotes absolute value”

My solution

• Given condition seems like I have to use index smartly.

class Solution {

    public int findDuplicate(int[] nums) {

        for(int i=0;i<nums.length;i++){
            if(nums[Math.abs(nums[i])]>0){
                nums[Math.abs(nums[i])]*=(-1);
            }else{
                for(int j=0;j<i;j++){
                    nums[Math.abs(nums[j])]*=-1;
                }
                return nums[i];
            }
        }
        return -1;
    }
}

Other Answer 1) Array as HashMap

• such a smart idea!

• “The key idea is to always map the number at index0 to its equivalent index.”

  class Solution {
      public int findDuplicate(int[] nums) {
          while (nums[0] != nums[nums[0]]) {
              int nxt = nums[nums[0]];
              nums[nums[0]] = nums[0];
              nums[0] = nxt;
          }
          return nums[0];
      }
  }
  

Other Answer 2) Binary Search

• New approach!

• Binary search can be utilized widely, so I should stop to think I cannot use the BS, if the array is UNSORTED.

• This algorithm has O(nlogn) time complexity.

• There is one given array, and we can think of an imaginary HashMap, which has keys of [1,2,3,4…n], and values of [frequency of 1 in a given array, frequence of 2 in a given array…].

  • We do not store this value , we already know the key sets of this imaginary hashmap, and what we need to examine by using binary search is the frequency of the key number in a given array.

  {1: Frequency of 1 in a given array, 2: Frequency of 2 in a given array ..}
  

  • The way of examination is something like this. key range [1,n]
    1. set a start pointer(1) and end pointer(n).
    2. examine how many values which are equal or less than (n+1)/2, shows up in a given array.
       1. If this value is greater than key, then move end pointer to the mid,
       2. if this value is equal to the key, then move start pointer to the mid.
    3. return the value.

class Solution {
    public int findDuplicate(int[] nums) {
        // 'low' and 'high' represent the range of values of the target        
        int low = 1, high = nums.length - 1;
        int duplicate = -1;

        while (low <= high) {
            int cur = (low + high) / 2;

            // Count how many numbers in 'nums' are less than or equal to 'cur'
            int count = 0;
            for (int num : nums) {
                if (num <= cur)
                    count++;
            }

            if (count > cur) {
                duplicate = cur;
                high = cur - 1;
            } else {
                low = cur + 1;
            }
        }
        return duplicate;
    }
}

Other Answer 3) Floyd’s Tortoise and Hare (Cycle Detection)

• Technique that was used in linked list!!

  class Solution {
      public int findDuplicate(int[] nums) {
    
          // Find the intersection point of the two runners.
          int tortoise = nums[0];
          int hare = nums[0];
    
          do {
              tortoise = nums[tortoise];
              hare = nums[nums[hare]];
          } while (tortoise != hare);
    
          // Find the "entrance" to the cycle.
          tortoise = nums[0];
    
          while (tortoise != hare) {
              tortoise = nums[tortoise];
              hare = nums[hare];
          }
    
          return hare;
      }
  }