Java In-place swapping solution


  • 0
    P

    The idea is to take element at index i and replace it with element at index A[i] until we get i equal to A[i] - 1 . We iterate this logic over each element of the Array beginning from first element. After this iteration each element at index i will have i + 1 as it's value and those element that are not in this array will have value other than i + 1.

    public class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> result = new ArrayList<>();
            for(int i=0; i<nums.length; i++){
                if(i+1 == nums[i])
                    continue;
                    
                int x = nums[i];
                int y = nums[x-1];
                
                while(x != y){
                    nums[x-1] = x;
                    x = y;
                    y = nums[y-1];
                }
            }
            for(int i=0; i<nums.length; i++){
                if(nums[i] != i + 1){
                    result.add(i+1);
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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