Find First and Last Position of Element in Sorted Array — Medium Problem & Solution

Problem statement

Given a nums sorted in non-decreasing order, return the first and last index of target as [first, last].

If target is absent, return [-1,-1]. The algorithm must run in O(log n) time.

Example 1

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

Example 2

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

Example 3

Input: nums = [1], target = 1
Output: [0,0]

Constraints

• 1 <= nums.length <= 100000
• -1000000000 <= nums[i], target <= 1000000000
• nums is sorted in non-decreasing order.

How to solve Find First and Last Position of Element in Sorted Array

Both ends come from the same primitive. lowerBound(t) is the first index whose value is at least t; calling it twice pins the whole run of equal values without a second, mirror-image search.

Approach

1. Implement lowerBound(t): binary search over [0, n], moving lo past mid while nums[mid] < t.
2. Let a = lowerBound(target). If a == n or nums[a] != target, the value is absent.
3. Otherwise the answer is [a, lowerBound(target + 1) - 1].

Why it works

nums[i] < t is false for a suffix of a sorted array, so the boundary is unique. lowerBound(target + 1) is the first index past every copy of target, so one less is the last copy. Using target + 1 rather than a separate upper-bound search halves the code, at the cost of assuming integer values — which the problem gives.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• target + 1 can overflow when target is the maximum representable value; widen the type or write a true upper bound.
• Checking nums[a] != target before the a == n guard reads out of bounds.
• A linear scan after finding one occurrence is O(n) and fails the required complexity.

Reference solution

Python

from typing import List

def searchRange(nums: List[int], target: int) -> List[int]:
    def lower(t: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < t:
                lo = mid + 1
            else:
                hi = mid
        return lo

    a = lower(target)
    if a == len(nums) or nums[a] != target:
        return [-1, -1]
    return [a, lower(target + 1) - 1]

JavaScript

var searchRange = function(nums, target) {
    var lower = function(t) {
        var lo = 0, hi = nums.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (nums[mid] < t) lo = mid + 1; else hi = mid;
        }
        return lo;
    };
    var a = lower(target);
    if (a === nums.length || nums[a] !== target) return [-1, -1];
    return [a, lower(target + 1) - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium