Array 101 Find All Numbers Disappeared in an Array in Go

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

My code

func findDisappearedNumbers(nums []int) []int {
    n := len(nums)
    i := 0
    for i < n {
        if nums[i] == nums[nums[i]-1] {
            i++
        } else {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    missing := make([]int, 0)
    for i, v := range nums {
        if v != i+1 {
            missing = append(missing, i+1)
        }
    }
    return missing
}

• I wanted to implement O(n) code, but I don't have any idea solve this.
• So this code is somehow looping.
• I started arranging the number -1 into the array address.
• If the same number already exists in the array address, i is incremented.
• If not, a swap will happen.
• When the swap is finished, the array is output in order.
• If the address + 1 has different from the value, the value is not given to the initial array.
• So it will be added to missing array.

sample 36 ms submission

func findDisappearedNumbers(nums []int) []int {
    var results []int
    for i := 0; i < len(nums); i++ {
        if i != nums[i] - 1 && nums[i] - 1 < len(nums) && nums[nums[i]-1] != nums[i] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
            i--
        }
    }
    for i := range nums {
        if nums[i] != i + 1 {
            results = append(results, i + 1)
        }
    }
    return results
}

• This code is somehow complicated also simple.
• But almost same with my code.. what is the optimized code..
• Result slice was made.
• For loop will continue with increment.
• So when if condition is true, In short when values are swapped, i will decrease.
• After arrangement, Second for loop will check array has expected value added by 1.

sample 40 ms submission & sample 6800 KB submission

func findDisappearedNumbers(nums []int) []int {

 ans := []int{}
    for _, v := range nums {
        idx := abs(v) - 1
        if nums[idx] > 0 { nums[idx] = -nums[idx] }
    }
    for i, v := range nums {
        if v > 0 { ans = append(ans, i + 1) }
    }
    return ans
}

func abs(n int) int {
    if n > 0 { return n }
    return -n
}

• It just put - value to array[value-1]
• Sp after this, when array has positive then that index+1 value is missing.
• This code do less process than normal swapping code.
• Not bad. I need to take this concept also.

sample 41 ms submission

func findDisappearedNumbers(nums []int) []int {
    result := make([]int, len(nums))

    for _, v := range nums {
        result[v-1] = v
    }

    j := 0
    for i := 0; i < len(nums); i++ {
        if result[i] == 0 { 
            result[j] = i + 1
            j++
        }
    } 

    return result[:j]
}

• This code makes result array with nums length size.
• While For loop, result array will have vaule in result[value -1]
• Second for loop will overwrite to result when result[i] will have 0.
• later it will return only j value(count)

sample 6800 KB submission

func findDisappearedNumbers(nums []int) []int {

    for _,v := range nums {
        ab := abs(v)
        nums[ab-1] = -abs(nums[ab-1])
    }

    missing := make([]int, 0, len(nums))
    for i, v := range nums {
        if v > 0 {
            missing = append(missing, i+1)
        }
    }

    return missing

}

func abs(x int) int {
    if x > 0 {
        return x
    }

    return -x
}

sample 6900 KB submission

func findDisappearedNumbers(nums []int) []int  {
    n := len(nums)
    seen := make([]bool, len(nums)+1)
    for _, num := range nums {
        seen[num] = true
    }
    var res []int
    for i := 1; i <=n;i++ {
        if !seen[i] {
            res = append(res, i)
        }
    }
    return res
}

• This code makes seen array with bool.
• When seen is true, this value exists.
• Also i implemented from 1.
• This made array address = value
• Good code

sample 7000 KB submission

func findDisappearedNumbers(nums []int) []int {
    output := make([]int, 0)
    numberMatched := false
    length := len(nums)
    for i:=1; i<=length; i++{
        numberMatched = false
        if len(nums) == 0{
            break
        }
        for j:=0; j<len(nums); j++{
            if i == nums[j]{
                numberMatched = true
                nums = append(nums[:j], nums[j+1:]...)
                numberMatched = true
                break
            }
        }
        if numberMatched == false{
            output = append(output, i)
        }
    }
    return output
}

• This code is not good because second for loop runs to find value from start to end every time.
• Concept is that first forloop is increment to find value
• Second forloop is deleting array when it has.
• But it took a lot of time.
  https://go.dev/play/p/p0Ysi6pU3mw

sample 7100 KB submission

func findDisappearedNumbers(nums []int) []int {

    //array to store result nums
    disappearedNums := []int{}

    for i := 0; i < len(nums); i++ {
        //find out whether or not an element "i+1" exist in input array
        _, found := Find(nums, i+1)

        //element is not found
        if !found {
            disappearedNums = append(disappearedNums, i+1)
        }
    }

    return disappearedNums

}

func Find(slice []int, val int) (int, bool) {
    for i, item := range slice {
        if item == val {
            return i, true
        }
    }
    return -1, false
}

• This code added Find function.
• I don't understand this code was made like that.
• When Find function couldn't find value, then it will be added.
• Takes a lot of time.

sample 7200 KB submission

func findDisappearedNumbers(nums []int) []int {
    disappeared := 0
    for idx := 0; idx < len(nums); idx++ {
        for nums[idx] != idx+1 {
            if nums[nums[idx]-1] == nums[idx] {
                disappeared++
                break
            }
            nums[idx], nums[nums[idx]-1] = nums[nums[idx]-1], nums[idx]
        }
    }
    count := 0
    for idx := 0; idx < len(nums) && count < disappeared; idx++ {
        if nums[idx] != idx+1 {
            nums[count] = idx+1
            count++
        }
    }
    return nums[:count]
}

• First for loop is just running to end of array.
• Second for loop is running until nums[idx] has idx+1.
• When if condition find duplicated number, it break for loop with increasing disappered.
• Thrid for loop will overwirte when nums[idx] and idx+1.
• New value will overwrite from 0 and return this array until count length.