Find First and Last Position — Problem Statement & Solution Guide
Problem Description
You are provided with a sorted array of integers, nums, and a specific integer value, target. Your task is to determine the indices of the first and last occurrence of target within the array. If the target does not exist in the array, return the array [-1, -1].
The input array is guaranteed to be sorted in non-decreasing order. You must design an algorithm that efficiently locates the boundaries of the target value. Given the potential size of the input, a linear scan is not optimal; consider leveraging the sorted property to achieve logarithmic time complexity.
Return a list or array containing two integers: the index of the first occurrence and the index of the last occurrence of target in nums.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Find First and Last Position"
WHY DOES IT MATTER?
Binary search is a foundational algorithmic pattern that transforms linear search into logarithmic time, enabling efficient solutions for large datasets. Mastering this pattern equips engineers to tackle a wide range of problems—searching, sorting, and even complex data structure operations—while keeping performance within acceptable bounds.
OPTIMIZATION CHALLENGE
The crux is realizing that the target’s occurrences form a contiguous block in a sorted array. By performing two separate binary searches—one for the lower bound and one for the upper bound—you avoid scanning the entire block, reducing time from O(n) to O(log n) while keeping space constant.
REAL-WORLD CONNECTION
Consider a distributed log system where events are timestamped and stored in order. To retrieve all events for a particular user ID, you can perform two binary searches on the sorted log to find the first and last indices of that ID, analogous to locating the first and last positions of a target in an array. This pattern is also used in database index lookups and search engines.
When explaining this in an interview, emphasize the two-phase approach: first find the left boundary, then the right. Show how the loop conditions differ (<= vs <) and how to handle the mid calculation to avoid infinite loops. Demonstrating careful boundary checks showcases attention to detail.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The problem of finding the first and last positions of a target in a sorted array is a classic application of binary search, a divide‑and‑conquer technique that reduces the search space by half at each step. A naive linear scan would examine every element, yielding O(n) time, which becomes prohibitive for large arrays (e.g., millions of elements). By leveraging the array’s sorted property, we can perform two independent binary searches: one to locate the leftmost (first) occurrence and another to locate the rightmost (last) occurrence. Each search runs in O(log n) time, and because the two searches are independent, the overall time complexity remains O(log n). The space complexity stays constant, O(1), as we only use a few index variables.
Binary search for the first occurrence is often called a “lower bound” search: we keep moving left when we see the target to find the earliest index, and we move right when the current element is greater than the target. Conversely, the “upper bound” search for the last occurrence moves right when we see the target to find the latest index, and moves left when the current element is less than the target. These two bounds together give the exact range of indices where the target appears. The key insight is that the sorted order guarantees that all target values form a contiguous block, so the boundaries can be found independently without scanning the entire block.
Interview Questions on This Problem
Q1How would you modify the algorithm if the array were not sorted but you still needed to find the first and last positions of a target?
Without sorting, you cannot rely on binary search. You would need to perform a linear scan to identify the first and last indices, resulting in O(n) time. Alternatively, you could build a hash map of value to list of indices in O(n) time and O(n) space, then query the target’s list to get the min and max indices in O(1).
Q2A candidate suggests using two pointers starting from the ends of the array to find the first and last positions. Why is this approach suboptimal?
Two pointers moving inward would still examine each element until the target is found, leading to O(n) time in the worst case. Binary search guarantees O(log n) time regardless of target distribution, making it far more efficient for large inputs.
Q3During an interview, a candidate returns [-1, -1] when the target is present but at the very beginning of the array. What mistake might they have made?
They likely used a binary search that stops when nums[mid] == target but then incorrectly returns mid without verifying if it is the first or last occurrence. They must continue searching left (or right) to confirm the boundary, otherwise they will miss earlier (or later) duplicates.
Examples
Input
nums = [1, 3, 5, 7, 7, 7, 9, 11], target = 7
Output
[3, 5]
Explanation: The array is sorted. The value 7 appears at indices 3, 4, and 5. The first occurrence is at index 3, and the last occurrence is at index 5. Thus, the result is [3, 5].
Input
nums = [2, 4, 6, 8, 10], target = 5
Output
[-1, -1]
Explanation: The array contains even numbers only. The target 5 is not present in the array. Therefore, the function returns the default not-found indicator [-1, -1].
Input
nums = [1, 1, 1, 1, 1], target = 1
Output
[0, 4]
Explanation: The array consists entirely of the value 1. The first occurrence is at index 0, and the last occurrence is at index 4 (the last element). The result is [0, 4].
Input
nums = [10, 20, 30, 40, 50], target = 30
Output
[2, 2]
Explanation: The target 30 appears exactly once in the array at index 2. Since the first and last occurrences are the same, the result is [2, 2].
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order
- -10^9 <= target <= 10^9
Optimal Approach & Strategy
Perform two binary searches: one to locate the first occurrence (lower bound) and one to locate the last occurrence (upper bound). Each search runs in O(log n) time, yielding an overall O(log n) solution with O(1) extra space.
Brute Force Approach
Scan the array from left to right to find the first index of the target, then continue scanning to find the last index. This takes O(n) time and O(1) space.
Verified Code Solutions
function searchRange(nums, target) {
let first = -1, last = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
if (first === -1) first = i;
last = i;
}
}
return [first, last];
}class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int first = -1, last = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
if (first == -1) first = i;
last = i;
}
}
return {first, last};
}
}class Solution {
public int[] searchRange(int[] nums, int target) {
int first = -1, last = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
if (first == -1) first = i;
last = i;
}
}
return new int[] {first, last};
}
}def searchRange(nums, target):
first, last = -1, -1
for i in range(len(nums)):
if nums[i] == target:
if first == -1: first = i
last = i
return [first, last]function searchRange(nums, target) {
let first = -1, last = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
if (first === -1) first = i;
last = i;
}
}
return [first, last];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.