Log inSign up
mediumLeetCodeNot Started

Find First and Last Position of Element in Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on LeetCode
Lesson

Problem Statement

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]
Explanation: The target value 8 appears first at index 3 and last at index 4.

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Explanation: The target value 6 does not exist in the array.

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]
Explanation: Empty array contains no elements.

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Classic Binary Search on sorted arrays
  • Understanding midpoint calculation to prevent integer overflow low + (high - low) / 2
  • Lower bound and Upper bound concepts

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how binary search can be tailored to find extreme boundaries (lower and upper bounds).
  • Recognize the trap of linear expansion around a single binary search hit.
  • Write clean, overflow-safe binary search loops using low + (high - low) / 2.
  • Structure parameterized helper functions to reuse binary search logic for both left and right bounds.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted input array with potential duplicates.
  • Explicit requirement for O(log N) runtime.
  • Searching for range boundaries, first occurrence, or last occurrence.

Algorithmic Decision Tree:

  • If array is unsorted -> Sort first O(N log N) or linear scan O(N).
  • If array is sorted and need single element -> Standard Binary Search O(log N).
  • If array is sorted with duplicates and need boundary range -> Dual Binary Search (findFirst, findLast) O(log N).

Connected Patterns:

Find Peak Element (Binary Search on Answer)Search in Rotated Sorted ArrayKth Missing Positive Number

1. Brute Force (Linear Scan)

Intuition

Find first occurrence from start, and last occurrence by scanning from end or updating during iteration.

Algorithm

  1. Step 1: Initialize first = -1, last = -1.
  2. Step 2: Iterate i from 0 to nums.length - 1. If nums[i] == target: if first == -1 set first = i; always set last = i.
  3. Step 3: Return [first, last].

