Find First and Last Position of Element in Sorted Array

Medium
814.

Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array is a medium coding problem on arrays and binary search, asked in Amazon, Microsoft and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find First and Last Position of Element in Sorted Array Solution

Find First and Last Position of Element in Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find First and Last Position of Element in Sorted Array is a medium coding problem on arrays and binary search, asked in Amazon, Microsoft and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Microsoft, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Find First and Last Position of Element in Sorted Array

  1. Hint 1

    Write one helper: the leftmost index where a value could be inserted (the lower bound).

  2. Hint 2

    The first occurrence is lowerBound(target).

  3. Hint 3

    The last occurrence is lowerBound(target + 1) - 1.

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]

Java

private static int lowerBoundRange(int[] nums, long t) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] < t) lo = mid + 1; else hi = mid;
    }
    return lo;
}

public static int[] searchRange(int[] nums, int target) {
    int a = lowerBoundRange(nums, target);
    if (a == nums.length || nums[a] != target) return new int[] { -1, -1 };
    return new int[] { a, lowerBoundRange(nums, (long) target + 1) - 1 };
}

C++

static int lowerBoundRange(vector<int>& nums, long long t) {
    int lo = 0, hi = (int) nums.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < t) lo = mid + 1; else hi = mid;
    }
    return lo;
}

vector<int> searchRange(vector<int>& nums, int target) {
    int a = lowerBoundRange(nums, target);
    if (a == (int) nums.size() || nums[a] != target) return vector<int>{ -1, -1 };
    return vector<int>{ a, lowerBoundRange(nums, (long long) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search