Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find First and Last Position of Element in Sorted Array

MEDIUMProblemSolveExternal Links

Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Examples

Example 1

Input: nums = [5, 7, 7, 8, 8, 10], target = 8

Output: [3, 4]

Explanation: The value 8 appears at indices 3 and 4. Index 3 is its first occurrence and index 4 is its last occurrence, so we return [3, 4].

Example 2

Input: nums = [5, 7, 7, 8, 8, 10], target = 6

Output: [-1, -1]

Explanation: The value 6 does not exist in the array. Since no occurrence is found, we return [-1, -1].

Example 3

Input: nums = [], target = 0

Output: [-1, -1]

Explanation: The array is empty, so no element can be found. Return [-1, -1].

Constraints

  • 0 ≤ nums.length ≤ 10^5
  • -10^9 ≤ nums[i] ≤ 10^9
  • nums is a non-decreasing array
  • -10^9 ≤ target ≤ 10^9

Editorial

Brute Force

Intuition

The simplest approach is to scan the entire array from left to right. The first time we encounter the target, we record that index as the starting position. We continue scanning, and the last time we see the target gives us the ending position.

Think of it like reading a book and looking for every page that mentions a specific word. You start at page 1 and flip through every page. The first mention is your start, and you keep going until you pass the last mention — that's your end. You cannot skip pages because you don't know where the word might appear (even though the book is sorted, you're not taking advantage of that yet).

Step-by-Step Explanation

Let's trace through with nums = [5, 7, 7, 8, 8, 10], target = 8:

Step 1: Initialize first = -1, last = -1. These will store our answer.

Step 2: Check nums[0] = 5. Is 5 == 8? No. Move on.

Step 3: Check nums[1] = 7. Is 7 == 8? No. Move on.

Step 4: Check nums[2] = 7. Is 7 == 8? No. Move on.

Step 5: Check nums[3] = 8. Is 8 == 8? Yes! Since first is still -1, set first = 3. Also update last = 3.

Step 6: Check nums[4] = 8. Is 8 == 8? Yes! first stays 3 (already set). Update last = 4.

Step 7: Check nums[5] = 10. Is 10 == 8? No. Move on.

Step 8: Array fully scanned. Return [first, last] = [3, 4].

Brute Force — Linear Scan for Target Range — Watch how a simple left-to-right scan finds the first and last positions of the target by checking every element.

Algorithm

  1. Initialize first = -1 and last = -1
  2. Iterate through the array from index 0 to n-1:
    • If nums[i] == target:
      • If first == -1, set first = i
      • Set last = i
  3. Return [first, last]

Code

#include <vector>
using namespace std;

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:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        first, last = -1, -1
        for i in range(len(nums)):
            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};
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan every element in the array exactly once. In the worst case (all elements equal to target), we visit all n elements.

Space Complexity: O(1)

We use only two integer variables (first, last) regardless of input size.

Why This Approach Is Not Efficient

The brute force runs in O(n) time, but the problem explicitly requires O(log n) runtime complexity. For n up to 10^5, the linear scan works fine in practice, but it violates the stated constraint and doesn't take advantage of the fact that the array is sorted.

The key insight: a sorted array is tailor-made for binary search. Standard binary search finds any occurrence of the target in O(log n) time. But we need the first and last occurrence specifically.

The trick is to modify binary search slightly:

  • To find the first occurrence: when we find the target, instead of stopping, we continue searching the left half to see if there's an earlier occurrence.
  • To find the last occurrence: when we find the target, we continue searching the right half to see if there's a later occurrence.

Running two modified binary searches gives us both boundaries in O(log n) total time.

Optimal Approach - Two Binary Searches

Intuition

We perform two separate binary searches on the same sorted array:

  1. Find the leftmost (first) occurrence of the target
  2. Find the rightmost (last) occurrence of the target

