This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #34 (Medium): Find First and Last Position of Element in Sorted Array
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given an array of integers
numssorted in ascending order, find the starting and ending position of a giventargetvalue.If
targetis not found in the array, return[-1, -1].Follow up: Could you write an algorithm with
O(log n)runtime complexity?
Examples:
Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3: Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9numsis a non-decreasing array.-10^9 <= target <= 10^9
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
This problem is very nearly the definition of a binary search. A binary search allows us to find the insertion index for a target number in a sorted array. It's called a "binary" search because in each step it halves the input array and determines in which half the number belongs. Since a binary search is able to eliminate half the remaining array in each iteration, it can accomplish its objective with a time complexity of O(log N).
In this case, however, we don't just want to find out where the target number (T) would be placed in the nums array (N), we want to additionally find out if T actually exists in N, as well as the starting and end indexes.
The standard implementation of a binary search will find the left-most index in which T could be placed, though many languages have functions for both sides. Rather than having to define two sets of functions here, however, we can, with a little creativity, use a single function to find our answer.
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.
Now that we have our range, we can return it.
- Time Complexity: O(log N) for the binary search
- Space Complexity: O(1)
Implementation:
Python has built-in binary search functions for both sides: bisect_left() and bisect_right().
The built-in function for Java, Arrays.binarySearch() does not find the left-most insertion point, so it's easier to define our own binary search function.
C++ can use the built-in function equal_range(), which returns iterator pointers to the range of T values.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var searchRange = function(N, T) {
const find = (target, arr, left=0, right=arr.length) => {
while (left <= right) {
let mid = left + right >> 1
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return left
}
let Tleft = find(T, N)
if (N[Tleft] !== T) return [-1,-1]
return [Tleft, find(T+1, N, Tleft) - 1]
};
Python Code:
(Jump to: Problem Description || Solution Idea)
w/ bisect_left() & bisect_right():
class Solution:
def searchRange(self, N: List[int], T: int) -> List[int]:
Tleft = bisect_left(N, T)
if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
return [Tleft, bisect_right(N, T) - 1]
w/ Custom Binary Search:
class Solution:
def searchRange(self, N: List[int], T: int) -> List[int]:
def find(target, arr, left=0):
right = len(arr) - 1
while left <= right:
mid = left + right >> 1
if arr[mid] < target: left = mid + 1
else: right = mid - 1
return left
Tleft = find(T, N)
if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
return [Tleft, find(T+1, N, Tleft) - 1]
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int[] searchRange(int[] N, int T) {
int Tleft = find(T, N, 0);
if (Tleft == N.length || N[Tleft] != T) return new int[] {-1, -1};
return new int[] {Tleft, find(T+1, N, Tleft) - 1};
}
public int find(int target, int[] arr, int left) {
int right = arr.length - 1;
while (left <= right) {
int mid = left + right >> 1;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
w/ equal_range():
class Solution {
public:
vector<int> searchRange(vector<int>& N, int T) {
pair<vector<int>::iterator,vector<int>::iterator> range;
range = equal_range(N.begin(), N.end(), T);
int Tleft = distance(N.begin(), range.first);
if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
return {Tleft, (int)distance(N.begin(), range.second) - 1};
}
};
w/ Custom Binary Search:
class Solution {
public:
vector<int> searchRange(vector<int>& N, int T) {
int Tleft = find(T, N);
if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
return {Tleft, find(T+1, N, Tleft) - 1};
}
int find(int target, vector<int> arr, int left=0) {
int right = arr.size() - 1;
while (left <= right) {
int mid = left + right >> 1;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-04-29T09:23:56+00:00) Solution: Find First and Last Position of Element in Sorted Array. Retrieved from https://www.scien.cx/2021/04/29/solution-find-first-and-last-position-of-element-in-sorted-array/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.