Leetcode: Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Understand the problem:
Since the problem suggests to use O(n) time complexity and constant space complexity, we can easily think of using the idea of bucket sorting. 

For each number, we need to check if i == num[i], if not, we need to swap the number to its corresponding bucket. At last, we iterate the array again and find out the missing number. 

There is one corner case to consider: if the array after the bucketing is [0, 1, 2], then the missing number is 3. That is because we have N numbers ranging from 0 to N, the last bucket stores N - 1. So we need to return nums.length.

Code (Java):

public class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // Step 1: iterate the array and swap according to the buckets
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num != i && num < nums.length && num != nums[num]) {
                swap(nums, i, num);
                i--;
            }
        }
        
        // Step 2: iterate again to find out the missing number
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        
        return nums.length;
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}