Problem

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.

Solution

To solve this, you should think what’s common between array indexes and a positive integer: it’s the same thing. So we put each positive integer of an array at its place (i+1 since we count from 1) and then iterate again to find first missing. If we don’t, return length plus one (=next).

Code

func solution(aa []int) int {
	if len(aa) == 0 {
		return 1
	}
	for _, a := range aa { // try to place all numbers at same index (from 1)
		if a < 0 { // we don't care, it's negative
			continue
		}
		if a >= len(aa) { // we don't care, result always < len(aa)
			continue
		}
		aa[a-1] = a
	}
	for i := range aa { // find first missing
		if aa[i] != i+1 {
			return i + 1
		}
	}
	return len(aa) + 1 // all there
}

Benchmarks

goos: darwin
goarch: amd64
pkg: github.com/ngalayko/dcp/problems/2018-07-05
Benchmark/0-4   1000000000               2.18 ns/op            0 B/op          0 allocs/op
Benchmark/100-4                 20000000                65.0 ns/op             0 B/op          0 allocs/op
Benchmark/200-4                 10000000               122 ns/op               0 B/op          0 allocs/op
Benchmark/300-4                 10000000               178 ns/op               0 B/op          0 allocs/op
Benchmark/400-4                 10000000               238 ns/op               0 B/op          0 allocs/op
Benchmark/500-4                  5000000               295 ns/op               0 B/op          0 allocs/op
Benchmark/600-4                  5000000               354 ns/op               0 B/op          0 allocs/op
Benchmark/700-4                  3000000               410 ns/op               0 B/op          0 allocs/op
Benchmark/800-4                  3000000               466 ns/op               0 B/op          0 allocs/op
Benchmark/900-4                  3000000               528 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/ngalayko/dcp/problems/2018-07-05     19.293s

Links

github