Workspace

Problem workspace

3 day streakD

First & Last Occurrence

MediumBinary SearchSearch & boundaries

The challenge

Return [first index, last index, count] for a target in a sorted array. If absent, return [−1, −1, 0].

Ascending order with duplicates. Empty input returns [−1, −1, 0].

Example

[1, 2, 2, 2, 5, 8], target = 2 → [1, 3, 3].

Use the walkthrough below to inspect the input and each state change.

See Equal range & count, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indicestarget = 2
L = 0 · mid = — · R = 5102122235485
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
5
Step 01 / 11

Find the first value ≥ target

Reset the inclusive candidate interval. The returned boundary is allowed to equal the array length.

left = 0; right = 5

Recorded result so far

Not resolved
View exact input

Input: [1,2,2,2,5,8] · target = 2

Put it into code

Run lower bound and upper bound independently. Their half-open interval contains exactly the target’s occurrences.

Indices are zero-based. C++ uses C++17 or later.

def equal_range(nums, target):
    def boundary(strict):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target or (strict and nums[mid] == target):
                left = mid + 1
            else:
                right = mid - 1
        return left

    first, end = boundary(False), boundary(True)
    if first == end:
        return [-1, -1, 0]
    return [first, end - 1, end - first]  # First, last, count.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap