Data Structures & Algorithms In Go/

...

/

Solution Review: Smallest Positive Missing Number

Solution Review: Smallest Positive Missing Number

This review provides a detailed analysis of finding the smallest positive missing number in an unsorted array.

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

Press + to interact
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.

...