Skip to main content
Talentd

Find First and Last Position of Element in Sorted Array - Solution & Explanation

MediumArrayBinary Search14 min readAsked at: Amazon, Microsoft, Apple +26
Practice this problem

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]

Example 2:

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

Example 3:

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

 

Constraints:

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

Approach Overview

Problem Overview: You are given a sorted integer array and a target value. Return the first and last index where the target appears. If the value does not exist, return [-1, -1]. The challenge is finding both boundaries efficiently rather than scanning the whole array.

Approach 1: Linear Scan (O(n) time, O(1) space)

The straightforward approach iterates through the array from left to right while tracking the first and last positions where the target appears. When you encounter the target for the first time, store the index as the starting position. Continue scanning and update the ending index whenever the value appears again. This approach works for any array but ignores the fact that the array is sorted, so it runs in O(n) time with constant O(1) extra space.

Approach 2: Modified Binary Search for First and Last Position (O(log n) time, O(1) space)

The optimal solution leverages binary search. Instead of stopping when the target is found, the search continues to locate the boundary positions. Run binary search twice: once to find the leftmost occurrence and once to find the rightmost occurrence. For the left boundary, when nums[mid] == target, move the search window to the left half to check if an earlier occurrence exists. For the right boundary, move the search window to the right half after a match.

This works because the array is sorted. Each binary search cuts the search space in half, resulting in O(log n) time. No additional data structures are required, so space complexity remains O(1). The two searches together still maintain logarithmic performance.

Implementation usually creates a helper function that returns a boundary index based on the direction of the search. Many solutions compute the left boundary first, then reuse the same logic with slightly different conditions to find the right boundary.

Recommended for interviews: Interviewers expect the modified binary search solution. A linear scan demonstrates basic correctness but fails to use the sorted property of the input. The two-pass boundary search shows you understand how to adapt binary search patterns, which is a common expectation in array and binary search interview problems.

Approach 1: Binary Search Modified for First and Last Position

The goal is to use the binary search algorithm to achieve O(log n) time complexity. We perform two separate binary searches:

  • First, we use binary search to find the first position of the target.
  • Second, repeat binary search to locate the last position of the target.

This solution uses two modified binary searches, one to find the first occurrence of the target and another to find the last occurrence. The code makes sure to continue searching even if the target is found to ensure the first or last position is located.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) due to binary search. Space Complexity: O(1) as no extra space is used apart from input and output.

Try this approach in the editor →

Approach 2: Binary Search

We can perform two binary searches to find the left boundary and the right boundary.

The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHPKotlin

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Kotlin

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Modified for First and Last Position

Time Complexity: O(log n) due to binary search. Space Complexity: O(1) as no extra space is used apart from input and output.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)Quick baseline solution or when the array is not guaranteed to be sorted
Modified Binary Search (Left and Right Boundaries)O(log n)O(1)Best choice when the array is sorted and interviewers expect logarithmic search

Video Solution

First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34 • NeetCode • 120,232 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find First and Last Position of Element in Sorted Array easy or hard?
The problem is rated Medium difficulty. The logic of binary search is straightforward, but modifying it to detect boundaries instead of stopping at the first match requires careful pointer updates and edge case handling.
Find First and Last Position of Element in Sorted Array Python/Java solution
Python and Java solutions typically implement two helper binary searches: one to find the first occurrence and one for the last occurrence. Both versions maintain left and right pointers and adjust the search boundaries when the target is found. The final result returns the two indices or [-1, -1] if the target is absent.
How to solve Find First and Last Position of Element in Sorted Array in O(log n)?
Use binary search to find boundary positions instead of stopping at the first match. When searching for the first index, continue exploring the left half after finding the target. When searching for the last index, continue exploring the right half. This modification ensures both boundaries are found in logarithmic time.
What is the best approach for Find First and Last Position of Element in Sorted Array?
The best approach is a modified binary search that finds the leftmost and rightmost occurrence separately. Run binary search twice: once to locate the first index where the target appears and once to locate the last index. Each search takes O(log n) time, so the total complexity remains O(log n) with O(1) extra space.
Is Find First and Last Position of Element in Sorted Array asked at Google/Amazon/Meta?
This problem appears frequently in interviews at large tech companies including Google, Amazon, Meta, and Microsoft. It tests your understanding of binary search variations and boundary detection in sorted arrays, which are common patterns in technical interviews.
What data structure is used in Find First and Last Position of Element in Sorted Array?
The primary data structure is a sorted array. The algorithm relies on binary search to efficiently narrow the search range. No additional data structures are required beyond index variables used during the search process.
What is the time complexity of Find First and Last Position of Element in Sorted Array?
The optimal solution runs in O(log n) time using binary search. Two searches are performed—one for the first occurrence and one for the last occurrence—but each halves the search space. Space complexity remains O(1) since the algorithm only uses a few pointers.

Ready to solve this problem?

Practice Find First and Last Position of Element in Sorted Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Target Indices After Sorting Array

Next

First Bad Version