Start learning free

LESSON 146 OF 347 · LOOPING OVER ARRAY INDICES

Lower Bound in C#: Insert Position in a Sorted Array, 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

    C# · LOOPING OVER ARRAY INDICES

    Linear Lower Bound in C#, explained

    Problem overview

    LowerBound(int[] nums, int value) receives a sorted array and a number. It returns the smallest index at which value could be inserted so that the array stays sorted. This index is called the lower bound of the value.

    Two examples show the idea:

    • 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], which is still sorted.
    • For nums = [1, 2, 3] and value = 2, the answer is 1. Inserting 2 at index 1 gives [1, 2, 2, 3]. Index 2 would also keep the array sorted, but the question asks for the smallest index.

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

    Approach: find the first element that is not smaller

    In a sorted array, everything smaller than value comes first, followed by everything greater than or equal to it. The insertion point is exactly the boundary between those two groups, which means the index of the first element that is greater than or equal to value. The new number goes right before that element.

    So the task becomes a scan from the left: stop at the first element that is not smaller than value, and return its index. If no element qualifies, then every element is smaller, and the value belongs after the last one.

    Because the array is sorted, you could find the boundary much faster with binary search. This lesson practises the simple linear version first.

    Step by step

    1. Loop over the indices. The answer is a position, not an element, so the loop uses an index: for (int i = 0; i < nums.Length; i++).
    2. Test nums[i] >= value and return i. The first time the test is true, the sorted order guarantees that i is the right position, and returning stops the search immediately. The test uses >=, not >. If the value is already in the array, the answer is the index of its first occurrence, and > would skip past it.
    3. Return nums.Length after the loop. If the loop finishes, every element is smaller than value, so the value goes at the end. The index just past the last element is exactly nums.Length.

    The solution in C#

    class Solution {
    public int LowerBound(int[] nums, int value) {
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] >= value) {
                return i;
            }
        }
        return nums.Length;
    }
}

    Notes on the C# side:

    • The answer can be nums.Length. That index is one past the end, so it isn't a position you can read from, but it is a valid place to insert. The method only returns the number. Don't use it as nums[answer] without checking.
    • Arrays can't grow. The method doesn't insert anything; it only reports where the value would go. Actually inserting into an array means allocating a new, longer array, whereas a List<int> has an Insert(index, item) method that makes room for you.
    • Length is a property, written with a capital L and no parentheses.

    Here is the first example traced step by step, with value = 4:

    i = 0: nums[0] = 1, is 1 >= 4? no
i = 1: nums[1] = 2, is 2 >= 4? no
i = 2: nums[2] = 3, is 3 >= 4? no
i = 3: nums[3] = 5, is 5 >= 4? yes, so return 3

    Complexity

    Time: O(n). In the worst case, no element is large enough, and the loop makes n comparisons.

    Space: O(1). The method uses the loop index and nothing else.

    Edge cases and common mistakes

    • The value is larger than everything. For [1, 2, 3] and value 9, the loop ends and the method returns 3, the array's length.
    • The value is smaller than everything. For [1, 2, 3] and value -1, the very first element passes the test, and the answer is 0.
    • An empty array. The loop doesn't run, and the method returns 0, which is both the start and the end.
    • Duplicates. For [1, 2, 2, 2, 3] and value 2, the answer is 1, the first 2. Using > would return 4.
    • Returning -1 for "not found". This problem always has an answer. A missing value still has a position where it belongs.
    • Returning the element. return nums[i]; returns the value, not the index.
    • Using the method on an unsorted array. The reasoning depends on the sorted order. In [5, 1, 9], the first element that is at least 3 is the 5, but inserting 3 at index 0 doesn't describe any useful "sorted" position.

    Testing

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