Java Daily Coding Problem #004

Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Java, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

Problem

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.

Strategy

Spoilers! Don't look below unless you want to see my solution!

The way I interpret this problem is that we're looking for the smallest integer value, greater than 0, which does not appear in the array. So if an array contains 1, 2, and 3, but not 4, the code should return 4. Duplicates and negative numbers can be ignored. The maximum value which should be returned is the length of the array plus one, as shown in the second example, so the solution will always be between 1 and N+1, inclusive, where N is the length of the given array.

My first thought is to create a new array of length N, fill it with falses, and flip those falses to true if the index exists in the given array. But this solution is not a constant-space solution, as it requires an array of length N. (Though it is linear in time, since we only need to pass through the original array once.) What can we do instead?

The example arrays aren't sorted, so we can't make any assumption that they will be in general. In researching a constant-space, linear-time sorting algorithm, I found this SO answer, which prescribes the following algorithm that fits those requirements:

1. Start at the first array element.
2. If its array index matches its value, go to the next one.
3. If not, swap it with the value at the array index corresponding to its value.
4. Repeat step 3, until no more swaps are necessary.
5. If not at the end of the array, go to the next array element, otherwise go to step 7
6. Go to step 2.
7. Done

Note that there is a problem with this for our purposes -- our array can contain duplicates and negative numbers. Suppose the integer at index 0 is 7, and the integer at index 7 is also 7 -- we would be stuck in an infinite loop! So this solution is also out.

This is a tough problem!

The prompt says that we can modify the input array in place, which -- to me -- seems like the only way we can keep this algorithm as constant space complexity. (Apart from making a true/false array, as described above, with a length equal to Integer.MAX_VALUE.) So I think we need to do something similar to the above, but not exactly the same.

After a bit more research, I found this solution to this problem, which suggests simply ignoring the negative values. I wonder if that will work? So the (slightly clarified) algorithm would be instead:

1. Move to the next element of the array (or start at the beginning of the array if this is the first time that this step has been encountered):
2. If this is the last element of the array, move to step 5.
3. If this element's array index matches its value, or if its value is zero or negative, go back to step 1. Otherwise, continue to step 4.
4. Swap this element's value with the value contained at the index represented by this element's value and go back to step 3.
5. Step through the array again, from the beginning, and compare the array indices (1-based) to the values they contain. If the index and value do not match, that index is the smallest positive integer value which is not contained within the array.

For the example array given in the prompt, this process looks like (all 1-based indices):

[ 3,  4, -1,  1] -- original array
[-1,  4,  3,  1] -- after swapping 1st and 3rd elements
[-1,  1,  3,  4] -- after swapping 2nd and 4th elements
[ 1, -1,  3,  4] -- after swapping 2nd and 1st elements

Then, we can just walk the array a second time to find the first element whose value doesn't match its index. Walking the array twice requires N + N time, or 2N (aka. linear) time. Since we're modifying the array in place, this is also a constant space solution. Let's consider another example:

[ -1, -1,  8,  1,  2,  2]

The algorithm should return 3 for this array. But when we get to the third element (8), we have a problem: the array has fewer than 8 elements. We need to add another condition to step 3 of our algorithm:

If this element's array index matches its value, or if its value is zero, negative, or larger than the length of the array, go back to step 1. Otherwise, continue to step 4.

Stepping through this second example:

[ -1, -1,  8,  1,  2,  2] -- original array
[  1, -1,  8, -1,  2,  2] -- after swapping 4th and 1st elements
[  1,  2,  8, -1, -1,  2] -- after swapping 5th and 2nd elements
[  1,  2,  8, -1, -1,  2] -- ...

And here we run into another problem -- duplicates. We will have an infinite loop if we keep trying to swap the 6th and 2nd elements in the above example. So we should check if the "target" and "source" value are the same, and if they are, move to the next element of the array:

Swap this element's value with the value contained at the index represented by this element's value, unless the two values are the same, in which case go back to step 1.

So the final algorithm looks like:

1. Move to the next element of the array (or start at the beginning of the array if this is the first time that this step has been encountered):
2. If this is the last element of the array, move to step 5.
3. If this element's array index matches its value, or if its value is zero, negative, or larger than the length of the array, go back to step 1. Otherwise, continue to step 4.
4. Swap this element's value with the value contained at the index represented by this element's value, unless the two values are the same, in which case go back to step 1.
5. Step through the array again, from the beginning, and compare the array indices (1-based) to the values they contain. If the index and value do not match, that index is the smallest positive integer value which is not contained within the array.

...I think this should work. Let's try coding it!

Code

So the first thing I do is set up a shell class. We'll want a method which finds the first missing integer and maybe a main which runs the two examples in the prompt:

public class DCP004 {

  public static void main (String[] args) {
    findSmallestMissing(new int[]{  3,  4, -1,  1 });
    findSmallestMissing(new int[]{  1,  2,  0 });
  }

