Java O(n) time; O(1) space


  • 0
    G

    We know that if the numbers were continguous, the sum would be (n * (n + 1)) / 2; We can find the duplicate by changing the values in the array from positive to negative. So, all we need to do is sum the numbers in the array and compare that sum to what we expect (subtracting the duplicate we find along the way). The missing number will be revealed via simple algebra.

    public class Solution {
        public int[] findErrorNums(int[] nums) {
            int[] result = new int[2];
            int  max = Integer.MIN_VALUE;
            long sum = 0;
            
            for(int i = 0; i < nums.length; i++) {
                int idx = Math.abs(nums[i]);
                sum    += idx;
                max     = Math.max(max, idx);
                
                if(nums[idx-1] < 0) result[0] = idx;
                else nums[idx-1] = -nums[idx-1];
            }
            
            result[1] =  Math.abs((int)(sum - ((max * (max + 1)) / 2) - result[0]));
            if(result[1] == 0) result[1] = max + 1;
            
            return result;
        }
    }
    

Log in to reply
 

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