Easy Java solution with O(n) running time and O(1) additional space.

  • 0
    public class Solution {
        public int missingNumber(int[] nums){
            int i = 0; 
            int n = nums.length;
            while(i < n)
                if(nums[i] < n && nums[i] != nums[nums[i]]){
                     int temp = nums[nums[i]];
                     nums[nums[i]] = nums[i];
                     nums[i] = temp; 
                else i++;
            int j = 0;
            while(j < n && nums[j] == j)
            return j;  

    The logic is simple : nums[i] should be stored at index i. The first element
    which is not in it's correct position is the missing number.

    1. For every index array i if the value stored is not i then store i at nums[i] by swapping the elements.
    2. After step 1, recurse the array again from 0.
    3. The first element such that nums[i] != i is the missing number!.

Log in to reply

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