Coding

First and last occurrence

Asked atLLinkeye

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1].

Input: nums = [5, 7, 7, 8, 8, 10], target = 8 Output: [3, 4] Explanation:The target is 8, and it appears in the array at indices 3 and 4, so the output is [3,4]

Input: nums = [5, 7, 7, 8, 8, 10], target = 6 Output: [-1, -1] Expalantion: The target is 6, which is not present in the array. Therefore, the output is [-1, -1].

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

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

cpp

class Solution{
public:
    vector<int> searchRange(vector<int> &nums, int target) {
        
    }
};

java

class Solution {
    public int[] searchRange(int[] nums, int target) {
    
    }
}

python

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

javascript

class Solution {
    searchRange(nums, target) {
        
    }
}

csharp

public class Solution {
    public int[] SearchRange(int[] nums, int target) {

    }
}

func searchRange(nums []int, target int) []int {
	
}

Stuck? Show a way to structure it+

01Run a lower-bound search for the first index with value at least target.
02Verify the candidate holds target.
03Run a right-biased search for the last index with value at most target.
04Return both positions or minus one values.

Reference answer

Use two biased binary searches rather than stopping at an arbitrary match. For the first occurrence, when nums[mid] is at least target, record mid if equal and continue left; otherwise move low right. For the last occurrence, when nums[mid] is at most target, record mid if equal and continue right; otherwise move high left. Initialize both answers to minus one, which naturally handles an empty array and a missing target. An equivalent formulation uses reusable lower-bound helpers, but two explicit searches make the directional invariant clear. Each search is O(log n), so total time is O(log n) and extra space is O(1). State the sorted non-decreasing precondition; this approach is not valid on arbitrary arrays. Test a target at either boundary, all equal values, and a target between two values.

Then expect these follow-ups

How would you count occurrences from these indices?
Tests: follow-up reasoning
Can you express this using a reusable lower-bound helper?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question