Cyclic Sort

Given an array with n elements. Each element is a unique number from range 0 to n-1. Let's see some arrays below.

[0,1,2,3,4]
[1,0,2,3,4]
[2,0,1,3,4]
...

You can see from the above arrays that these arrays are just like permutations. There is a special sorting algorithm to make this kind of array sorted.

The idea is, because every element is unique, we can try to place all element at its own place. Take array [3,2,1,0] as an example, let's see the process.

[3,2,1,0], index 0, value 3, swap index 0 and index 3
[0,2,1,3], index 0, value 0, index++
[0,2,1,3], index 1, value 2, swap index 1 and index 2
[0,1,2,3], index 1, value 1, index++
[0,1,2,3], index 2, value 2, index++
[0,1,2,3], index 3, value 3, index++

As you can see, we just iterate the array once, so time complexity is O(n), and we don't need any other space, so space complexity is O(1).

function cyclic_sort(nums: number[]) {
    let i = 0;

    while(i < nums.length) {
        const j = nums[i];
        if (i === j) {
            i += 1;
        } else {
            [nums[i], nums[j]] = [nums[j], nums[i]]
        }
    }
};

Missing Number

The problem's description is very similiar to cyclic sort pattern. But two things need to be noted. First, because there is one missing number, so there might be one element which has the value equal to array's length, which means we shouldn't swap it at this case. The solution is that because it is the largest element, so we don't need to swap it, after all other elements have find their place, this element will be placed at the end of the array. Second, after cyclic sorting, we need to iterate the array again to find the target missing number.

function missingNumber(nums: number[]): number {
    let i = 0;
    while(i < nums.length) {
        const j = nums[i];
        // when j equals to nums.length, just ignore it and continue iterating
        if (j < nums.length && i !== j) {
            [nums[i], nums[j]] = [nums[j], nums[i]]
        } else {
            i += 1;
        }
    }

    for (let i = 0; i< nums.length; i++) {
        if (i !== nums[i]) {
            return i;
        }
    }

    return nums.length;
};

Find the Duplicate Number

This problem is similar to cyclic sort pattern too. The point is how to use the algorithm to solve it. If we try to use cyclic sort algorithm to sort this kind of array, we should find a pattern. Because there is a duplicate number, so according to cyclic sort, there will be two numbers want to be placed to the same index. So when we do the swap operation, we can check the source number and target number. If two numbers are equal, then this is the duplicate number.

function findDuplicate(nums: number[]): number {
    let i = 0;
    while (i < nums.length) {
        // this time, number range is [1,n], so minus 1 here
        const j = nums[i] - 1;
        if (i === j) {
            i += 1;
        } else {
            // if source equals target, then return
            if (nums[i] === nums[j]) {
                return nums[i];
            }
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }
    return -1;
};