Finding the first occurrence: In a standard binary search, when nums[mid] == target, we return immediately. To find the first occurrence, when we find the target at mid, we don't stop. Instead, we record mid as a candidate answer and then search the left half (right = mid - 1) to see if there's an even earlier occurrence. If there is, we'll update our answer. If there isn't, our recorded candidate is correct.

Finding the last occurrence: Similarly, when nums[mid] == target, we record mid and then search the right half (left = mid + 1) to see if there's a later occurrence.

Imagine a sorted bookshelf with multiple copies of the same book. To find the leftmost copy, you binary search to any copy, then keep looking left. To find the rightmost copy, you binary search and keep looking right. Each search independently narrows down in O(log n) steps.

Step-by-Step Explanation

Let's trace through with nums = [5, 7, 7, 8, 8, 10], target = 8:

Binary Search 1: Find First Occurrence

Step 1: left = 0, right = 5, result = -1. mid = (0+5)/2 = 2. nums[2] = 7 < 8 → search right half. left = 3.

Step 2: left = 3, right = 5. mid = (3+5)/2 = 4. nums[4] = 8 == 8 → found target! Record result = 4. Search left half for earlier occurrence. right = 3.

Step 3: left = 3, right = 3. mid = (3+3)/2 = 3. nums[3] = 8 == 8 → found target again! Update result = 3. Search left half. right = 2.

Step 4: left = 3, right = 2. left > right → stop. First occurrence = 3.

Binary Search 2: Find Last Occurrence

Step 5: left = 0, right = 5, result = -1. mid = (0+5)/2 = 2. nums[2] = 7 < 8 → search right half. left = 3.

Step 6: left = 3, right = 5. mid = (3+5)/2 = 4. nums[4] = 8 == 8 → found target! Record result = 4. Search right half for later occurrence. left = 5.

Step 7: left = 5, right = 5. mid = (5+5)/2 = 5. nums[5] = 10 > 8 → search left half. right = 4.

Step 8: left = 5, right = 4. left > right → stop. Last occurrence = 4.

Result: [3, 4]

Two Binary Searches — Finding First and Last Position — Watch two modified binary searches in action: the first narrows leftward to find the earliest target, the second narrows rightward to find the latest target.

Algorithm

  1. Find First Position (binary search variant):

    • Initialize left = 0, right = n - 1, result = -1
    • While left ≤ right:
      • mid = left + (right - left) / 2
      • If nums[mid] == target: record result = mid, move right = mid - 1 (search left for earlier)
      • If nums[mid] < target: move left = mid + 1
      • If nums[mid] > target: move right = mid - 1
    • Return result

  2. Find Last Position (binary search variant):

    • Initialize left = 0, right = n - 1, result = -1
    • While left ≤ right:
      • mid = left + (right - left) / 2
      • If nums[mid] == target: record result = mid, move left = mid + 1 (search right for later)
      • If nums[mid] < target: move left = mid + 1
      • If nums[mid] > target: move right = mid - 1
    • Return result

  3. Return [first_position, last_position]

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {findFirst(nums, target), findLast(nums, target)};
    }
    
private:
    int findFirst(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1; // keep searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    
    int findLast(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1; // keep searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
};
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        return [self.find_first(nums, target), self.find_last(nums, target)]
    
    def find_first(self, nums: list[int], target: int) -> int:
        left, right, result = 0, len(nums) - 1, -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                result = mid
                right = mid - 1  # keep searching left
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return result
    
    def find_last(self, nums: list[int], target: int) -> int:
        left, right, result = 0, len(nums) - 1, -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                result = mid
                left = mid + 1  # keep searching right
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return result
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }
    
    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1; // keep searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    
    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1; // keep searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log n)

We perform two binary searches, each taking O(log n) time. Each search halves the search space at every step, so after at most log₂(n) iterations, we converge. Total: 2 × O(log n) = O(log n).

Space Complexity: O(1)

Each binary search uses only a constant number of variables (left, right, mid, result). No additional data structures are needed. The algorithm operates entirely in-place on the input array.