Introduction

In this blog post, we will explore how to solve the LeetCode problem "34" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 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 <= 105 -109 <= nums[i] <= 109 nums is a non-decreasing array. -109 <= target <= 109

Explanation

• Binary Search for First Occurrence: Use binary search to find the leftmost occurrence of the target value. If the target is not found, return [-1, -1].
  • Binary Search for Last Occurrence: Use binary search again to find the rightmost occurrence of the target value.
  • Combine Results: Return the indices of the first and last occurrences as a list.

• Runtime Complexity: O(log n), Storage Complexity: O(1)

Code

    def searchRange(nums: list[int], target: int) -> list[int]:
    """
    Finds the starting and ending position of a given target value in a sorted array.

    Args:
        nums: A list of integers sorted in non-decreasing order.
        target: The target value to search for.

    Returns:
        A list containing the starting and ending positions of the target value.
        If the target is not found, returns [-1, -1].
    """

    def find_first(nums: list[int], target: int) -> int:
        """
        Finds the index of the first occurrence of the target value using binary search.
        """
        left, right = 0, len(nums) - 1
        index = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
            if nums[mid] == target:
                index = mid
        return index

    def find_last(nums: list[int], target: int) -> int:
        """
        Finds the index of the last occurrence of the target value using binary search.
        """
        left, right = 0, len(nums) - 1
        index = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
            if nums[mid] == target:
                index = mid
        return index

    first = find_first(nums, target)
    if first == -1:
        return [-1, -1]
    last = find_last(nums, target)
    return [first, last]