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 len(nums) - 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,
len(nums).
Free plan: 30 tutor messages. PRO is unlimited.
Saved
Ctrl + Enter to check
