Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Smallest Positive Missing Number

Explore multiple approaches for finding the smallest positive missing number in an array using Go. Learn to implement brute force, hash table, auxiliary array, and in-place rearrangement techniques along with their time complexities to understand their efficiency and application.

We'll cover the following...

First solution

Using a brute force method, we check if each number exists in the list. We compare each number starting from 1 to the array’s length and check if it’s present in the array. The first missing number is returned. If all of the numbers are present, then -1 is returned.

Let’s check the illustration below to better understand the solution.

Solution code

Go (1.6.2)
package main
import "fmt"
func SmallestPositiveMissingNumber(arr []int, size int) int {
    found := 0
    for i := 1; i < size+1; i++ {
        found = 0
        for j := 0; j < size; j++ {
            if arr[j] == i {
              found = 1
              break
             }
        }
        if found == 0 {
          return i 
        }
      }
  return -1 
}
//Testing code
func main() {
    arr := []int{8, 5, 6, 1, 9, 11, 2, 7, 4, 10}
    size := len(arr)
    fmt.Println("Missing Number :", SmallestPositiveMissingNumber(arr,size))
}

Time complexity

In this case, the time complexity is O(n2)O(n^2).

Explanation

  • Line 5: We initialize the found flag with a false value.

  • Lines 6–17: The outer for loop generates the number sequence from 1 to n and passes it to the inner for loop.

    • Line 7: At the start of each iteration, we reset this found flag.
    • Line 14–16: At the
...