2Brute2Best
🔥0

Find First and Last Position of Element in Sorted Array

Medium·LeetCode #34 Pro OnlyMedium
LeetCode
01

Problem Statement

You are given an array nums sorted from smallest to largest. Values can repeat. You are also given a number target.

Return the first and last index where target appears, as [first, last]. If target doesn't appear at all, return [-1, -1].

Your solution must run in O(log n) time.

Input

A sorted integer array nums (possibly with duplicates, possibly empty) and an integer target.

Output

[first, last] — the leftmost and rightmost positions of target, or [-1, -1] if it's absent.

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

The two 8s are at indexes 3 and 4.

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

There is no 6 in the array.

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

An empty array contains nothing.

Constraints
  • • 0 ≤ nums.length ≤ 10^5
  • • −10^9 ≤ nums[i] ≤ 10^9
  • • nums is sorted in non-decreasing order
  • • −10^9 ≤ target ≤ 10^9
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“sorted, values can repeat”
→ All copies of target form one block → find its two edges.
“first and last position”
→ Two boundaries: first ≥ target and first > target.
“O(log n)”
→ Even walking the block is too slow; each edge needs its own binary search.
03

Approach Complexity Ladder

Brute Force — scan the whole arrayO(N)O(1)

Walk left to right; record the first and last match

Better — binary search, then expandO(log N + k)O(1)

Binary search for any copy, then walk left and right to the edges

Optimal — two boundary searchesO(log N)O(1)

First index ≥ target, and first index > target minus 1

Brute Force Intuition

Go through every element. The first time you see target, save its index as first. Every time you see it, update last.

Recognition rule for this sub-pattern:

Sorted array; find a value, or the first/last position where a condition becomes true.
Remember this · Binary Search
Trigger
Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).
Think
Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.
Key question
What is my check function, and is it monotonic?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track
C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track
Sqrt(x)