LESSON 152 OF 414 · LOOPING OVER ARRAY INDICES

Linear Lower Bound in Scala: O(n) Scan with Early Return

Given a sorted array of integers nums, find the smallest index where we can place a given value such that the array remains sorted

Example 1:

Input: nums = [1, 2, 3, 5, 7], value = 4
Output: 3
Explanation: Placing the value 4 on the 4^th index we obtain nums = [1, 2, 3, 4, 5, 7]

Example 2:

Input: nums = [1, 2, 3], value = 2
Output: 1
Explanation: Placing the value 2 on the 1^st index we obtain nums = [1, 2, 2, 3]

Note:

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

Hints:

value should be placed right before the first element greater than or equal to it.

We can iterate through the elements of nums until we find the first one greater than or equal to value.

As we need to return an index, we will iterate through every index i between 0 and n - 1 using a for loop. What should we do inside this loop?

Inside the loop, we can check if nums(i) >= value and if so, return i and exit the program. What if there is no such element tho?

If the loop terminates and we haven't returned anything, this means value must be placed at the end of the array. So, below the for loop, we should return nums.size.

STEP 1 OF 3

Guided

Ctrl + Enter to check

Linear Lower Bound in Scala, explained

Problem overview

The method lowerBound receives a sorted array of integers, nums, and an integer value. It returns the smallest index at which value could be inserted so that the array stays sorted.

In the first example, nums = [1, 2, 3, 5, 7] and value = 4. Inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7], which is sorted, so the answer is 3. In the second example, nums = [1, 2, 3] and value = 2. The value 2 is already present at index 1, and inserting another 2 there gives [1, 2, 2, 3], so the answer is 1. Index 2 would also keep the array sorted, but the task asks for the smallest index.

The statement allows O(n) time and O(1) extra space, so a single pass over the array with a few variables is enough.

Approach: find the first element that is not smaller

Because nums is sorted, every element before the insertion point is smaller than value, and every element from that point on is greater than or equal to it. The answer is therefore the index of the first element that is greater than or equal to value.

That gives a plain linear scan: walk through the indices from left to right and stop at the first element that is not smaller than value. If the scan never stops, every element is smaller than value, and the value belongs after the last one, at index nums.size.

Since the array is sorted, a binary search could find the same position in O(log n) time. This lesson uses the simple scan, which is the version to understand first.

Step by step

Loop over the indices. The answer is a position, not an element, so the loop variable i runs over nums.indices, the range from 0 to nums.size - 1. Looping over the elements directly would give you the values but not where they sit.
Test each element. Inside the loop, check whether nums(i) >= value. If so, return i right away: it is the first such index, and nothing after it needs to be looked at. The comparison is >= rather than > so that, when value is already present, you get the index of its first occurrence.
Handle the no-match case. After the loop, return nums.size. Reaching that line means no element was greater than or equal to value, so the value goes at the end.

The solution in Scala

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

A few Scala details are worth knowing here:

Parentheses for indexing. Scala reads an array element with nums(i), not nums[i]. Square brackets are used for type parameters, as in Array[Int].
i <- nums.indices. The arrow reads as "for each i in". The expression nums.indices is the range 0 until nums.size, so i never reaches nums.size.
return inside a loop. A for loop in Scala is a method call that takes a function, and return still leaves lowerBound from inside it. Scala 3.5 accepts the code and prints a warning that non-local returns are no longer supported, recommending boundary from scala.util. The method behaves as described, and the lesson's tests pass.
Return type and last expression. The last expression of a block is its value, so the final return could be written as plain nums.size. The explicit return says the same thing.

Complexity

Time: O(n). In the worst case, when every element is smaller than value, the loop looks at all n elements once and does constant work for each. In the best case it stops at index 0. Space: O(1). The method only uses the loop variable. It does not copy or change the array.

Edge cases and common mistakes

Value larger than everything. For nums = [1, 2, 3] and value = 9 the loop finishes without returning, and the answer is 3, which is nums.size. This is the case the final line exists for.
Value smaller than everything. For value = 0 on the same array, the very first element passes the test and the answer is 0.
Empty array. The loop body never runs, and the method returns nums.size, which is 0. That is correct: the only place to insert is index 0.
Duplicates. With nums = [1, 2, 2, 2, 3] and value = 2 the answer is 1, the first 2. Using > instead of >= would skip all the 2s and return 4, which is the wrong index.
Returning the element instead of the index. return nums(i) compiles, since both are Int, but it returns a value from the array and not its position.

Testing

Inputs worth trying, with their answers:

[1, 2, 3, 5, 7] with 4 gives 3.
[1, 2, 3] with 2 gives 1.
[1, 2, 3] with 9 gives 3.
[1, 2, 3] with 0 gives 0.
[] with 5 gives 0.

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

Start learning free