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

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

Example:

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

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

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

Clarifying Questions

  1. Are the array elements always integers?
    • Yes.
  2. Can the array be empty?
    • Yes.
  3. Is the target value always an integer?
    • Yes.

Strategy

  1. We need to find the first and last positions of the target.
  2. We will use binary search, leveraging the fact that the array is sorted, to achieve O(log n) complexity.
  3. We will perform two binary searches:
    • One to find the first occurrence of the target.
    • One to find the last occurrence of the target.

Steps:

  1. Implement a helper function findFirstPosition that performs binary search to find the first position of the target.
  2. Implement a helper function findLastPosition that performs binary search to find the last position of the target.
  3. If the target is not present, both functions should return -1.
  4. Return the results in an array [firstPosition, lastPosition].

Code

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int firstPos = findFirstPosition(nums, target);
        int lastPos = findLastPosition(nums, target);
        return new int[]{firstPos, lastPos};
    }

    private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                result = mid;
                right = mid - 1;  // Move left to find the first occurrence
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    private int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                result = mid;
                left = mid + 1;  // Move right to find the last occurrence
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

Time Complexity

This approach ensures that we satisfy the requirements of optimal time complexity for this problem.

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