Lets Code Everyday - Day 26

Question - 26:

Find the Duplicate Number

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.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

 First approach:

class Solution {
    public int findDuplicate(int[] nums) {
    Arrays.sort(nums);
    for(int i=0;i<nums.length-1;i++){
         if(nums[i]==nums[i+1]) return nums[i];
     }
    return 0;
  }
}

Step-by-step implementation:

1. The method findDuplicate takes an array of integers nums as an input and returns an integer.

2. The method sorts the input array using the Arrays.sort method. Sorting the array is important because it brings all duplicate elements together in the sorted order, making it easier to identify them.

3. The method then loops through the sorted array using a for loop that starts at the first element and goes up to the second-last element of the array (i.e., nums.length-1).

4. In each iteration of the loop, the code checks if the current element is equal to the next element in the array (i.e., nums[i] == nums[i+1]). If the elements are equal, that means we have found a duplicate, and the method returns that element (i.e., return nums[i]).

5. If the loop completes without finding any duplicates, the method returns 0 (i.e., return 0).

The time complexity of this algorithm is O(nlogn) because of the sorting operation. The space complexity is O(1) because the algorithm does not use any extra space.

Second approach:

class Solution {
    public int findDuplicate(int[] nums) {
    Map<Integer,Integer> resMap = new HashMap<>();
    for(int num:nums){
       if(resMap.get(num)!=null && resMap.get(num)==num)
           return num;
       else resMap.put(num,num);
     }
    return 0;
  }
}

Step-by-step implementation:

1. The method findDuplicate takes an array of integers nums as an input and returns an integer.

2. The method creates a new hashmap called resMap with Integer as key and Integer as value to keep track of previously seen numbers.

3. The method loops through each element in the input array using an enhanced for loop.

4. For each element in the input array, the method checks if the element already exists as a key in the resMap using the get() method. If the element already exists as a key in the resMap, it means the current element is a duplicate. In that case, the method checks if the value corresponding to the key in the map is equal to the current element. If it is, then we have found the duplicate, and the method returns that element (i.e., return num). If not, we skip to the next element.

5. If the current element is not a duplicate, the method adds it to the resMap with the element as both the key and the value (i.e., resMap.put(num, num)).

6. If the loop completes without finding any duplicates, the method returns 0 (i.e., return 0).

The time complexity of this algorithm is O(n) because it uses a hashmap to check if an element already exists, which takes constant time on average. The space complexity is also O(n) because the size of the resMap can grow up to the size of the input array nums.

Third approach:

class Solution {
    public int findDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for(int num:nums){
        if(set.contains(num)) return num;
        else set.add(num);
    }
    return 0;
  }
}

Step-by-step implementation:

1. The findDuplicate method takes an integer array nums as an input and returns an integer as output.

2. The method creates a new hash set called set with Integer as element type.

3. The method loops through each element in the input array using an enhanced for loop.

4. For each element in the input array, the method checks if the element already exists in the set using the contains() method. If the element already exists in the set, it means the current element is a duplicate, so the method returns that element (i.e., return num).

5. If the current element is not a duplicate, the method adds it to the set using the add() method (i.e., set.add(num)).

6. If the loop completes without finding any duplicates, the method returns 0 (i.e., return 0).

The time complexity of this algorithm is O(n) because the contains() and add() methods of a hash set take constant time on average. The space complexity is also O(n) because the size of the set can grow up to the size of the input array nums.

Conclusion:

The second and third approaches have lower time complexity and higher space complexity than the first. Depending on the requirements, one of three ways may be selected.

Thanks for reading...Happy learning...😊