First and Last Target Position

Interview Problem Interview Medium Array Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.searchRange(nums, target). Return [first_index, last_index] for target in nondecreasing nums, or [-1, -1] when absent. Use O(log n) time.

Starter code

class Solution:
    def searchRange(self, nums, target):
        pass

Test cases

duplicate-run

{
  "args": [
    [
      5,
      7,
      7,
      8,
      8,
      10
    ],
    8
  ]
}

Expected: [3,4]

Wizard outline

Step 1: Initialize Solution.searchRange
Replace the empty starter with the first real state owned by Solution.searchRange. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Missing case
Complete the readable core algorithm for one representative Interview case. Implement lower-bound binary search and reuse it for both target boundaries.
Step 3: Harden the Duplicate Run boundary
Repair the reviewed boundary and pass the complete submission contract. lower_bound(x) returns the first index whose value is at least x. Therefore lower_bound(target) is the first target when present, and lower_bound(target+1)-1 is the final value equal to target.

Footguns and prerequisites

A normal binary search finds an arbitrary occurrence, not necessarily either boundary.
arrays strings two pointers sliding window

Reviewed references

LeetCode 34 — Find First and Last Position of Element in Sorted Array

Practice prerequisites

Find the First True Boundary(opens in a new tab)
Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing first last position as a complete Interview Problem.

Recommended approach and implementation

Use a lower-bound helper for target and target + 1; the second insertion point minus one is the last target index.

Why it works: lower_bound(x) returns the first index whose value is at least x. Therefore lower_bound(target) is the first target when present, and lower_bound(target+1)-1 is the final value equal to target.

class Solution:
    def searchRange(self, nums, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        def lower_bound(value):
            left, right = 0, len(nums)
            while left < right:
                middle = (left + right) // 2
                if nums[middle] < value:
                    left = middle + 1
                else:
                    right = middle
            return left
        first = lower_bound(target)
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        return [first, lower_bound(target + 1) - 1]

Similar exercises

Search a Rotated Sorted Array(opens in a new tab)