DSA First and Last Position

The problem

The first and last position of a target in a sorted list are the smallest and largest indices where the target appears. A sorted list groups every copy of a value together. The answer is the two ends of that group.

An absent target answers -1 at both ends. A target that appears once answers the same index twice. The count of occurrences is the last index minus the first, plus one.

cases = [
    (8, (3, 4)),
    (7, (1, 2)),
    (10, (5, 5)),
    (6, (-1, -1)),
]
nums = [5, 7, 7, 8, 8, 10]
print("nums", nums)
for target, expected in cases:
    print("target", target, "first and last:", expected)

Read one row at a time. The value 8 occupies indices 3 and 4. The value 6 appears nowhere, because the list jumps from 5 to 7, so its row answers -1 twice.

Intuition: find one copy, then expand

The first idea finds any copy of the target. A plain search, or even a guess, lands on one copy quickly. Two walks then spread left and right to the edges of the group.

Expansion is the trap. Its cost depends on how many copies exist. A list made of nothing but the target turns the expansion into a full walk of the list.

nums = [7] * 12
target = 7
mid = len(nums) // 2
print("one copy found at index:", mid)
steps = 0
i = mid
while i >= 0 and nums[i] == target:
    steps += 1
    i -= 1
j = mid + 1
while j < len(nums) and nums[j] == target:
    steps += 1
    j += 1
print("expansion steps:", steps)
print("first:", i + 1, "last:", j - 1)

Twelve equal values cost twelve expansion steps after the copy was already found. The finding was fast and the spreading was not. A group with a million copies makes the same point a million times.

Brute force: one full scan recording both ends

The brute force scans every element once. The first sighting of the target records the first position. Every later sighting updates the last position.

The scan never stops early. Even a target whose group ends at index 2 pays for the rest of the list, because the scan cannot know that no later copy exists until it reaches the end.

def first_last_brute(nums, target):
    first = -1
    last = -1
    compared = 0
    for i, value in enumerate(nums):
        compared += 1
        if value == target:
            if first == -1:
                first = i
            last = i
    return (first, last), compared

nums = [5, 7, 7, 8, 8, 10]
for target in [8, 7, 6]:
    result, compared = first_last_brute(nums, target)
    print("target:", target, "first and last:", result, "compared:", compared)

Every target costs six comparisons, the full list. The cost is flat and predictable. On a million sorted values, flat means a million comparisons for an answer the sorted order could give far sooner.

The optimal solution: two bound searches

The lower bound gives the first position and the upper bound minus one gives the last, so two halving searches find both ends without ever walking the group. That one sentence is the whole method.

The upper bound is the first index whose value is greater than the target. One step back from it lands on the last copy. An absence check comes first, because an absent target has a lower bound that points at a different value or off the end.

def lower_bound(nums, target):
    lo = 0
    hi = len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(nums, target):
    lo = 0
    hi = len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def first_last(nums, target):
    first = lower_bound(nums, target)
    if first == len(nums) or nums[first] != target:
        return (-1, -1)
    last = upper_bound(nums, target) - 1
    return (first, last)

nums = [5, 7, 7, 8, 8, 10]
cases = [(8, (3, 4)), (7, (1, 2)), (10, (5, 5)), (6, (-1, -1))]
for target, expected in cases:
    result = first_last(nums, target)
    print("target", target, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The single-copy row answers index 5 twice. The absent row answers -1 twice, caught by the absence check before the upper bound runs.

Walkthrough: both bounds for target 8

The list is [5, 7, 7, 8, 8, 10]. The lower bound search hunts the first value not less than 8. The upper bound search hunts the first value greater than 8.

nums = [5, 7, 7, 8, 8, 10]
target = 8
lo, hi = 0, len(nums)
print("lower bound search:")
while lo < hi:
    mid = (lo + hi) // 2
    print(" lo:", lo, "hi:", hi, "mid:", mid, "value:", nums[mid])
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid
print(" first:", lo)
lo, hi = 0, len(nums)
print("upper bound search:")
while lo < hi:
    mid = (lo + hi) // 2
    print(" lo:", lo, "hi:", hi, "mid:", mid, "value:", nums[mid])
    if nums[mid] <= target:
        lo = mid + 1
    else:
        hi = mid
print(" upper:", lo, "- last:", lo - 1)

The searches differ in one symbol only. The lower bound test uses less-than, so equal values pull hi down onto the first copy. The upper bound test uses less-than-or-equal, so equal values push lo past the last copy.

Complexity

Each bound search halves its range, so one search costs O(log n) steps for n values and the pair costs O(log n) as well. The scan and the expansion both cost O(n) in the worst case.

Both methods store only a few index variables, so both use O(1) extra space. The bound searches win purely on steps, not on memory.

def bound_steps(nums, target, upper):
    lo = 0
    hi = len(nums)
    steps = 0
    while lo < hi:
        mid = (lo + hi) // 2
        steps += 1
        if (nums[mid] <= target) if upper else (nums[mid] < target):
            lo = mid + 1
        else:
            hi = mid
    return steps

for n in [6, 1000]:
    nums = sorted([8] * (n // 2) + [1] * (n // 2))
    both = bound_steps(nums, 8, False) + bound_steps(nums, 8, True)
    print("values:", n, "- scan comparisons:", n, " two bounds, steps:", both)

Counts beat clocks here. A thousand values cost the scan a thousand comparisons. The two bound searches together cost about twenty steps, and the size of the target's group never enters the count.

Edge cases and pitfalls

Skipping the absence check is the classic bug. For an absent target, the lower bound points at the next larger value. Reading a last position off that index reports a group that does not exist.

An all-equal list stretches the group across the whole list. The bounds answer the two ends of the list itself. The expansion idea from section 2 would walk every element to learn the same thing.

def lower_bound(nums, target):
    lo = 0
    hi = len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(nums, target):
    lo = 0
    hi = len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def first_last(nums, target):
    first = lower_bound(nums, target)
    if first == len(nums) or nums[first] != target:
        return (-1, -1)
    last = upper_bound(nums, target) - 1
    return (first, last)

nums = [5, 7, 7, 8, 8, 10]
print("absent target:", first_last(nums, 6))
print("target above all:", first_last(nums, 99))
print("target below all:", first_last(nums, 1))
print("empty list:", first_last([], 5))
print("single matching value:", first_last([4], 4))
print("single other value:", first_last([4], 9))
print("all equal:", first_last([3, 3, 3, 3], 3))
print("group at the start:", first_last(nums, 5))

The group-at-the-start row answers index 0 twice. A single copy at an edge is still a group. Both bounds agree on its one position.