Find First and Last Position of Element in Sorted Array
MedPrompt
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
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 <= 105-109 <= nums[i] <= 109numsis a non-decreasing array.-109 <= target <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through the entire array. We can use two variables, one to store the index of the first occurrence and another for the last. We traverse the array, and whenever we find the target element, we update these variables.
Algorithm
- Initialize a result array
ansto[-1, -1]. - Iterate through the
numsarray from left to right with indexi. - If
nums[i]equals thetarget:- If
ans[0]is still-1, it means this is the first time we've seen the target. Setans[0] = i. - Always update the last seen position:
ans[1] = i.
- If
- After the loop finishes, return the
ansarray.
Walkthrough
This method involves a single pass through the array from left to right. We keep track of the first and last indices where the target element is found. The first time we encounter the target, we record its index in a variable, say first. For every occurrence of the target, we update another variable, last. If the loop completes and we never found the target, the initial values indicating 'not found' (e.g., -1) are returned.
class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[]{-1, -1}; // Find the first occurrence for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { result[0] = i; break; } } // If the first occurrence was not found, the element doesn't exist. if (result[0] == -1) { return result; } // Find the last occurrence, searching backwards for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] == target) { result[1] = i; break; } } return result; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Cons
Inefficient for large arrays.
Time complexity of O(n) does not meet the problem's requirement of O(log n).
It doesn't leverage the fact that the input array is sorted.
Since the array is sorted and the time complexity requirement is O(log n), binary search is the indicated approach. A standard binary search finds if an element exists, but we need its first and last positions. We can achieve this by running two modified binary searches: one to find the leftmost (first) occurrence and another to find the rightmost (last) occurrence.
Algorithm
- Define a function
searchRangethat will return the final[-1, -1]or[first, last]array. - Inside
searchRange, call a helper function,findFirst, to find the leftmost index of thetarget. - If
findFirstreturns-1, the target is not in the array, so return[-1, -1]immediately. - If the target was found, call another helper function,
findLast, to find the rightmost index of thetarget. - Return the results from
findFirstandfindLastin an array.
findFirst (Left-Biased Binary Search):
- Perform a binary search.
- If
nums[mid] == target, we've found a potential first occurrence. Storemidas the answer and continue searching in the left half (high = mid - 1) to find an even earlier one. - If
nums[mid] < target, search in the right half (low = mid + 1). - If
nums[mid] > target, search in the left half (high = mid - 1).
findLast (Right-Biased Binary Search):
- Perform a binary search.
- If
nums[mid] == target, we've found a potential last occurrence. Storemidas the answer and continue searching in the right half (low = mid + 1) to find a later one. - If
nums[mid] < target, search in the right half (low = mid + 1). - If
nums[mid] > target, search in the left half (high = mid - 1).
Walkthrough
This approach consists of two main parts: finding the first position and finding the last position of the target. Both can be found using a variation of the standard binary search algorithm. We design one search to be 'left-biased', meaning it continues to search the left part of the array even after finding the target, to ensure it finds the absolute first occurrence. The second search is 'right-biased', continuing to search the right part to find the absolute last occurrence.
class Solution { public int[] searchRange(int[] nums, int target) { int first = findFirst(nums, target); if (first == -1) { return new int[]{-1, -1}; } int last = findLast(nums, target); return new int[]{first, last}; } // Helper function to find the first occurrence of the target private int findFirst(int[] nums, int target) { int index = -1; int low = 0; int high = nums.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { index = mid; // Potential answer found high = mid - 1; // Continue searching on the left side } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return index; } // Helper function to find the last occurrence of the target private int findLast(int[] nums, int target) { int index = -1; int low = 0; int high = nums.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { index = mid; // Potential answer found low = mid + 1; // Continue searching on the right side } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return index; }}Complexity
Time
O(log n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(log n), which is very efficient for large datasets.
Fully utilizes the sorted property of the array.
Cons
Slightly more complex to implement and reason about than a simple linear scan.
Requires careful handling of boundary conditions and loop termination in the binary searches.
Solutions
Solution
public class Solution { public int[] SearchRange(int[] nums, int target) { int l = Search(nums, target); int r = Search(nums, target + 1); return l == r ? new int[] { -1, -1 } : new int[] { l, r - 1 }; } private int Search(int[] nums, int x) { int left = 0, right = nums.Length; while (left < right) { int mid = (left + right) >>> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; }}boolean check ( int x ) { } int search ( int left , int right ) { while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if ( check ( mid )) { left = mid ; } else { right = mid - 1 ; } } return left ; }/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function (nums, target) { function search(x) { let left = 0, right = nums.length; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } const l = search(target); const r = search(target + 1); return l == r ? [-1, -1] : [l, r - 1]; };class Solution {public: vector<int> searchRange(vector<int> &nums, int target) { int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin(); if (l == r) return {-1, -1}; return {l, r - 1}; }};''' >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2) 3 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2+1) 6 >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2) 6 >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2+1) 6 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 0) 0 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 1) 0 # below, even single value for 2, after +1 the index will be different >>> bisect.bisect_left([1,2,3,4,5], 2) 1 >>> bisect.bisect_left([1,2,3,4,5], 2+1) 2 ''' import bisect class Solution : def searchRange ( self , nums : List [ int ], target : int ) -> List [ int ]: l = bisect_left ( nums , target ) r = bisect_left ( nums , target + 1 ) return [ - 1 , - 1 ] if l == r else [ l , r - 1 ] ############ class Solution : def searchRange ( self , nums : List [ int ], target : int ) -> List [ int ]: def findRange ( to_left ): l , r = 0 , len ( nums ) - 1 m = 0 while l <= r : m = l + ( r - l ) // 2 if nums [ m ] < target : l = m + 1 elif nums [ m ] > target : r = m - 1 elif to_left and m > 0 and nums [ m - 1 ] == nums [ m ]: # so now nums[m] == target, but maybe not the leftmost or rightmost r = m - 1 elif not to_left and m + 1 < len ( nums ) and nums [ m + 1 ] == nums [ m ]: # so now nums[m] == target, but maybe not the leftmost or rightmost l = m + 1 else : return m if m < len ( nums ) and nums [ m ] == target : # 1. cover not-found, # or 2. cover input=[3] and target=3, first and last both 0, return [0,0] return m else : return - 1 return [ findRange ( True ), findRange ( False )]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.