  public static int findSmallestMissing (int[] array) {
    // to be implemented
    return -1;
  }

}

Now, within findSmallestMissing(), we'll want to implement our algorithm outlined above. First, let's set up a loop to move through the array:

  public static int findSmallestMissing (int[] array) {

    // if array is null or empty, 1 is the smallest missing number
    if (array == null || array.length < 1) return 1;

    // get the length of the array
    int len = array.length;

    // assume 1 is smallest missing number until proven otherwise
    int smallestMissing = 1;

    // loop over input array (steps 1 and 5)
    for (int ii = 0; ii < len; ++ii) {
      // implement steps 2-4 in here
    }

    // to be implemented
    return -1;
  }

Within that loop is where most of the work of this algorithm happens:

    // loop over input array (steps 1 and 5)
    for (int ii = 0; ii < len; ++ii) {

      // step 3 (make sure to use 1-based indexing)
      if (array[ii] == (ii+1) || array[ii] < 1 || array[ii] > len)
        continue;

      // step 4
      while (array[ii] != ii) {

        // index of the element to swap with
        int swap = array[ii]-1;

        // value of the element to swap with
        int temp = array[swap];

        // swap the values
        array[swap] = array[ii];
        array[ii] = temp;

        // if the new value is < 1 or > len, move to next one
        if (temp < 1 || temp > len) break;
      }
    }

Since we've modified array in place, the last thing we need to do is loop through it and find the first element whose value doesn't match its (base-1) index:

    // loop over modified array
    for (int ii = 0; ii < len; ++ii) {
      if (array[ii] != ii+1) return ii+1;
    }

    return len+1;

I've written this code in my markdown editor without testing it, so let's paste it all together and see if it works!

Debugging

jshell> /open DCP004.java

jshell> DCP004.main(new String[]{})

jshell> DCP004.findSmallestMissing(new int[]{1, 2, 0})
$3 ==> 3

jshell> DCP004.findSmallestMissing(new int[]{3, 4, -1, 1})
$4 ==> 1

...alright, so we've got a few small issues. First, in main, nothing is printed. Let's add System.out.println statements around those function calls in main:

  public static void main (String[] args) {
    System.out.println(findSmallestMissing(new int[]{  3,  4, -1,  1 }));
    System.out.println(findSmallestMissing(new int[]{  1,  2,  0 }));
  }

Next, it looks like the first array returns the correct result (3), but we have a problem with the second array. It's returning 1 when it should be returning 2. Is this just an off-by-one error? Let's try another array:

jshell> DCP004.findSmallestMissing(new int[]{2, 4, -1, 1})
$7 ==> 

...this has no return value because I had to kill it -- I think there was an infinite loop! I've found one problem at least. The following line:

      while (array[ii] != ii) {

...should instead be

      while (array[ii] != (ii+1)) {

That seems to have fixed the problem!

jshell> DCP004.findSmallestMissing(new int[]{2, 4, -1, 1})
$9 ==> 3

jshell> DCP004.findSmallestMissing(new int[]{3, 4, -1, 1})
$10 ==> 2

There is another issue, though. This array also gives an infinite loop:

jshell> DCP004.findSmallestMissing(new int[]{1, 1, 2, 2, 3, 5})
$11 ==> 

...what did we miss this time? To debug, let's print out the array before each swap in the while loop:

      // step 4
      while (array[ii] != (ii+1)) {

        // DEBUG: print array
        System.out.println(Arrays.toString(array));

        // index of the element to swap with
        int swap = array[ii]-1;

The output for the last example looks like:

[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
...

It looks like nothing was ever swapped! (Or, the two 1s at the beginning are swapped over and over again.) It looks like we forgot to break out of the while when the two swapped values are identical. Let's add a catch for that:

        // if the new value is < 1 or > len, move to next one
        if (temp < 1 || temp > len) break;

        // if new value equals old value, move to next one
        if (temp == array[ii]) break;

...has that fixed the problem?

jshell> DCP004.findSmallestMissing(new int[]{1, 1, 2, 2, 3, 5})
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 2, 1, 2, 3, 5]
[1, 2, 1, 2, 3, 5]
[1, 2, 3, 2, 1, 5]
$15 ==> 4

jshell> DCP004.findSmallestMissing(new int[]{-1, -1, 8, 1, 2, 4})
[-1, -1, 8, 1, 2, 4]
[1, -1, 8, -1, 2, 4]
[1, 2, 8, -1, -1, 4]
$16 ==> 3

...it looks so!

Discussion

There we go! A solution in constant time and linear space which also prints the modified array before each swap for diagnostic purposes. It works fine on the example arrays and the few additional arrays I've thrown at it.

This problem took a bit of thinking to stick to the constraints, but it was fun! Can anyone find any arrays that break my code?

All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.

Suggestions? Let me know in the comments.