[Leetcode] 34. Find First and Last Position of Element in Sorted Array

Table of Contents

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 \leq \text{nums.length} \leq 10^5$
• $-10^9 \leq \text{nums[i]} \leq 10^9$
• nums is a non-decreasing array
• $-10^9 \leq \text{target} \leq 10^9$

Approach

Because the requirement is to limit the solution to $O(log n)$ complexity, we use binary search. We perform two separate binary searches: one to find the leftmost (startIndex) occurrence of the target and another to find the rightmost (endIndex) occurrence.

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // Call helper functions to find the first and last occurrence of target
  return [findStartIndex(nums, target), findEndIndex(nums, target)];
};

const findStartIndex = (nums, target) => {
  let left = 0,
    right = nums.length - 1;
  // The index of the found target, -1 if not found
  let foundIndex = -1;

  // Binary search loop
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const num = nums[mid];
    const previousNum = nums[mid - 1];
    // If target found, update foundIndex and continue searching to the left
    if (num === target) foundIndex = mid;

    if (num >= target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return foundIndex;
};

const findEndIndex = (nums, target) => {
  let left = 0,
    right = nums.length - 1;
  // The index of the found target, -1 if not found
  let foundIndex = -1;

  // Binary search loop
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const num = nums[mid];
    const nextNum = nums[mid + 1];
    // If target found, update foundIndex and continue searching to the right
    if (num === target) foundIndex = mid;

    if (num > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return foundIndex;
};

Complexity Analysis

Time Complexity

The time complexity is $O(\log n)$, where $n$ is the length of the input array nums. This is because we are halving the search space in each iteration of the while loop.

Space Complexity

The space complexity is $O(1)$ as we only use a constant amount of extra space regardless of the input size.