LESSON 151 OF 414 · LOOPING OVER ARRAY INDICES

Linear Search in Scala: O(n) Time with Indices

Given an array of integers nums, return the index of a given value.

If the value doesn't exist, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums(2) is 4

Note:

Your algorithm should run in O(n) time and use O(1) space.

Hints:

We should try out each element in nums until we find one equal to value and return its index. How can we achieve this?

With a for loop, of course! We can use a variable num to iterate through the elements and an if statement to check if num == value:

for (num <- nums) {
  if (num == value) {
    // Solution found! But...
  }
}

This is how we look for value in nums, but there's a problem. The problem asks us to return the index of that element, and by iterating like this we only know the value of the current element, not its index. How can we fix this?

We should use another method of iterating through an array: by indices! Let's use an index variable i to go through every index between 0 and nums.length - 1:

for (i <- nums.indices) {
  // index is i, value is nums(i)
  if (nums(i) == value) {
    return i
  }
}

What if we don't have any element equal to value? Where should we return -1?

for (i <- nums.indices) {
  // index is i, value is nums(i)
  if (nums(i) == value) {
    return i
  }
}

// Here:
return -1

If we reach the line with the comment, this means the for loop terminated naturally without returning any index. If we have had returned an index, we wouldn't even be executing this line of code as the program would have finished.

We have a for loop that performs exactly n iterations (where n is the length of nums), thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 3

Guided

Ctrl + Enter to check

Linear Search in Scala, explained

Problem overview

The method find receives an array of integers nums and an integer value. It returns the index of value in the array, or -1 if the value isn't there. For Array(1, 2, 4, 5) and value = 4, the 4 sits at index 2, so the answer is 2.

The statement asks for O(n) time and O(1) extra space. The array isn't sorted, so you can't skip any element in advance.

Approach: check each position in order

This is linear search. Start at the first element and check one position after another until you either find the value or run out of array. The first position where the element equals value is the answer, and you can stop right there.

Looping over the elements, as in for (num <- nums), is not enough, because the loop variable holds a value and not its position. To return an index, loop over the indices and read the element at each one.

If the loop ends without a match, then every position was checked and none held the value, so the method returns -1. That number can never be a real index, so the caller can't confuse it with a position.

Step by step

Loop over the indices with for (i <- nums.indices). The range nums.indices is 0 until nums.length, every valid position.
Test nums(i) == value. Scala reads an element with parentheses. If they are equal, return i immediately. Returning inside the loop stops the search at the first match, so when the value occurs several times, you get its first index.
Return -1 after the loop. The line is reached only if no return ran inside the loop.

The solution in Scala

class Solution {
    def find(nums: Array[Int], value: Int): Int = {
        for (i <- nums.indices) {
            if (nums(i) == value) {
                return i
            }
        }
        return -1
    }
}

For nums = Array(1, 2, 4, 5) and value = 4, the loop checks index 0 (1), index 1 (2) and index 2 (4). The third check succeeds, so the method returns 2 and never looks at index 3.

Language details

return inside a for loop. A Scala for loop over a range is compiled to a call that takes the body as a function, and a return inside it leaves the whole method. This works as the lesson needs. Scala 3 prints a compiler warning that such non-local returns are no longer supported and suggests scala.util.boundary, but the code compiles and returns the right index.
The result type. The method's type is Int, so both the index and -1 fit.

Complexity

In the worst case the value is the last element or missing, so the loop checks all n positions: O(n) time. When the value is early in the array the method returns sooner, but the bound is stated for the worst case. The method stores only the loop variable, so the extra space is O(1).

Edge cases and common mistakes

The value is missing. The loop ends without returning and the method returns -1. With Array(1, 2, 4, 5) and value = 9 the answer is -1.
Duplicates. Array(4, 4) with value = 4 returns 0, the first index.
An empty array. The loop doesn't run and the method returns -1.
Putting return -1 inside the loop. The method would give up after the first element that doesn't match. The -1 belongs after the loop.
Returning the value instead of the index. return nums(i) hands back the element you already knew. The task asks for i.
Square brackets. nums[i] is not how Scala reads an array element. Use nums(i).

Testing

Try Array(1, 2, 4, 5) with 4 (2), the same array with 9 (-1), Array(4, 4) with 4 (0), and an empty array with any value (-1).

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free