Start learning free

LESSON 135 OF 415 · LOOPS & CONDITIONALS

Array Contains in Swift: Linear Search with a for Loop

Practice Read the full explanation

Given an array of integers nums and another integer value, check if value occurs in nums.

If the value occurs in nums, return true; otherwise return false.


Examples:

contains([1, 2, 4, 5], 4) -> true

contains([-1, 2, -4, 0, 10], 7) -> false

Note:

Do not use builtin functions such as contains(), it would defy the whole purpose of the challenge. Write the whole code yourself.

STEP 1 OF 3
    Ctrl + Enter to check

    SWIFT · LOOPS & CONDITIONALS

    Array Contains in Swift, explained

    Problem overview

    The method contains takes an array of integers nums and an integer value. It returns true if value occurs anywhere in nums and false otherwise. For [1, 2, 4, 5] and 4 the answer is true. For [-1, 2, -4, 0, 10] and 7 it is false.

    The task is to write the search yourself rather than call the array's built-in contains, so the loop is the whole point.

    Approach: look at every element until you find it

    Nothing is known about the order of the array, so the only way to be sure a value is missing is to look at every element. This is a linear search. Start at the first element and compare each one with value. The first match settles the question, so the method can return true at once. If the loop ends without a match, every element has been ruled out, and the answer is false.

    The answer false can only be given after the loop, never inside it. One element that differs from value says nothing about the rest.

    Step by step

    1. Loop over the array with for num in nums. This visits each element in order and gives it the name num. No index is needed.
    2. Compare inside the loop. When num == value, return true. A return ends the whole method immediately, so the remaining elements are never examined.
    3. Return false after the loop. The line is reached only when no element matched, so no else is needed.

    The solution in Swift

    class Solution {
    func contains(_ nums: [Int], _ value: Int) -> Bool {
        for num in nums {
            if num == value {
                return true
            }
        }
        return false
    }
}

    Swift details worth knowing:

    • Unlabeled parameters. Each parameter is declared with a leading _, so the call is Solution().contains([1, 2, 4, 5], 4) with no labels.
    • Method versus built-in. The method is named contains, like the standard library's [1, 2, 3].contains(2). The two are unrelated: the method belongs to Solution, and the loop does the work.
    • Value semantics. The array is passed as a value and the method only reads it, so the caller's array is untouched.
    • Return paths. Swift requires every path of a function that returns Bool to return a value. The final return false covers the case where the loop finishes, including an empty array.

    Complexity

    Time: O(n). In the worst case, a missing value or one in the last position, every element is compared once. If the value is the first element, the method returns after one comparison.

    Space: O(1). Only the loop variable is used, whatever the size of the array.

    Edge cases and common mistakes

    • Empty array. The loop doesn't run and the method returns false.
    • Returning false in an else inside the loop. The method would then decide after the first element and miss matches further on. For [1, 2, 4, 5] and 4 it would return false.
    • Duplicates. The method stops at the first occurrence, so repeated values cost nothing extra.
    • Negative numbers and zero. The comparison with == works the same for them.

    Testing

    • [1, 2, 4, 5], 4 gives true.
    • [-1, 2, -4, 0, 10], 7 gives false.
    • [], 3 gives false.
    • [3], 3 gives true.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free