In place sorting with O(n) time O(1) space complexity


  • 0
    L
    public int[] findErrorNums(int[] nums) {
            //Sort in place: O(n)
            for (int i = 0; i < nums.length; i++) {
                while (nums[nums[i] - 1] != nums[i]) {
                    swap(nums, i, nums[i] - 1);
                }
            }
    
            //Find dup and miss: O(n)
            int duplicate = nums[0], miss = 1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i + 1) {
                    duplicate = nums[i];
                    miss = i + 1;
                    break;
                }
            }
    
            return new int[]{duplicate, miss};
        }
    
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

Log in to reply
 

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