Find First and Last Position of Element in Sorted Array LeetCode

In many real-world scenarios, efficiently finding the starting and ending positions of a target value in a sorted array is essential. For instance, in systems monitoring, log files record events with timestamps, etc. To investigate issues, it's often necessary to locate the range of log entries for a specific event type. Similar problems arise in other contexts as well, such as searching library databases for books published in a specific year, analyzing customer transaction records for a particular date, identifying specific sensor readings in IoT systems, and querying movie databases for films released in a given year. In all these cases, quick and accurate access to specific data ranges is important.

Key takeaways
The problem involves finding the starting and ending positions of a target value in a sorted array.
The problem can be solved using binary search to achieve O(log n) time complexity.
By slightly modifying binary search, we can locate both the first and last occurrences of the target.
The algorithm has a space complexity of O(1) due to minimal additional space usage.
The approach is ideal for handling large datasets with quick access to data ranges.

Problem statement

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

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

Constraints

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums is a non-decreasing array.
-10⁹ <= target <= 10⁹

Note: Our algorithm's runtime complexity is $O(\log n)$ .

Example

Solution using binary search

To write an algorithm with $O(\log n)$ runtime complexity, we can use two binary searches because they allow us to efficiently find the starting and ending positions of the target value in the sorted array. Instead of performing a linear scan, we take advantage of the properties of binary search to locate the first and last occurrences of the target, achieving runtime complexity. By slightly modifying the conditions within the binary search, we can pinpoint the exact boundaries of the target value.

Algorithm steps

Define the findBound function:
1. Takes three arguments: the array nums, the target value target, and a boolean isFirst to indicate whether to find the first or last occurrence of the target.
Initialize variables:
1. Set begin to 0.
2. Set end to the last index of the array.
Iterate until begin is greater than end:
1. Calculate the middle index mid as (begin + end) / 2.
2. Use the value of the middle element to decide the next steps.
Handle cases based on comparison with target:
1. If nums[mid] == target:
  1. For first occurrence (isFirst is true):
    1. If mid == begin or nums[mid - 1] != target, return mid.
    2. Otherwise, update end = mid - 1.
  2. For last occurrence (isFirst is false):
    1. If mid == end or nums[mid + 1] != target, return mid.
    2. Otherwise, update begin = mid + 1.
2. If nums[mid] > target:
  1. Update end = mid - 1.
3. If nums[mid] < target:
  1. Update begin = mid + 1.
Return -1 If target not found:
1. At the end of the findBound function, return -1 if the target was not found.
Implement the searchRange function:
1. Call findBound with isFirst set to true to find the first occurrence.
2. If the result is $-1$ , return [-1, -1] since the target is not in the array.
3. Otherwise, call findBound with isFirst set to false to find the last occurrence.
4. Return the result as [first_occurrence, last_occurrence].

This algorithm ensures that we efficiently locate the boundaries of the target value in a sorted array with a logarithmic runtime, making it suitable for large datasets.

Illustration

The following illustration shows the algorithm explained above:

def find_bound(nums, target, isFirst):
    # Initialize the beginning and end indices
    begin, end = 0, len(nums) - 1
    # Perform binary search
    while begin <= end:
        # Calculate the middle index
        mid = (begin + end) // 2
        
        # Check if the middle element is the target
        if nums[mid] == target:
            if isFirst:
                # Check if it is the first occurrence
                if mid == begin or nums[mid - 1] != target:
                    return mid
                else:
                    end = mid - 1
            else:
                # Check if it is the last occurrence
                if mid == end or nums[mid + 1] != target:
                    return mid
                else:
                    begin = mid + 1
        elif nums[mid] > target:
            # Adjust end index for left subarray
            end = mid - 1
        else:
            # Adjust begin index for right subarray
            begin = mid + 1
    return -1
def search_range(nums, target):
    # Find the first occurrence of target
    first = find_bound(nums, target, True)
    
    # If the target is not found, return [-1, -1]
    if first == -1:
        return [-1, -1]
    
    # Find the last occurrence of target
    last = find_bound(nums, target, False)
    return [first, last]
# Driver code with examples
examples = [
    ([5, 7, 7, 8, 8, 10], 8),
    ([5, 7, 7, 8, 8, 10], 6),
    ([2, 2, 2, 2, 2], 2),
    ([1, 3, 5, 7], 7),
    ([1, 3, 5, 7], 4)
]
for nums, target in examples:
    result = search_range(nums, target)
    print(f"Array: {nums}, Target: {target}, Result: {result}\n")

Find First and Last Position of Element in Sorted Array

Time complexity

The time complexity of the provided algorithm is $O(\log n)$ because it uses binary search twice.

Space complexity

The space complexity is $O(1)$ due to the use of a constant amount of additional space.

Resources for preparation

To effectively prepare for the coding interview, consider leveraging some of the most popular resources from Educative as follows:

You may consider the following course to enhance your C++ skills based on your experience:

Preparing for operating system and object oriented design and analysis, following are a well suited courses:

Good luck with your preparation!

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is the optimal approach to solve the "Find First and Last Position of Element in Sorted Array" problem?

The optimal approach is to use binary search. First, use binary search to find the first occurrence of the target element, and then use it again to find the last occurrence. This approach has a time complexity of O(log n), which is much faster than a linear scan for large arrays.

How do I handle cases where the target element is not present in the array?

If the target element is not found using binary search, you should return [-1, -1]. During the binary search, if the element at the calculated midpoint does not match the target, adjust the search boundaries accordingly until the element is found or the search space is exhausted.

Why is binary search used instead of a linear search for this problem?

Binary search is used because the array is sorted, making it possible to efficiently narrow down the search space. By leveraging binary search, you can find the first and last positions of the target element in O(log n) time, whereas a linear search would take O(n) time. For large datasets, this difference in performance can be significant.

Free Resources