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.

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 <= 105

  • -109 <= nums[i] <= 109

  • nums is a non-decreasing array.

  • -109 <= target <= 109

Note: Our algorithm will take O(logn)O(logn) runtime complexity.

Example

canvasAnimation-image
1 of 2

Knowledge test

Now that we have understood the problem, let’s check our knowledge by solving the MCQs given below:

Choose the correct option:

1

Given the sorted array nums = [1, 2, 2, 2, 3, 4, 5] and target = 2, what will be the output of the function that finds the starting and ending position of the target value?

A)

[1, 3]

B)

[2, 4]

C)

[1, 4]

D)

[0, 2]

Question 1 of 30 attempted

Solution

To write an algorithm with O(logn)O(logn) 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

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

  2. Initialize variables:

    1. Set begin to 0.

    2. Set end to the last index of the array.

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

  4. Handle cases cased 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.

  5. Return -1 If target not found:

    1. At the end of the findBound function, return -1 if the target was not found.

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

The following illustration shows the algorithm explained above:

canvasAnimation-image
1 of 7

Code

Let’s have a look at the code for the algorithm we just discussed.

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(logn)O(log n) because it uses binary search twice.

Space complexity

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

Copyright ©2024 Educative, Inc. All rights reserved