Find First and Last Position of Element in Sorted Array (LC 34)
You're given an array nums sorted in non-decreasing order and a target value. Find the first and last index at which target occurs.
If target never appears, answer [-1, -1].
Your algorithm must run in O(log n) time.
Worked Examples
nums = [5,7,7,8,8,10], target = 8[3,4]nums = [5,7,7,8,8,10], target = 6[-1,-1]nums = [], target = 0[-1,-1]⚖️Formal Constraints & Bounds
0 <= nums.length <= 105-109 <= nums[i] <= 109numsis a non-decreasing array.-109 <= target <= 109
Core Insight
When nums[mid] == target, do not exit. Record the index and continue searching left (hi = mid - 1) for the first occurrence, or right (lo = mid + 1) for the last.
Real-World Scenario & Production Applications
In search engines and financial transaction ledgers, identical timestamps or duplicate transaction IDs frequently occur. Finding the exact starting index of duplicate events is critical for interval scans.
Step-by-Step Execution Trace Table
First occurrence pass (leftward bias):
| Step | (left, right) | mid | nums[mid] | Result | Action | After |
|---|---|---|---|---|---|---|
| 1 | 0, 6 | 3 | 2 | Match | Record first = 3, push left → right = 2 | 0, 2 |
| 2 | 0, 2 | 1 | 2 | Match | Record first = 1, push left → right = 0 | 0, 0 |
| 3 | 0, 0 | 0 | 1 | Too small | Not a match (1 < 2) → left = 1 | 1, 0 |
| 4 | 1, 0 | — | — | Empty | left > right → stop | returns 1 |
Last occurrence pass (rightward bias, same code with one branch flipped):
| Step | (left, right) | mid | nums[mid] | Result | Action | After |
|---|---|---|---|---|---|---|
| 1 | 0, 6 | 3 | 2 | Match | Record last = 3, push right → left = 4 | 4, 6 |
| 2 | 4, 6 | 5 | 3 | Too large | Not a match (3 > 2) → right = 4 | 4, 4 |
| 3 | 4, 4 | 4 | 2 | Match | Record last = 4, push right → left = 5 | 5, 4 |
| 4 | 5, 4 | — | — | Empty | left > right → stop | returns 4 |
| 1 | left, right = 0, len(nums) - 1 |
| 2 | bound = -1 |
| 3 | while left <= right: |
| 4 | mid = left + (right - left) // 2 |
| 5 | if nums[mid] == target: |
| 6 | bound, right = mid, mid - 1 |
| 7 | elif nums[mid] < target: |
| 8 | left = mid + 1 |
| 9 | else: |
| 10 | right = mid - 1 |
| 11 | return bound |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When an array contains duplicate copies of the target value (e.g. [5, 7, 7, 8, 8, 10] with target = 8), standard exact-match binary search fails because it halts on the very first match it stumbles upon. Depending on array length, that initial encounter could be at index 3 or index 4. To find the exact boundary—the first (leftmost) occurrence or last (rightmost) occurrence—we must convert binary search from an equality-seeker into a boundary-seeking predicate recorder.
🏟️ The Analogy: The Quality Control Inspector on a Conveyor Belt
Imagine an assembly line where defective parts are marked with stamp "8". You need to find the exact moment the machine started producing defects (the first "8"). If you sample a part in the middle and it has stamp "8", you do not stop there. You write down that part's serial number on your clipboard as your "best known suspect so far", and then you immediately walk upstream (towards the left) to see if an even earlier part was stamped with "8". You only stop when you've inspected all upstream candidates.
🔑 Why It Works
By replacing return mid with bound = mid followed by an aggressive boundary push (hi = mid - 1 or lo = mid + 1), we turn binary search into a monotonic boundary finder without sacrificing its efficiency.
Early exit on first target match: Returning immediately upon
nums[mid] == targetfinds an arbitrary occurrence, not the first (or last) occurrence in a duplicate run. You must recordans = midand continue searching left (hi = mid - 1).Separate non-monotonic loops for bounds: Implementing left-bound and right-bound search with different conditional heuristics creates subtle off-by-one bugs. Use a unified binary search helper parameterized by search direction.
Target absent returning
[0, 0]: If the target does not exist in the array, the function must return[-1, -1]. Ensure the validation check verifiesnums[left] == targetbefore returning.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array containing duplicate elements + requirement to find the FIRST (leftmost) or LAST (rightmost) occurrence of a target value.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the leftmost occurrence of target, if it exists, always lies within [left, right]. A match at mid only records a candidate — it never proves leftmost — so the interval keeps narrowing left instead of returning.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Empty/Missing Verification: Forgetting to verify that boundary_index != -1 before returning.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since the array contains duplicates, finding a match at nums[mid] is not sufficient to prove it is the first occurrence. I record mid as a potential answer and continue searching strictly to the left by setting right = mid - 1. This guarantees we isolate the leftmost occurrence in
O(log N)time andO(1)space."
Complexity & Mathematical Proof
O(log N)
Look at the two sequential binary search helper functions (findFirst and findLast): Each executes an independent while loop while lo <= hi:. Each loop halves the search space from N down to 1 in at most ceil(log2 N) iterations doing O(1) work per step. Summing both passes: O(log N) + O(log N) = 2 · O(log N) = O(log N) total time.
O(1) Auxiliary
Look at memory allocation: Both binary search passes run iteratively without recursive call frames (O(1) stack). We store only scalar boundary registers. Output is a 2-element list [first, last]. Auxiliary space is strictly O(1) in-place.
Derivation Progression
Pass 1 (findFirst): O(log N)
First while loop pushes left on matches (hi = mid - 1) to find the earliest target index in O(log N) steps.
Pass 2 (findLast): O(log N)
Second while loop pushes right on matches (lo = mid + 1) to find the latest target index in O(log N) steps.
O(log N) + O(log N) = O(log N)
Two sequential logarithmic passes combine to strictly O(log N) runtime.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative passes with zero recursion frames
O(1) Scalar boundary registers only
O(1) Returns 2-element index pair [first, last]
Boundary Best / Worst Cases
— Both binary search runs execute to logarithmic exhaustion.
— Consistent across all element distributions.
— Target occupies entire array; binary search still halves each step.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The defining signal is "sorted in non-decreasing order" coupled with the requirement to find both the "starting and ending position of a given target value." The presence of non-distinct elements (duplicates) means that exact-match binary search fails: landing on nums[mid] == target gives an arbitrary index inside a cluster of duplicates. To isolate both edges of the cluster, we must decouple the problem into two distinct binary searches with directional tie-breaking bias: one biased leftward (first occurrence) and one biased rightward (last occurrence).
With , an scan expanding outward from a matched midpoint will degrade to worst-case time on arrays like nums = [8, 8, ..., 8], triggering Time Limit Exceeded. Both searches must run in strictly logarithmic time. For both passes, the search bounds are lo = 0 and hi = len(nums) - 1. If the target is not found in the first pass, the second pass can be skipped entirely, immediately returning [-1, -1].
The most frequent trap is writing a single binary search to find any match, followed by a linear while-loop to expand left and right. That naive hybrid collapses to on uniform arrays. Edge cases include empty arrays (nums = []), target completely absent (smaller than nums[0] or greater than nums[-1]), and arrays where target appears as a singleton (first_pos == last_pos).
Find First and Last Position of Element in Sorted Array (LC 34)
You're given an array nums sorted in non-decreasing order and a target value. Find the first and last index at which target occurs.
If target never appears, answer [-1, -1].
Your algorithm must run in O(log n) time.
Worked Examples
nums = [5,7,7,8,8,10], target = 8[3,4]nums = [5,7,7,8,8,10], target = 6[-1,-1]nums = [], target = 0[-1,-1]⚖️Formal Constraints & Bounds
0 <= nums.length <= 105-109 <= nums[i] <= 109numsis a non-decreasing array.-109 <= target <= 109
Core Insight
When nums[mid] == target, do not exit. Record the index and continue searching left (hi = mid - 1) for the first occurrence, or right (lo = mid + 1) for the last.
Real-World Scenario & Production Applications
In search engines and financial transaction ledgers, identical timestamps or duplicate transaction IDs frequently occur. Finding the exact starting index of duplicate events is critical for interval scans.
Step-by-Step Execution Trace Table
First occurrence pass (leftward bias):
| Step | (left, right) | mid | nums[mid] | Result | Action | After |
|---|---|---|---|---|---|---|
| 1 | 0, 6 | 3 | 2 | Match | Record first = 3, push left → right = 2 | 0, 2 |
| 2 | 0, 2 | 1 | 2 | Match | Record first = 1, push left → right = 0 | 0, 0 |
| 3 | 0, 0 | 0 | 1 | Too small | Not a match (1 < 2) → left = 1 | 1, 0 |
| 4 | 1, 0 | — | — | Empty | left > right → stop | returns 1 |
Last occurrence pass (rightward bias, same code with one branch flipped):
| Step | (left, right) | mid | nums[mid] | Result | Action | After |
|---|---|---|---|---|---|---|
| 1 | 0, 6 | 3 | 2 | Match | Record last = 3, push right → left = 4 | 4, 6 |
| 2 | 4, 6 | 5 | 3 | Too large | Not a match (3 > 2) → right = 4 | 4, 4 |
| 3 | 4, 4 | 4 | 2 | Match | Record last = 4, push right → left = 5 | 5, 4 |
| 4 | 5, 4 | — | — | Empty | left > right → stop | returns 4 |
| 1 | left, right = 0, len(nums) - 1 |
| 2 | bound = -1 |
| 3 | while left <= right: |
| 4 | mid = left + (right - left) // 2 |
| 5 | if nums[mid] == target: |
| 6 | bound, right = mid, mid - 1 |
| 7 | elif nums[mid] < target: |
| 8 | left = mid + 1 |
| 9 | else: |
| 10 | right = mid - 1 |
| 11 | return bound |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When an array contains duplicate copies of the target value (e.g. [5, 7, 7, 8, 8, 10] with target = 8), standard exact-match binary search fails because it halts on the very first match it stumbles upon. Depending on array length, that initial encounter could be at index 3 or index 4. To find the exact boundary—the first (leftmost) occurrence or last (rightmost) occurrence—we must convert binary search from an equality-seeker into a boundary-seeking predicate recorder.
🏟️ The Analogy: The Quality Control Inspector on a Conveyor Belt
Imagine an assembly line where defective parts are marked with stamp "8". You need to find the exact moment the machine started producing defects (the first "8"). If you sample a part in the middle and it has stamp "8", you do not stop there. You write down that part's serial number on your clipboard as your "best known suspect so far", and then you immediately walk upstream (towards the left) to see if an even earlier part was stamped with "8". You only stop when you've inspected all upstream candidates.
🔑 Why It Works
By replacing return mid with bound = mid followed by an aggressive boundary push (hi = mid - 1 or lo = mid + 1), we turn binary search into a monotonic boundary finder without sacrificing its efficiency.
Early exit on first target match: Returning immediately upon
nums[mid] == targetfinds an arbitrary occurrence, not the first (or last) occurrence in a duplicate run. You must recordans = midand continue searching left (hi = mid - 1).Separate non-monotonic loops for bounds: Implementing left-bound and right-bound search with different conditional heuristics creates subtle off-by-one bugs. Use a unified binary search helper parameterized by search direction.
Target absent returning
[0, 0]: If the target does not exist in the array, the function must return[-1, -1]. Ensure the validation check verifiesnums[left] == targetbefore returning.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array containing duplicate elements + requirement to find the FIRST (leftmost) or LAST (rightmost) occurrence of a target value.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the leftmost occurrence of target, if it exists, always lies within [left, right]. A match at mid only records a candidate — it never proves leftmost — so the interval keeps narrowing left instead of returning.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Empty/Missing Verification: Forgetting to verify that boundary_index != -1 before returning.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since the array contains duplicates, finding a match at nums[mid] is not sufficient to prove it is the first occurrence. I record mid as a potential answer and continue searching strictly to the left by setting right = mid - 1. This guarantees we isolate the leftmost occurrence in
O(log N)time andO(1)space."
Complexity & Mathematical Proof
O(log N)
Look at the two sequential binary search helper functions (findFirst and findLast): Each executes an independent while loop while lo <= hi:. Each loop halves the search space from N down to 1 in at most ceil(log2 N) iterations doing O(1) work per step. Summing both passes: O(log N) + O(log N) = 2 · O(log N) = O(log N) total time.
O(1) Auxiliary
Look at memory allocation: Both binary search passes run iteratively without recursive call frames (O(1) stack). We store only scalar boundary registers. Output is a 2-element list [first, last]. Auxiliary space is strictly O(1) in-place.
Derivation Progression
Pass 1 (findFirst): O(log N)
First while loop pushes left on matches (hi = mid - 1) to find the earliest target index in O(log N) steps.
Pass 2 (findLast): O(log N)
Second while loop pushes right on matches (lo = mid + 1) to find the latest target index in O(log N) steps.
O(log N) + O(log N) = O(log N)
Two sequential logarithmic passes combine to strictly O(log N) runtime.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative passes with zero recursion frames
O(1) Scalar boundary registers only
O(1) Returns 2-element index pair [first, last]
Boundary Best / Worst Cases
— Both binary search runs execute to logarithmic exhaustion.
— Consistent across all element distributions.
— Target occupies entire array; binary search still halves each step.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The defining signal is "sorted in non-decreasing order" coupled with the requirement to find both the "starting and ending position of a given target value." The presence of non-distinct elements (duplicates) means that exact-match binary search fails: landing on nums[mid] == target gives an arbitrary index inside a cluster of duplicates. To isolate both edges of the cluster, we must decouple the problem into two distinct binary searches with directional tie-breaking bias: one biased leftward (first occurrence) and one biased rightward (last occurrence).
With , an scan expanding outward from a matched midpoint will degrade to worst-case time on arrays like nums = [8, 8, ..., 8], triggering Time Limit Exceeded. Both searches must run in strictly logarithmic time. For both passes, the search bounds are lo = 0 and hi = len(nums) - 1. If the target is not found in the first pass, the second pass can be skipped entirely, immediately returning [-1, -1].
The most frequent trap is writing a single binary search to find any match, followed by a linear while-loop to expand left and right. That naive hybrid collapses to on uniform arrays. Edge cases include empty arrays (nums = []), target completely absent (smaller than nums[0] or greater than nums[-1]), and arrays where target appears as a singleton (first_pos == last_pos).