Start learning free

LESSON 147 OF 338 · LOOPING OVER ARRAY INDICES

Lower Bound in Go: Linear Scan of a Sorted Slice

Practice Read the full explanation

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 4th 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 1st 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
    Ctrl + Enter to check

    GO · LOOPING OVER ARRAY INDICES

    Linear Lower Bound in Go, explained

    Problem overview

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

    For nums = [1, 2, 3, 5, 7] and value = 4, inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7], so the answer is 3. For nums = [1, 2, 3] and value = 2, the 2 can go at index 1, before the existing 2, giving [1, 2, 2, 3], so the answer is 1. The statement asks for O(n) time and O(1) extra space. The function only computes the position: it does not change the slice.

    Approach

    Because the slice is sorted, all elements smaller than value come first, then the elements that are greater than or equal to it. The answer is the boundary between the two groups: the index of the first element that is greater than or equal to value. Inserting there keeps the order, and it is the smallest index that does.

    A linear scan finds that boundary. Check the elements from the left, and return the index of the first one that is not smaller than value. If there is no such element, every element is smaller, so value belongs after the last one, at index len(nums).

    This is the same shape as a linear search, except the condition is "at least value" instead of "equal to value", and the fallback is the length instead of -1. Since the data is sorted, binary search could find the boundary in O(log n), but this lesson uses the simple scan.

    Step by step

    1. Loop over the indices. for i := range nums keeps only the index, because the answer is a position and not an element.
    2. Test the boundary. If nums[i] >= value, return i. The first element that passes this test is the first one that is not smaller, and since the slice is sorted, every element after it passes too.
    3. Handle the end. After the loop, return len(nums). Reaching that line means every element was smaller than value, so value goes at the end.

    The solution in Go

    func lowerBound(nums []int, value int) int {
    for i := range nums {
        if nums[i] >= value {
            return i
        }
    }
    return len(nums)
}

    The Go details worth knowing:

    • Index-only range. With one variable, range over a slice yields indices. The element is read with nums[i].
    • Index versus length. The valid indices are 0 to len(nums) - 1, but the answer may be len(nums). An insertion position at the end is not an index of an existing element, and that is fine here because the function only returns the number.
    • Early return. Returning inside the loop leaves the function immediately, so the scan stops at the first suitable index.
    • A required final return. Go demands a return at the end of a function that has a result, so return len(nums) is needed for the compiler as well as for the logic.

    Complexity

    Time: O(n). In the worst case, when every element is smaller than value, the loop looks at all n elements.

    Space: O(1). Only the loop index is kept.

    Edge cases and common mistakes

    • Value already present. The comparison is >=, not >. With >, [1, 2, 3] and 2 would return 2, but the smallest valid position is 1.
    • Duplicates. [1, 2, 2, 3] with 2 returns 1, the first copy.
    • Smaller than everything. [5, 6] with 1 returns 0.
    • Larger than everything. [1, 2, 3] with 9 returns 3, the length.
    • Empty or nil slice. The loop does not run and the function returns 0, which is len(nums).
    • Returning -1 at the end. This is not a search for a present value. There is always a valid insertion position.

    Testing

    • []int{1, 2, 3, 5, 7} with 4 gives 3.
    • []int{1, 2, 3} with 2 gives 1.
    • []int{1, 2, 3} with 9 gives 3.
    • []int{} with 1 gives 0.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free