Finding the Smallest Missing Positive Integer: Interview Problem Explanation and Go Solutions

The problem originates from a Tencent interview: given an array of QQ numbers (or any integers) within the range (0, max_unsigned_int), find the smallest missing positive integer in O(n) time and O(1) extra space.

Analysis shows that the answer must lie in the interval [1, n+1], where n is the array length. Three practical algorithms are discussed.

1. Brute‑Force

Iterate over [1, n+1] and check each value’s presence in the array. This yields O(n²) time, which is unsuitable for interviews.

2. Hash‑Based Approach

Insert all elements into a hash table and then scan the range [1, n+1]. Both time and space become O(n), still failing the O(1) space requirement.

3. Clever Marking (In‑Place)

Replace non‑positive numbers with n+1, then for each element use its absolute value as an index and mark the corresponding position negative. The first positive index after this pass indicates the missing number. This achieves O(n) time and O(1) space.

Go implementation of the marking method:

package main
import "fmt"

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func solution(a []int) int {
    n := len(a)
    for i := 0; i < n; i++ {
        if a[i] <= 0 {
            a[i] = n + 1
        }
    }
    for i := 0; i < n; i++ {
        num := abs(a[i])
        if num <= n {
            a[num-1] = -abs(a[num-1])
        }
    }
    for i := 0; i < n; i++ {
        if a[i] > 0 {
            return i + 1
        }
    }
    return n + 1
}

func main() {
    a := []int{3, 4, 1, -1}
    fmt.Println(solution(a)) // prints 2
}

4. Swap‑Based Placement

Iterate through the array, swapping each element into its correct position a[i‑1] when the value lies in [1, n]. After placement, a second pass finds the first index where a[i] != i+1, which is the missing integer. This also runs in O(n) time with O(1) extra space.

Go implementation of the swap‑based method:

package main
import "fmt"

func solution(a []int) int {
    n := len(a)
    for i := 0; i < n; i++ {
        // keep swapping until the current element is out of range or already in correct place
        for a[i] > 0 && a[i] <= n && a[a[i]-1] != a[i] {
            a[a[i]-1], a[i] = a[i], a[a[i]-1]
        }
    }
    for i := 0; i < n; i++ {
        if a[i] != i+1 {
            return i + 1
        }
    }
    return n + 1
}

func main() {
    a := []int{3, 4, 1, -1}
    fmt.Println(solution(a)) // prints 2
}

Both in‑place techniques satisfy the interview constraints and reliably produce the smallest missing positive integer.