Find the Missing no from an array the efficient way-CodePudding

I am trying to find an efficient way to solve the find a missing number from an array. I implemented the following way it's O(n). Please write any codes that efficiently solves this, just for learning purpose.

func findMissingNo(arrA: [Int]) -> [Int] {
    let firstIndex = arrA.first ?? 0
    let lastIndex = arrA.last ?? 0
    let rslt = Array(firstIndex...lastIndex)
    let missingNoArray = rslt.filter{ !arrA.contains($0)}
    return missingNoArray
}
findMissingNo(arrA: [11,12,14,15,16,18]) // Prints [13, 17] by looping 9 times

CodePudding user response：

Quickly written and tested (in terms of times performances against your code, but not in term of possible edges cases/mistakes, for instance, if array is 0...10, it won't work, but I'll let you work on the edges cases, since I focused mainly on the main cases, cases which might be covered during an edit and the end of the question)

Your current code:

func findMissingNo(arrA: [Int]) -> [Int] {
    let firstIndex = arrA.first ?? 0
    let lastIndex = arrA.last ?? 0
    let rslt = Array(firstIndex...lastIndex)
    let missingNoArray = rslt.filter{ !arrA.contains($0)}
    return missingNoArray
}
let numberArray = [11,12,14,15,18]
let missing1 = findMissingNo(arrA: numberArray)
print("Missing1: \(missing1)")

My attempt:

func findMissingNo2(arrA: [Int]) -> [Int] {
    var missingNumbers: [Int] = []
    guard arrA.count > 2 else { return missingNumbers }
    for i in 0...arrA.count-2 {
        var current = arrA[i]
        let next = arrA[i 1]
        if next != current   1 {
            current  = 1
            while current != next {
                missingNumbers.append(current)
                current  = 1
            }
        }
    }
    return missingNumbers
}


let missing2 = findMissingNo2(arrA: numberArray)
print("Missing1: \(missing2)")

Creating a big batch:

var array = Array(0...1000)
for _ in 0...10 {
    if let index = array.indices.randomElement() {
        let value = array.remove(at: index)
        print("removed: \(value)") //To check just in case that's the good value returned by the methods
    }
}

Testing:

let date1 = Date()
for _ in 0...100 {
    let missing = findMissingNo(arrA: array)
    print(missing)
}
print(Date().timeIntervalSince(date1)) //18.617565035820007

let date2 = Date()
for _ in 0...100 {
    let missing = findMissingNo2(arrA: array)
    print(missing)
}
print(Date().timeIntervalSince(date2)) //0.09566605091094971

print("---End")
print("")

For the time, I got: 18.857954025268555 vs 0.09159696102142334, a big factor difference (~200 times).

Why is there such a big difference?

Because of

let missingNoArray = rslt.filter{ !arrA.contains($0)}

It means:
for each number in result, check if arrayA contains that number.
->
for each number in result, for each number in arrayA (with a stop condition, so it's not a full iteration, but "almost" in term of complexity) check if there is a match...
Here there is a "double" (which is in fact not double, but n?) iteration that you missed.

I tested first with bigger value (array from "0 to 100000"), but it was taking too much time, with that "low number of values", the difference can already be seen.

Instead, you could use a Set:

let missingNoArray = Array(Set(rslt).subtracting(Set(arrA))).sorted()

It's faster than you method in my tests, (double my solution (0.21 ~ 0.22) in time performances), but still much faster than yours. I added the sorted(), which may or may not be important in your solution, but will add time consumption since Set aren't ordered.

For the edges cases (ie: [3], [3, 4], [3, 8])

guard arrA.count > 2 else { return missingNumbers }

==>

guard !arrA.isEmpty else { return [] }
guard arrA.count > 2 else {
    if arrA[0]   1 >= arrA[1] {
        return []
    } else {
        return Array((arrA[0]   1)...arrA[1]).dropLast() //Because last will be arrA[1] which is present)
    }
}