287. Find the Duplicate Number (Solution || Leetcode medium || Java)

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.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

SOLUTION:

            class Solution {
    public int findDuplicate(int[] nums) {
      int i = 0;
        
        while(i < nums.length){
            int correct = nums[i] - 1;
            
            if(nums[i] != nums[correct]){
                int temp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = temp;
            }
            else if(nums[i] != i+1){
                return nums[i];
            }
            else{
                i++;
            }
        }
        
        return -1;
    }
}

SOLUTION(2):

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

Runtime: 4 ms, faster than 97.21% of Java online submissions for Find the Duplicate Number.

Memory Usage: 78.1 MB, less than 17.56% of Java online submissions for Find the Duplicate Number.

Thank you for reading. If you have any queries, then please let me know in the comment section, I will surely response toward it.