LESSON 147 OF 348 · LOOPING OVER ARRAY INDICES

Lower Bound in TypeScript: Linear Scan in O(n) Time

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 and 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 n.

STEP 1 OF 3

Guided

Ctrl + Enter to check

Linear Lower Bound in TypeScript, explained

Problem overview

The method lowerBound receives a sorted array of numbers, nums, and a number, 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 still sorted, so the answer is 3. In the second example, nums = [1, 2, 3] and value = 2. The 2 can go at index 1, in front of the existing 2, or at index 2, behind it. Both keep the array sorted, and the method must return the smaller one, 1.

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

Approach: find the first element that is not smaller

Because nums is sorted, everything before the insertion point is smaller than value, and everything from the insertion point on is greater than or equal to it. So the answer is the index of the first element that is greater than or equal to value. Walk through the array from the left and return the first index where that is true.

If the walk ends without finding such an element, every element is smaller than value, so it belongs after the last one. That position is nums.length.

A linear scan is the simplest correct answer. Since the array is sorted, binary search could find the same index in O(log n) time, but this lesson practises looping over indices, so it scans.

Step by step

Loop over the indices. The method returns a position, not an element, so the loop needs the index i. It starts at 0 and runs while i < nums.length. TypeScript infers that i is a number from its initial value, so no annotation is needed.
Compare and return. Inside the loop, check whether nums[i] >= value. The first time this is true, i is the answer, and return ends the method at once. Use >= and not >: when value is already in the array, the index of its first occurrence is the smallest valid position.
Handle the no-match case. After the loop, return nums.length. Reaching that line means no element was greater than or equal to value.

The solution in TypeScript

class Solution {
    lowerBound(nums: number[], value: number): number {
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] >= value) {
                return i;
            }
        }
        return nums.length;
    }
}

A few details are worth knowing:

Return from inside a loop. A return leaves the whole method, not just the current iteration. That is why the final return nums.length only runs when the loop finished without returning.
Types are only checked by the compiler. The annotations number[] and number are erased when TypeScript compiles to JavaScript. They help you while writing the code but add nothing at run time.
Plain numbers. A TypeScript number is a double-precision float, so the comparison works for negative values and decimals too, and there is no integer overflow to worry about here.
The return type. The method returns an index, which is always a whole number between 0 and nums.length inclusive. The value nums.length is one past the last valid index, which is exactly what "insert at the end" means.

Complexity

Time: O(n). In the worst case, when value is larger than every element, the loop runs nums.length times and each iteration does one comparison. In the best case it returns at index 0.

Space: O(1). The method only keeps the loop variable i. It does not copy or change the array.

Edge cases and common mistakes

Empty array. The loop never runs, and the method returns nums.length, which is 0. Inserting into an empty array puts the value at index 0.
Value larger than everything. [1, 2, 3] with value = 10 returns 3.
Value smaller than everything. [1, 2, 3] with value = -4 returns 0.
Duplicates. [1, 2, 2, 2, 3] with value = 2 returns 1, the first 2, and [2, 2, 2, 2] with value = 2 returns 0.
Using > instead of >=. That version skips over equal elements and returns the index after the last one that matches. For [1, 2, 3] and value = 2 it returns 2 instead of 1.
Forgetting the final return. Without return nums.length, the method returns undefined when every element is smaller, and with the lessons' compiler settings nothing warns you about it.
Returning the element. The task asks for a position. Returning nums[i] instead of i gives a value from the array.

Testing

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

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

Start learning free