Start learning free

LESSON 147 OF 348 · LOOPING OVER ARRAY INDICES

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

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

    KOTLIN · LOOPING OVER ARRAY INDICES

    Linear Lower Bound in Kotlin, explained

    Problem overview

    The function lowerBound receives a sorted IntArray named nums and an Int named value. It returns the smallest index at which value can be inserted so that the array stays sorted. The lesson asks for O(n) time and O(1) extra space.

    In the first example, nums = [1, 2, 3, 5, 7] and value = 4. Putting 4 at index 3 gives [1, 2, 3, 4, 5, 7], which is sorted, so the answer is 3. In the second, nums = [1, 2, 3] and value = 2. The 2 may go at index 1, before the existing 2, or at index 2, after it. Both keep the array sorted, and the smaller index, 1, is the answer.

    Approach: find the first element that is not smaller

    In a sorted array, everything to the left of the insertion point is smaller than value and everything to the right 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. Inserting there pushes that element and all later ones one step right, and the order is preserved.

    That gives a plain scan. Go through the indices from the left, and return the first one whose element is at least value. If there is no such element, every element is smaller, and the value belongs after the last one, at index nums.size.

    This scan is linear, which fits the lesson's budget. Because the array is sorted, a binary search could find the same index in O(log n) time, but that is a different lesson.

    Step by step

    1. Loop over the indices with for (i in nums.indices). The answer is a position, not an element, so the loop runs over positions.
    2. Check each element with nums[i] >= value, and return i as soon as it is true. The array is sorted, so the first such index is the insertion point. Use >= rather than >: when value is already present, the index of its first occurrence is the smallest valid answer.
    3. Return nums.size after the loop. Reaching that line means no element was greater than or equal to value, so the value goes at the end.

    The solution in Kotlin

    class Solution {
    fun lowerBound(nums: IntArray, value: Int): Int {
        for (i in nums.indices) {
            if (nums[i] >= value) {
                return i
            }
        }
        return nums.size
    }
}

    The Kotlin details behind it:

    • nums.indices is the range from 0 to nums.size - 1. For an empty array it is empty, so the loop doesn't run.
    • nums.size is the array's length, which is also the first index past the last element. The value 3 for an array of length 3 is a valid insertion index even though nums[3] doesn't exist, because nothing is read there.
    • Early return. A return inside the loop leaves the function immediately, so the scan stops at the first suitable index and never looks at the rest.
    • Comparison operators on Int. >= works directly on two Int values, and the result is a Boolean, which is what if needs.

    Complexity

    Let n be the length of nums.

    Time: O(n). In the worst case, when value is larger than every element, the loop examines all n elements, once each.

    Space: O(1). Only the loop variable is stored. The function doesn't build the new array, since it returns just the index.

    Edge cases and common mistakes

    • Smaller than everything. [1, 2, 3] with value = 0 returns 0, because the first element is already at least 0.
    • Larger than everything. [1, 2, 3] with value = 10 returns 3, the array size.
    • An empty array. The result is 0, since nums.size is 0 and the loop doesn't run.
    • Duplicates. [2, 2, 2, 5] with value = 2 returns 0, the first of the equal elements. With value = 3 it returns 3, where the 5 sits.
    • Using > instead of >=. For [1, 2, 3] and value = 2 the function would return 2 instead of 1.
    • Returning -1 for "end". Unlike a search for an element, this problem has no "not found". Every value has an insertion point, and the end of the array is one.
    • Returning the element. The function must return the index i, not nums[i].

    Testing

    • nums = [1, 2, 3, 5, 7], value = 4 gives 3.
    • nums = [1, 2, 3], value = 2 gives 1.
    • nums = [1, 2, 3], value = 0 gives 0.
    • nums = [1, 2, 3], value = 10 gives 3.
    • nums = [], value = 10 gives 0.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free