Find First and Last Position of Element in Sorted Array

LeetCode 34 | Difficulty: Medium

Medium

Problem Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

- `0 <= nums.length <= 10^5`

- `-10^9 <= nums[i] <= 10^9`

- `nums` is a non-decreasing array.

- `-10^9 <= target <= 10^9`

Topics: Array, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 290 ms)

Metric	Value
Runtime	290 ms
Memory	41.2 MB
Date	2021-11-24

Solution

public class Solution {
    public int[] SearchRange(int[] nums, int target) 
     {
    int[] result = new int[2];
    int n = nums.Length;
    result[0] = FindFirst(nums, target, 0, n-1, n);
    result[1] = FindLast(nums, target, 0, n-1, n);
    return result;
}


public int FindFirst(int[] nums, int target, int l, int r, int n)
{
    if(l <=r)
    {
        int mid = l + (r-l)/2;
        
        if((mid == 0 || target > nums[mid-1]) && nums[mid] == target)
        {
            return mid;
        }
        else if(target > nums[mid])
        {
            return FindFirst(nums, target, mid+1, r, n);
        }
        else
        { 
            return FindFirst(nums, target, l, mid-1, n);
        }
    }
    return -1;
}

public int FindLast(int[] nums, int target, int l, int r, int n)
{
    if (l <= r)
    {
        int mid = l + (r - l) / 2;

        if ((mid == n-1 || target < nums[mid + 1]) && nums[mid] == target)
        {
            return mid;
        }
        else if (target < nums[mid])
        {
            return FindLast(nums, target, l,mid-1, n);
        }
        else
        {
            return FindLast(nums, target, mid + 1, r, n);
        }
    }
    return -1;
}
}

📜 2 more C# submission(s)

Submission (2017-10-30) — 495 ms, N/A

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
    
    int i = 0, j = nums.Length - 1;
    while (i < j)
    {
        int mid=(i+j)/2;
        if(nums[mid]<target) i=mid+1;
        else j=mid;
    }
    if (nums.Length ==0 || nums[i] != target) return new int[] { -1, -1};
    int start = i;
    j=nums.Length-1;
    while (i<j)
    {
        int mid=1+(j+i)/2;
        if(nums[mid]>target) j = mid-1;
        else i = mid;
    }
    return new int[] { start, j};
    }
}

Submission (2017-10-29) — 652 ms, N/A

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
   int start = -1, end = -1;
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] == target)
        {
            start = i;
            i++;
            while (i < nums.Length && nums[i] == target)
            {
                i++;
            }
            end = i-1;
        }
    }
    return new int[] { start, end };
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Precisely define what the left and right boundaries represent, and the loop invariant.