This problem requires identifying the starting and ending positions of a target in a sorted array. The optimal solution uses binary search twice to locate the leftmost and rightmost occurrences efficiently. GhostInterview emphasizes stepwise reasoning and edge case checks, ensuring you consistently achieve O(log n) runtime while handling empty arrays and absent targets.
Problem Statement
Given a sorted array of integers, determine the first and last positions of a specified target value. Return [-1,-1] if the target does not exist in the array. The array may be empty, and integers can range widely.
Your algorithm must achieve O(log n) time complexity, leveraging the sorted property to avoid linear scans. Carefully consider boundary conditions when the target appears at the start or end, and handle duplicates correctly.
Examples
Example 1
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example details omitted.
Example 2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example details omitted.
Example 3
Input: nums = [], target = 0
Output: [-1,-1]
Example details omitted.
Constraints
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums is a non-decreasing array.
- -109 <= target <= 109
Solution Approach
Binary Search for Left Boundary
Perform a standard binary search biased to the left: when nums[mid] >= target, move the high pointer; when nums[mid] < target, move the low pointer. Stop when low meets high to find the first occurrence. This ensures no unnecessary scanning and maintains O(log n) complexity.
Binary Search for Right Boundary
Repeat binary search but biased to the right: when nums[mid] <= target, move the low pointer; when nums[mid] > target, move the high pointer. This identifies the last occurrence. Ensuring correct adjustment of mid and pointers avoids overshooting and captures duplicates correctly.
Combine Results and Validate
After locating potential boundaries, check if the target actually exists at the computed indices. If not found, return [-1,-1]. This final step prevents false positives from empty arrays or targets outside the array range.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(log n) because each boundary search halves the search space. Space complexity is O(1) since no extra structures are used; only pointers and indices are maintained.
What Interviewers Usually Probe
- Check if the candidate identifies both leftmost and rightmost positions using separate searches.
- Listen for correct pointer movement logic to handle duplicates without scanning the entire array.
- Expect clarification on edge cases, such as empty arrays or targets at array boundaries.
Common Pitfalls or Variants
Common pitfalls
- Using a single binary search and assuming the first match is the left boundary.
- Incorrect pointer updates that skip valid duplicates, causing wrong last position.
- Neglecting validation after search, which can return indices when target is absent.
Follow-up variants
- Find the count of target occurrences using the same binary search boundaries approach.
- Return all ranges of multiple target values efficiently in one pass.
- Handle rotated sorted arrays while still identifying first and last positions with modified binary search.
How GhostInterview Helps
- Highlights precise binary search steps to avoid common off-by-one errors in boundary detection.
- Simulates candidate reasoning by checking left and right searches separately, mirroring interview expectations.
- Provides instant feedback on edge cases and empty array handling, reinforcing correct pattern application.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the best strategy to find the first and last positions of a target in a sorted array?
Use two separate binary searches, one biased left for the first occurrence and one biased right for the last occurrence, ensuring O(log n) efficiency.
How do I handle cases where the target is not present?
After computing the left and right boundaries, validate that nums[left] and nums[right] match the target; otherwise return [-1,-1].
Can this approach work for arrays with duplicates?
Yes, separate left-biased and right-biased binary searches correctly identify the extreme indices even when multiple duplicates exist.
What if the array is empty?
Immediately return [-1,-1] since the binary search will find no valid indices, preventing errors.
Does this problem pattern always require O(log n) solutions?
Yes, the pattern 'binary search over the valid answer space' ensures logarithmic performance, which is necessary for interview expectations.
Need direct help with Find First and Last Position of Element in Sorted Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find First and Last Position of Element in Sorted Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the index of a target in a rotated sorted array using a careful binary search that handles pivot shifts.
Open problem page#35 Search Insert PositionFind the correct index for a target value in a sorted array using binary search, or return the position where it should be inserted.
Open problem page#4 Median of Two Sorted ArraysFind the median of two sorted arrays using binary search for efficient O(log(min(m, n))) time complexity.
Open problem page