LESSON 156 OF 414 · LOOPING OVER ARRAY INDICES

Linear Lower Bound in Rust: O(n) Scan of a Sorted Vector

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 at index 3 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 at index 1 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 nums.len() - 1 using a for loop. What should we do inside this loop?

Inside the loop, we can check if the element at index i is greater than or equal to value and if so, return i and exit the function. What if there is no such element though?

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 the length of nums, nums.len().

STEP 1 OF 3

Guided

Ctrl + Enter to check

Linear Lower Bound in Rust, explained

Problem overview

The function lower_bound receives a sorted vector of integers, nums, and an integer value. It returns the smallest index at which value could be inserted so that the vector stays sorted. The value doesn't have to be in the vector, and the vector isn't changed.

For nums = [1, 2, 3, 5, 7] and value = 4, the answer is 3: inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7]. For nums = [1, 2, 3] and value = 2, the answer is 1: inserting 2 there gives [1, 2, 2, 3]. The statement asks for O(n) time and O(1) extra space.

Approach: find the first element that is not smaller

Everything before the insertion point must be smaller than value, and everything from it onward must be at least as large. So the answer is the index of the first element that is greater than or equal to value. Because the vector is sorted, once one element passes that test, all the following ones do as well, which is why the first match is the right one.

This lesson finds it with a left-to-right scan, the same shape as a linear search. The difference is the test: a linear search stops on ==, while the lower bound stops on >=. If the scan finds no such element, every element is smaller than value, and it belongs at the end, at index nums.len().

Sortedness also allows a faster method, binary search, which halves the search range each step. The scan is the simpler version and fits the O(n) budget given here.

Step by step

Loop over the indices with for i in 0..nums.len(). The answer is a position, so the loop works with indices rather than elements.
Test with >=. If nums[i] >= value, return i as i32. Using >= rather than > makes a value that already exists map to the index of its first occurrence.
Return the length after the loop. If no element reached the value, return nums.len() as i32, the position just past the last element.

The solution in Rust

impl Solution {
    fn lower_bound(nums: Vec<i32>, value: i32) -> i32 {
        for i in 0..nums.len() {
            if nums[i] >= value {
                return i as i32;
            }
        }
        return nums.len() as i32;
    }
}

The Rust details worth a closer look:

Two casts, same reason. Both i and nums.len() are usize, while the function returns an i32. Rust doesn't convert integer types on its own, so each return needs as i32. Without it the compiler reports a type mismatch.
The range is half-open. 0..nums.len() excludes the length, so nums[i] never reads past the end. The length only appears in the final return, as a position and not as an index to read.
Early return from a loop. return leaves the whole function from inside the for, so the line after the loop runs only when no element qualified.
The standard library has this. For a sorted vector, nums.partition_point(|&x| x < value) returns the same position as a usize, using binary search. Writing the scan yourself shows what it computes.

Complexity

Time: O(n). The loop runs at most n times, once per element, doing a constant amount of work each time. It stops sooner when an early element is large enough, but the worst case, a value larger than everything, scans the whole vector.

Space: O(1). One loop variable, and no copy of the vector.

Edge cases and common mistakes

Value larger than everything. [1, 2, 3] with value 9 returns 3, the length.
Value smaller than everything. [1, 2, 3] with value 0 returns 0, because the first element already passes the test.
Value already present. [1, 2, 3] with value 2 returns 1. With > instead of >= the loop would skip past the 2 and return 2.
Duplicates. [1, 2, 2, 2, 3] with value 2 returns 1, the first of the 2s. That is the smallest index where inserting 2 keeps the order.
Empty vector. The loop doesn't run and the function returns 0, the only possible position.
Returning the element. The answer is i, not nums[i].
Returning -1 at the end. That is the linear search convention. Here a missing value still has a valid insertion point.
An unsorted vector. The reasoning depends on the order. On an unsorted vector, the first element that is not smaller doesn't mark an insertion point for a sorted result.

Testing

nums = [1, 2, 3, 5, 7], value = 4 gives 3.
nums = [1, 2, 3], value = 2 gives 1.
nums = [1, 2, 3], value = 9 gives 3.
nums = [1, 2, 3], value = 0 gives 0.
nums = [], value = 5 gives 0.

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

Start learning free