Start learning free

LESSON 135 OF 414 · LOOPS & CONDITIONALS

Array Contains in Scala: 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(), exists() or find(), it would defy the purpose of the challenge. Write the whole code yourself.

STEP 1 OF 3
    Ctrl + Enter to check

    SCALA · LOOPS & CONDITIONALS

    Array Contains in Scala, explained

    Problem overview

    The method contains receives an Array[Int] named nums and an Int named value. It returns true if value occurs somewhere in nums and false otherwise. The task asks you to write the search yourself, so library helpers that do it for you are off the table.

    For example, contains([1, 2, 4, 5], 4) is true because 4 is the third element. contains([-1, 2, -4, 0, 10], 7) is false, because none of the five elements equals 7.

    Approach: linear search

    An unsorted array gives no hint about where a value might be, so the only way to be sure is to look at the elements one by one and compare each with value. This is called a linear search.

    The search can stop early. The moment one element matches, the answer is true and the remaining elements don't matter. The answer can be false only after every element has been checked and none matched. This asymmetry is what shapes the code: the check inside the loop returns true, and the false comes after the loop.

    Step by step

    1. Loop over the elements. for (num <- nums) binds each element to num in turn, in index order.
    2. Compare and return early. If num == value, return true at once. This ends the whole method, so nothing after the match is examined.
    3. Return false after the loop. The line after the loop runs only if no element matched, so it needs no else. An empty array falls straight through to it.

    The solution in Scala

    class Solution {
    def contains(nums: Array[Int], value: Int): Boolean = {
        for (num <- nums) {
            if (num == value) {
                return true
            }
        }
        return false
    }
}

    The Scala details worth knowing:

    • == compares values. For Int it checks whether the two numbers are equal. The same operator also compares strings and other values by content.
    • Explicit return. Idiomatic Scala usually leaves out return and lets the last expression be the result. This loop is a good case for it, though, because the method must stop in the middle of the iteration.
    • A compiler warning. The body of a for loop is a function that Scala passes to foreach, and a return inside it must jump out of the enclosing method. Scala 3.5 accepts this and the method works, but the compiler prints a warning that non-local returns are deprecated and that boundary and boundary.break from scala.util are the replacement. The warning does not change the result.
    • Why the method needs a final return false. A for loop without yield has the type Unit. If the last thing in the method were the loop, the compiler would reject the method, because it declares a Boolean result.
    • A library shortcut exists. nums.contains(value) and nums.exists(_ == value) do the same job in one line. The exercise asks for the loop, because writing it teaches the pattern.

    Complexity

    Time: O(n). In the worst case the value is the last element or absent, and the loop makes one comparison for each of the n elements. In the best case the first element matches and the method stops after one comparison.

    Space: O(1). The method only uses the loop variable, and nothing grows with the input size.

    Edge cases and common mistakes

    • Empty array. The loop body never runs and the method returns false, which is right because nothing can occur in an empty array.
    • Value at either end. Matches in the first or last position are found like any other.
    • Duplicates. The method stops at the first match, so how many times the value appears makes no difference.
    • Returning false inside the loop. An else { return false } branch makes the method answer after looking at only the first element. contains([1, 2, 4, 5], 4) would wrongly give false.
    • Negative numbers. They compare like any other numbers, so contains([-1, 2, -4, 0, 10], -4) is true.

    Testing

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