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.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check