Start learning free

LESSON 152 OF 415 · LOOPING OVER ARRAY INDICES

Lower Bound in Swift: O(n) Linear Scan of a Sorted Array

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 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.count - 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.count.
STEP 1 OF 3
    Ctrl + Enter to check

    SWIFT · LOOPING OVER ARRAY INDICES

    Linear Lower Bound in Swift, explained

    Problem overview

    The method lowerBound receives an array of integers nums, sorted in ascending order, and an integer value. It returns the smallest index at which value could be inserted so that the array 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, inserting 2 at index 1 gives [1, 2, 2, 3], so the answer is 1: when the value is already present, the answer is the index of its first occurrence.

    The lesson asks for O(n) time and O(1) extra space.

    Approach: find the first element that is not smaller

    The new value belongs right before the first element that is greater than or equal to it. Everything before that element is smaller, and the new value can slide in without breaking the order. Taking the first such element, rather than any later one, gives the smallest valid index.

    Because the array is sorted, scanning from the left finds that element: every element before it is smaller than value, and from there on, all are at least as large. If no element is greater than or equal to value, then value is bigger than everything and belongs at the end, at index nums.count.

    A sorted array also allows binary search in O(log n). This lesson uses the plain scan, which is simpler and meets the stated bound.

    Step by step

    1. Loop over the indices. for i in 0..<nums.count. The answer is a position, so the loop needs the index and not just the element.
    2. Return at the first element that is not smaller. If nums[i] >= value, return i. Using >= rather than > makes an existing equal value count, so duplicates give the index of the first copy.
    3. Return the count after the loop. If the loop finishes, every element is smaller than value, so it goes after all of them, at nums.count.

    The solution in Swift

    class Solution {
    func lowerBound(_ nums: [Int], _ value: Int) -> Int {
        for i in 0..<nums.count {
            if nums[i] >= value {
                return i
            }
        }
        return nums.count
    }
}

    Swift details worth knowing:

    • Insertion index versus last index. The valid insertion points run from 0 to nums.count inclusive, one more than the valid element indices. Returning nums.count is therefore correct, even though nums[nums.count] would crash if you read it.
    • Half-open range. 0..<nums.count is empty for an empty array, so the body never runs and the method returns 0.
    • Early return. A return inside the loop ends the whole method at the first match, so later elements are never examined.
    • Compare with find. A plain search compares with == and returns -1 when nothing matches. Here the comparison is >= and the fallback is a real position.

    Complexity

    Time: O(n). The scan stops at the first element that is not smaller than value, but when value is larger than every element, all n are checked.

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

    Edge cases and common mistakes

    • Value smaller than everything. [2, 3] with value = 1 returns 0.
    • Value larger than everything. [1, 2, 3] with value = 9 returns 3, the length.
    • Empty array. The result is 0.
    • Repeated values. [2, 2, 2] with value = 2 returns 0, the first copy. A strict > would skip all three and return 3.
    • Returning nums.count - 1 for the fallback. That places the value before the last element, not after it.
    • Unsorted input. The scan returns the first element that is not smaller, which is only the right answer because the input is sorted.

    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 = [2, 2, 2], value = 2 gives 0.
    • nums = [], value = 5 gives 0.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free