java solution based on first missing positive


  • 0
    B

    I think this problem is similar to LC 41: first missing positive, so I improvise a solution based on the logic used in LC 41. Here is the solution, which is 2pass O(n) time and O(1) space complexity.

    public List<Integer> findDuplicates(int[] nums) {
             List<Integer> res = new ArrayList<>();
            int i = 0;
           //logic from LeetCode 41: First Missing positive
            while(i < nums.length){
                if(nums[i] != nums[nums[i] - 1] && nums[i] != nums[nums[i] - 1]){
                    swap(nums, i, nums[i] - 1);
                }
                else{
                    i++;
                }
            }
    
            for(int k = 0; k < nums.length; k++){
                if(nums[k] != k + 1){
                    res.add(nums[k]);
                }
            }
            return res;
        }
        
        private void swap(int[] nums, int left, int right){
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.