Linear Scan from Both Ends (O(N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First occurrence of target 8 found at index 3
Visual state
Values and pointers at this exact step
pointers
S
5
7
7
8
8
10
0
1
2
3
↑ first
4
5
Variables at this step
firstIndex
3
lastIndex
-1
Check / comparison
Scan from index 0 rightwards: nums[3] == 8 is first match
Decision / next transition
Record firstIndex = 3.
Why this step matters

First occurrence of target 8 found at index 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> searchRange(std::vector<int>& nums, int target) {
7 int first = -1, last = -1;
8 for (int i = 0; i < (int)nums.size(); i++) {
9 if (nums[i] == target) {
10 if (first == -1) first = i;
11 last = i;
12 }
13 }
14 return {first, last};
15 }
16};
17
18int main() {
19 Solution sol;
20 std::vector<int> nums = {5, 7, 7, 8, 8, 10};
21 std::vector<int> res = sol.searchRange(nums, 8);
22 std::cout << "Range: [" << res[0] << ", " << res[1] << "]" << std::endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Linear Scan).
  • Space complexity: O(1) — Space complexity for Brute Force (Linear Scan).

Why Brute Force Doesn't Scale:

On a database table with 10 million rows sharing the same timestamp, a linear scan requires reading millions of disk blocks, whereas two B-Tree / binary index lookups take only ~24 comparisons.

With N = 1,000,000, linear scan takes up to 1,000,000 operations; binary search boundary takes at most 2 * 20 = 40 operations.

2. Better (Binary Search + Linear Expansion)

Intuition

Binary search finds an index mid where nums[mid] == target. Then while loops expand left to find the first occurrence and right to find the last occurrence.

Algorithm

  1. Step 1: Perform standard binary search to find any index idx where nums[idx] == target.
  2. Step 2: If not found, return [-1, -1].
  3. Step 3: Expand left: decrement while nums[first - 1] == target. Expand right: increment while nums[last + 1] == target.
  4. Step 4: Return [first, last].

Binary Search + Linear Expansion (O(log N + K) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Target is strictly to the right
Visual state
Values and pointers at this exact step
pointers
S
5
7
7
8
8
10
0
↑ low
1
2
↑ mid
3
4
5
↑ high
Variables at this step
low
0
mid
2
high
5
Check / comparison
Binary search step 1: mid = 2. nums[2] = 7 < target 8
Decision / next transition
7 < 8. Move low = mid + 1 = 3.
Why this step matters

Target is strictly to the right.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> searchRange(std::vector<int>& nums, int target) {
7 int n = nums.size();
8 int low = 0, high = n - 1, foundIdx = -1;
9
10 while (low <= high) {
11 int mid = low + (high - low) / 2;
12 if (nums[mid] == target) {
13 foundIdx = mid;
14 break;
15 } else if (nums[mid] < target) {
16 low = mid + 1;
17 } else {
18 high = mid - 1;
19 }
20 }
21
22 if (foundIdx == -1) return {-1, -1};
23
24 int first = foundIdx, last = foundIdx;
25 while (first > 0 && nums[first - 1] == target) first--;
26 while (last + 1 < n && nums[last + 1] == target) last++;
27
28 return {first, last};
29 }
30};
31
32int main() {
33 Solution sol;
34 std::vector<int> nums = {5, 7, 7, 8, 8, 10};
35 std::vector<int> res = sol.searchRange(nums, 8);
36 std::cout << "Better Range: [" << res[0] << ", " << res[1] << "]" << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Binary Search + Linear Expansion).
  • Space complexity: O(N) — Space complexity for Better (Binary Search + Linear Expansion).

3. Optimal (Dual Independent Binary Searches)

Intuition

To find the first index: - When nums[mid] == target, save mid into ans and set high = mid - 1 to keep searching left. - When nums[mid] < target, set low = mid + 1. - When nums[mid] > target, set high = mid - 1.

To find the last index: - When nums[mid] == target, save mid into ans and set low = mid + 1 to keep searching right. - When nums[mid] < target, set low = mid + 1. - When nums[mid] > target, set high = mid - 1.

Both searches take O(log N) time, totaling 2 * log(N) = O(log N).

Algorithm

  1. Step 1: Call findBound(nums, target, isFirst=true) to locate first position.
  2. Step 2: If first position is -1, target is absent; immediately return [-1, -1].
  3. Step 3: Call findBound(nums, target, isFirst=false) to locate last position.
  4. Step 4: Return [first, last].

Dual Binary Search: lower_bound & upper_bound (O(log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
To find the first occurrence, when nums[mid] < target, advance low
Visual state
Values and pointers at this exact step
pointers
S
5
7
7
8
8
10
0
↑ low
1
2
↑ mid
3
4
5
↑ high
Variables at this step
search
findFirst
low
3
high
5
Check / comparison
Search 1 (findFirst): mid = 2. nums[2] = 7 < target 8
Decision / next transition
Move low = mid + 1 = 3.
Why this step matters

To find the first occurrence, when nums[mid] < target, advance low.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5private:
6 int findBound(const std::vector<int>& nums, int target, bool isFirst) {
7 int n = nums.size();
8 int low = 0, high = n - 1;
9 int bound = -1;
10
11 while (low <= high) {
12 int mid = low + (high - low) / 2;
13 if (nums[mid] == target) {
14 bound = mid;
15 if (isFirst) {
16 high = mid - 1; // Narrow to left
17 } else {
18 low = mid + 1; // Narrow to right
19 }
20 } else if (nums[mid] < target) {
21 low = mid + 1;
22 } else {
23 high = mid - 1;
24 }
25 }
26 return bound;
27 }
28
29public:
30 std::vector<int> searchRange(std::vector<int>& nums, int target) {
31 int first = findBound(nums, target, true);
32 if (first == -1) return {-1, -1};
33 int last = findBound(nums, target, false);
34 return {first, last};
35 }
36};
37
38int main() {
39 Solution sol;
40 std::vector<int> nums = {5, 7, 7, 8, 8, 10};
41 std::vector<int> res = sol.searchRange(nums, 8);
42 std::cout << "Optimal Range: [" << res[0] << ", " << res[1] << "]" << std::endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Dual Independent Binary Searches).
  • Space complexity: O(1) — Space complexity for Optimal (Dual Independent Binary Searches).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Linear Scan)O(N)O(1)Scan the array from left to right to find the first index, and scan from right to left to find the last index.Inspects every element sequentially without exploiting sorted order.
2.Better (Binary Search + Linear Expansion)O(N) worst caseO(1)Use standard binary search to find any occurrence of target, then expand left and right linearly.Linear expansion step across duplicate runs.
3.Optimal (Dual Binary Searches)OptimalO(log N)O(1)Run two separate O(log N) binary search routines: one finds leftmost occurrence, the other finds rightmost occurrence.Theoretical minimum comparison lower bound for boundary search.

Common Pitfalls & Crucial Edge Cases

Linear expansion after finding one index

If the array has 100,000 copies of target, expanding linearly from the center takes O(N) operations and gets Time Limit Exceeded (TLE).

Integer overflow in mid calculation

Using (low + high) / 2 instead of low + (high - low) / 2 in C++/Java when indices exceed 230.

Missing the early exit optimization

If first == -1, running the second search is redundant; return [-1, -1] right away.

Crucial Edge Cases to Validate:

  • Empty Array (nums = []): Both searches immediately return -1, outputting [-1, -1].
  • Target Not Present (nums = [5,7,7,8,8,10], target = 6): Both searches exit without finding match -> [-1, -1].
  • All Elements Identical to Target (nums = [8,8,8,8,8], target = 8): Left bound finds 0 in O(log N), right bound finds 4 in O(log N). Total runtime remains strictly O(log N).
  • Single Element Match / Mismatch (nums = [1], target = 1 -> [0, 0]; target = 2 -> [-1, -1]).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Write a helper function with a boolean flag isFirst to demonstrate DRY (Don't Repeat Yourself) code principles.
  2. Mention lower_bound / upper_bound in C++ STL as alternative equivalents, but implement the raw binary search to prove algorithmic mastery.
  3. State clearly that if the first boundary search returns -1, the element is absent and the second search can be skipped.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does finding a target with binary search and expanding linearly fail the problem constraints in the worst case?

2.In the binary search helper to find the FIRST occurrence, what update is made when nums[mid] == target?

3.What is the overall time and space complexity of the dual binary search approach?

Back to DSA Sheet