#34 Find First and Last Position of Element in Sorted Array

frequently reported atMeta LinkedIn Apple Bloomberg Amazon Microsoft

the problem

In plain words

Given a sorted array (duplicates allowed), return [first, last] index of target, or [-1, -1] if absent. Must be O(log n).

in nums = [5,7,7,8,8,10], target = 8

out [3,4]

in nums = [5,7,7,8,8,10], target = 6

out [-1,-1]

in nums = [], target = 0

out [-1,-1]

0 ≤ n ≤ 10⁵
-10⁹ ≤ nums[i], target ≤ 10⁹
Sorted non-decreasing

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBinary search (exact & bounds)

first = lower bound (first ≥ target); last = upper bound (first > target) minus one. Two O(log n) searches, no scanning across the run of duplicates.

solutions

From brute force to optimal

Record the first and last index where nums[i] == target.

Scan all i.
Set first on the first hit, update last on every hit.

timeO(n)

Visits every element.

spaceO(1)

Two indices.

javajava.util.*

1class Solution {2    public int[] searchRange(int[] nums, int target) {3        int first = -1, last = -1;4        for (int i = 0; i < nums.length; i++) {5            if (nums[i] == target) {6                if (first == -1) first = i;7                last = i;8            }9        }10        return new int[] {first, last};11    }12}

On a hit, remember it and keep searching left (for first) or right (for last).

Run lo ≤ hi search twice.
On equality: ans = mid; then hi = mid − 1 (leftmost) or lo = mid + 1 (rightmost).

timeO(log n)

Two full binary searches.

spaceO(1)

A few integers.

javajava.util.*

1class Solution {2    public int[] searchRange(int[] nums, int target) {3        return new int[] {find(nums, target, true), find(nums, target, false)};4    }5 6    /** Classic lo <= hi search that keeps going after a hit, leaning left or right. */7    private int find(int[] nums, int target, boolean leftmost) {8        int lo = 0, hi = nums.length - 1, ans = -1;9        while (lo <= hi) {10            int mid = lo + (hi - lo) / 2;11            if (nums[mid] == target) {12                ans = mid;                                   // remember it, keep searching13                if (leftmost) hi = mid - 1;14                else lo = mid + 1;15            } else if (nums[mid] < target) {16                lo = mid + 1;17            } else {18                hi = mid - 1;19            }20        }21        return ans;22    }23}

Two boundary searches with the lo < hi template; no special case for the hit.

first = lowerBound(target).
If first == n or nums[first] ≠ target → [-1, -1].
last = upperBound(target) − 1.

timeO(log n)

Two binary searches of log n each.

spaceO(1)

A few integers.

javajava.util.*

1class Solution {2    public int[] searchRange(int[] nums, int target) {3        int first = lowerBound(nums, target);               // first index with value >= target4        if (first == nums.length || nums[first] != target) return new int[] {-1, -1};5        int last = upperBound(nums, target) - 1;             // (first index with value > target) - 16        return new int[] {first, last};7    }8 9    private int lowerBound(int[] a, int t) {10        int lo = 0, hi = a.length;11        while (lo < hi) {12            int mid = lo + (hi - lo) / 2;13            if (a[mid] >= t) hi = mid;      // mid could be the first copy: keep it14            else lo = mid + 1;              // too small: drop mid and everything left of it15        }16        return lo;17    }18 19    private int upperBound(int[] a, int t) {20        int lo = 0, hi = a.length;21        while (lo < hi) {22            int mid = lo + (hi - lo) / 2;23            if (a[mid] > t) hi = mid;       // bigger than t: the boundary is mid or left of it24            else lo = mid + 1;              // <= t (copies too): the boundary is right of mid25        }26        return lo;27    }28}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int[] searchRange(int[] nums, int target) {3        int first = lowerBound(nums, target);               // first index with value >= target4        if (first == nums.length || nums[first] != target) return new int[] {-1, -1};5        int last = upperBound(nums, target) - 1;             // (first index with value > target) - 16        return new int[] {first, last};7    }8 9    private int lowerBound(int[] a, int t) {10        int lo = 0, hi = a.length;11        while (lo < hi) {12            int mid = lo + (hi - lo) / 2;13            if (a[mid] >= t) hi = mid;      // mid could be the first copy: keep it14            else lo = mid + 1;              // too small: drop mid and everything left of it15        }16        return lo;17    }18 19    private int upperBound(int[] a, int t) {20        int lo = 0, hi = a.length;21        while (lo < hi) {22            int mid = lo + (hi - lo) / 2;23            if (a[mid] > t) hi = mid;       // bigger than t: the boundary is mid or left of it24            else lo = mid + 1;              // <= t (copies too): the boundary is right of mid25        }26        return lo;27    }28}

in the room

How to say it in the interview

talk track

Mention the trap first: "find any 8 then expand both ways" is O(n) when the array is all 8s.
Present lower/upper bound as reusable helpers — clean code scores points.

traps

Expanding outward from one match: correct but O(n) worst case.
Forgetting the first == n check before reading nums[first].

what they ask next

Follow-ups

How many times does target occur?

upperBound − lowerBound, in O(log n).

before you submit

Edge cases to test

Empty array → [-1, -1].
Every element is the target: [2, 2, 2, 2] → [0, 3] — a walk from one hit would be O(n).
Target missing but between two values: lower bound lands on a different value, so check nums[first] == target.

practise next