O(n) Java Solution


  • 0
    H

    The idea is borrowed from the missing duplicate question.
    Mark the presence of numbers by setting the number at their respective index as negative. The duplicate is tracked by finding the number at its index as already negative.
    To find the missing number, go through the array again and find the number having its value still positive. Its index is the missing number.

    public int[] findErrorNums(int[] nums) 
    	{	
    		int dup = 0;
    		for(int i = 0; i < nums.length; i++)
    		{
    			int idx = Math.abs(nums[i]) - 1;
    			if(nums[idx] > 0)
    				nums[idx] = -nums[idx];
    			else
    				dup = idx + 1;
    		}
    		
    		for(int i = 0; i < nums.length; i++)
    		{
    			if(nums[i] > 0)
    				return new int[]{dup, i+1};
    		}
    		
    		return new int[2];
    		
        }
    

Log in to reply
 

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