algoadvance

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

Problem Statement

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].

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]

Clarifying Questions

  1. Is the array always sorted?
    • Yes, the array is always sorted in non-decreasing order.
  2. What should be returned if the target is not found?
    • Return [-1, -1]
  3. Can we assume the array will contain only integers?
    • Yes.
  4. What are the constraints on the input size?
    • The array can have a size from 0 to 100,000, and the integers can be from -1,000,000 to 1,000,000.

With these clarifications, we can move to our strategy.

Strategy

We can use binary search to find the positions efficiently:

  1. Finding the first occurrence: Use binary search to find the leftmost index of the target.

  2. Finding the last occurrence: Use binary search to find the rightmost index of the target.

Using binary search will help us achieve this in O(log n) time complexity for both operations.

Code

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result(2, -1);
        int left = 0, right = nums.size() - 1;
        
        // Find the first occurrence
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Check if the target is found
        if (left < nums.size() && nums[left] == target) {
            result[0] = left;
        }
        
        left = 0, right = nums.size() - 1; // reset for finding last occurrence
        
        // Find the last occurrence
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // Check if the target is found
        if (right >= 0 && nums[right] == target) {
            result[1] = right;
        }
        
        return result;
    }
};

// Example Usage
int main() {
    Solution solver;
    vector<int> nums = {5,7,7,8,8,10};
    int target = 8;
    vector<int> result = solver.searchRange(nums, target);
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    return 0;
}

Time Complexity

The solution involves performing a binary search twice:

Since each binary search is logarithmic with respect to the size of the array n, the overall time complexity is O(log n). This ensures an efficient search even for the largest possible input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI