Difficulty: Medium Link: April Leetcode Challenge : Day 29
Given an array of integers
nums sorted in ascending order, find the starting and ending position of a given
target is not found in the array, return
Follow up: Could you write an algorithm with
O(log n) runtime complexity?
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Input: nums = , target = 0 Output: [-1,-1]
0 <= nums.length <= 105
-109 <= nums[i] <= 109
numsis a non-decreasing array.
-109 <= target <= 109
A naive straightforward solution can be to iterate over the array and keep track of the first and last positions using two variables. This would be a linear operation and very easy to implement however, this is not an optimal solution. Whenever we are given a sorted array we should be thinking about logarithmic complexity. The property we should be leveraging is the for any element in the sorted array, the elements greater than it would be towards the right side and lesser elements would be towards the left side. Which algorithm enables us to do that?
Sorted Arrays and binary search always go hand in hand. We can modify the vanilla binary search to find the first /last positions by first finding index for target and then finding the index for number slightly bigger than the target.
First, we can perform the standard left binary search (find) on T. Next, we can easily check to see if T exists in N already by checking the value stored at the result of that first search (N[Tleft]). If we don’t find T at that index, then T does not exist in N and we should return [-1, -1].
Otherwise, we still need to find the right end of the range of T values in N. To do this, we can just use find again, this time with the next integer (T + 1). Since this will find the index after the end of the range of T values, we can just move back one position to find the end of the T range.
Alternative approach could be to make two functions, one for finding the lower bound and other for finding the upper bound. Since both would be using the binary search, asymptotic bounds would be within LogN. This approach is simple but a bit redundant and while we can instead do it in a single function by passing an identifier like a flag to indicate if we want to left extreme or the right extreme.
Python has built-in binary search functions for both sides: bisect_left() and bisect_right(). The bisect_left() will return index before all repetitions of
target and the second one: after. So, if these two indexes are equal, it means that we did not found this element, so we return
[-1, -1]. If we found, we return
[l, r - 1].
- Time Complexity: O(log N) for the binary search
- Space Complexity: O(1)