Preface

Preface

Min free number puzzle

In the book, we only showed the divide and conqueror method to achieve the linear time O(n), and constant space O(1) solution. There are other ways to achieve such performance. Here are another two.

Before we diving into the detail, let's review the important fact we discussed in the book.

1 <= answer <= n + 1

Where n is the length of the sequence, and the answer is n + 1 when the original sequence is some permutation of 1 to n.

Radix sort

Any comparison based sort will downgrade the time performance to O(n lg n). So all methods, like heap, BST and so on are out. The idea is that we can put the i-th number x to the position where it should be, the x-th number. When i is greater than n, we know that it cann't be the answer, we can skip it. Otherwise, as the result, we exchange the number at the i-th and the x-th positions. Since the number we swapped to i-th position may not be i, we need repeatedly do this until either it exceeds n, or it becomes i. We iterate i from 1 to n, process all numbers. As each number will only swapped one time, this processing is linear (can you prove it formally?).

Next we scan the array 2nd round, if at any position i, the number isn't i, we find the answer. Otherwise, it means the array is 'full', and we return n+1 as the min free number.

Here is the C-style, C++ code.

int findMinFree1(vector<int> nums) {
    int i, n = nums.size();
    for (i = 0; i < n; ++i)
        while (nums[i] <= n && nums[i] != nums[nums[i]-1])
            swap(nums[i], nums[nums[i] - 1]);
    for (i = 0; i < n; ++i)
        if (i + 1 != nums[i])
            return i + 1;
    return n + 1;
}

Sng encoding

No matter using a flag array, or put the number to its 'right' position, we want to know if a number does exist. Exit or not is a kind of binary information. we can encode it as the sign of the number. The idea is that, if number x exists in the sequence, we mark the x-th number as negative. After we did this marking for all numbers if they are not greater than n, we can scan the sequence from left, find the first positive number. And that position is the answer.

Here is the C-style, C++ code

int findMinFree2(vector<int> nums) {
    int i, k, n = nums.size();
    for (i = 0; i < n; ++i)
        if ((k = abs(nums[i])) <= n)
            nums[k - 1] = - abs(nums[k - 1]);
    for (i = 0; i < n; ++i)
        if (nums[i] > 0)
            return i + 1;
    return n + 1;
}

End