First missing positive integer in linear time and constant space

Question

This problem was asked by Stripe.

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.

class DailyCodingProblem5 {

    public static void main(String args[]) {
        int[] arr = { 3, 4, -1, 1 };
        int res = solution(arr);
        System.out.println(res);

        int[] arr2 = { 1, 2, 0 };
        res = solution(arr2);
        System.out.println(res);
    }

    private static int solution(int[] arr) {
        int n = arr.length;
        int i = 0;
        for (i = 0; i < n; i++) {
            int val = arr[i];

            if (val <= 0 || val > n)
                continue;
            while (val != arr[val - 1]) {
                int nextval = arr[val - 1];
                arr[val - 1] = val;
                val = nextval;
                if (val <= 0 || val > n) {
                    break;
                }
            }
        }
        for (i = 0; i < n; i++) {
            if (arr[i] != i + 1) {
                return i + 1;
            }
        }
        return n+1;

    }
}

How can i improve the above solution? Is there any improvements i can have in my code ?

Answer 1

It would be good to have some comments in the code explaining why (a) it works; (b) it takes linear time.

---

        int i = 0;
        for (i = 0; i < n; i++) {

I would prefer to use for (int i = 0; ...) and similarly for the other loop over i: they don't need to use the same variable, and keeping scopes as small as possible helps understanding and maintenance. But if you prefer to keep the variable in the wider scope, there's no need to initialise it twice. Either of

        int i = 0;
        for (; i < n; i++) {

or

        int i;
        for (i = 0; i < n; i++) {

works fine.

---

            if (val <= 0 || val > n)
                continue;
            while (val != arr[val - 1]) {
                int nextval = arr[val - 1];
                arr[val - 1] = val;
                val = nextval;
                if (val <= 0 || val > n) {
                    break;
                }
            }

It's a bit inelegant to apply the range test twice. A simple refactor gives

        while (val > 0 && val <= n && val != arr[val - 1]) {
            int nextval = arr[val - 1];
            arr[val - 1] = val;
            val = nextval;
        }

---

        }
        return n+1;

    }

For consistency I would add whitespace around +. The blank line makes more sense to me before the return rather than after it, and I would also add a blank line separating the two loops.

The fact that I'm nitpicking whitespace like this is a good sign: I haven't found anything which I consider to be a major problem.