Swift how does my function exceed O(n)?

Question

I am trying to work on a leetcode problem that asks for

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

My solution to the problem is:

func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
    var returnedArray = [Int]()

    if nums.isEmpty == false {
        for i in 1...nums.count {
            if nums.contains(i) == false {
                returnedArray.append(i)
            }
        }
    } else {
        returnedArray = nums
    }
    return returnedArray
}

However, leetcode tells me that my solution is "Time limit exceeded"

Shouldn't my solution be O(n)? I am not sure where did I made it to be greater than O(n).

Answer 1

If I haven't missed anything your algorithm is O(n^2).

First, you iterate over each element of the array which is O(n), but for each element, you call contains which has to iterate over all the elements again and you end up with O(n^2).

I refrain from telling you the solution since it is for leetcode.