Crack the Backend

Problem Statement

Given a sorted (non-decreasing) array nums and an integer target, return the starting and ending position of target in nums. If target is not found, return [-1, -1]. The array may contain duplicates.

We need the first index where target appears and the last index. So the answer is [lower_bound(target), upper_bound(target) - 1] when target exists, and [-1, -1] if lower_bound points to a different value or past the array.

Key Observations

First index = lower_bound(target): smallest i such that nums[i] >= target. Last index = upper_bound(target) - 1: smallest i such that nums[i] > target, then last = that - 1. Equivalently, last = lower_bound(target + 1) - 1.
After finding left = lower_bound(target), check left < n && nums[left] == target. If not, return [-1, -1]. Otherwise right = lower_bound(target + 1) - 1, return [left, right].
Both bounds are O(log n) with binary search.

Approach

High-level: left = lower_bound(nums, target). If left == n or nums[left] != target, return [-1, -1]. right = lower_bound(nums, target + 1) - 1. Return [left, right]. Implement lower_bound: first index where nums[i] >= target.

Steps:

left = lowerBound(nums, target). If left == nums.length || nums[left] != target, return [-1, -1].
right = lowerBound(nums, target + 1) - 1. Return [left, right].

Implementation

Java

public int[] searchRange(int[] nums, int target) {
    int left = lowerBound(nums, target);

    if (left == nums.length || nums[left] != target) {
        return new int[]{-1, -1};
    }

    int right = lowerBound(nums, target + 1) - 1;
    return new int[]{left, right};
}

int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] < target) {
            lo = mid + 1;
        }
        else {
            hi = mid;
        }
    }

    return lo;
}

Test Cases

Example 1

Input

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

Expected

[3,4]

Explanation

8 at indices 3 and 4.

Complexity Analysis

Time: O(log n).
Space: O(1).

Follow-ups

Count occurrences of target in O(log n).