Jobs

Interviews

Discussions

Find First and Last Position of Element in Sorted Array

Medium

Amazon

14 views

Topics:

ArraysBinary Search

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

Find First and Last Position of Element in Sorted Array

Medium

Amazon

14 views

Topics:

ArraysBinary Search

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values that can be present in the `nums` array?
Can the input array `nums` be empty or null?
If the target is not found, should I return `[-1, -1]` specifically, or is there another specified return value for this case?
If the target appears multiple times, are we guaranteed that the array is sorted in non-decreasing order?
Can I assume that the input array `nums` is already sorted in ascending order?

Brute Force Solution

Approach

The brute-force method to find the first and last spot of a number in a sorted list is to simply look at each number in the list, one by one. We check each number to see if it is equal to the target number we are searching for.

Here's how the algorithm would work step-by-step:

Start by looking at the very first number in the list.
Check if this number is the target number we are searching for.
If it is, remember this spot as a possible first and last spot and keep going.
Move to the next number in the list.
Again, check if this number is the target number.
If it is, and we haven't found any target numbers yet, mark this as both the first and last spot.
If we've already found the target number, update the last spot to be the current spot.
Continue this process of checking each number one by one until you reach the end of the list.
Once you reach the end of the list, if you never found the target number, report that it's not in the list. If you found the number at least once, report the first and last spots you found.

Code Implementation

def find_first_and_last_brute_force(sorted_numbers, target_number):
    first_position = -1
    last_position = -1

    for index in range(len(sorted_numbers)):
        # Check each number to see if it equals the target
        if sorted_numbers[index] == target_number:

            # If we haven't found the target yet, mark the first position
            if first_position == -1:
                first_position = index
                last_position = index

            # Otherwise, update the last position
            else:
                last_position = index

    return [first_position, last_position]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. In each iteration, a constant-time comparison is performed to check if the current element equals the target value. The number of operations is directly proportional to the size of the input array. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided brute-force algorithm iterates through the input array and maintains two variables, one for the first index and one for the last index where the target element is found. These variables store integer values representing array indices. Since the space used for these variables does not depend on the size of the input array (N), the auxiliary space is constant.

Optimal Solution

Approach

Because the numbers are sorted, we can use a very efficient search strategy. Instead of checking each number individually, we repeatedly divide the search area in half to quickly narrow down the location of the number we are looking for and where it starts and ends.

Here's how the algorithm would work step-by-step:

First, use the divide-in-half search to find the very first occurrence of the number.
To do this, if the middle number is too small, only look at the right half. If the middle number is bigger, only look at the left half. If the middle number is our target, check if the number before it is also our target. If it is, keep searching on the left half.
Next, do the same divide-in-half search to find the very last occurrence of the number.
If the middle number is too small, only look at the right half. If the middle number is bigger, only look at the left half. If the middle number is our target, check if the number after it is also our target. If it is, keep searching on the right half.
Once you've found both the first and last positions, you have your answer.

Code Implementation

def find_first_and_last_position(nums, target):
    def find_first(nums, target):
        left_index = 0
        right_index = len(nums) - 1
        first_position = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if nums[middle_index] < target:
                left_index = middle_index + 1
            elif nums[middle_index] > target:
                right_index = middle_index - 1
            else:
                # Potential first occurence found.
                first_position = middle_index

                # Search left side for the first.
                right_index = middle_index - 1

        return first_position

    def find_last(nums, target):
        left_index = 0
        right_index = len(nums) - 1
        last_position = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if nums[middle_index] < target:
                left_index = middle_index + 1
            elif nums[middle_index] > target:
                right_index = middle_index - 1
            else:
                # Potential last occurence found.
                last_position = middle_index

                # Search right side for the last.
                left_index = middle_index + 1

        return last_position

    first_position = find_first(nums, target)
    last_position = find_last(nums, target)

    return [first_position, last_position]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm employs binary search to find both the first and last occurrences of the target value. Binary search repeatedly halves the search interval. Finding the first occurrence takes O(log n) time, and finding the last occurrence also takes O(log n) time. Since we perform two independent binary searches, the overall time complexity is O(log n) + O(log n), which simplifies to O(log n).

Space Complexity

O(1) – The algorithm described uses a binary search approach, repeatedly dividing the search space in half. It only requires a few constant space variables to store the start, end, and middle indices for the search. The space used does not depend on the input size N (the number of elements in the sorted array). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty array	Return [-1, -1] if the input array is empty as the target cannot exist.
Target is smaller than the smallest element in the array	Binary search will not find the target and return [-1, -1].
Target is larger than the largest element in the array	Binary search will not find the target and return [-1, -1].
Array with one element and target matches the element	Return [0, 0] if the single element matches the target.
Array with one element and target does not match the element	Return [-1, -1] if the single element does not match the target.
Array with all elements equal to the target	Binary search to find the leftmost and rightmost indices will correctly identify the start and end positions.
Target exists only once in the array	Binary search for leftmost and rightmost will return the same index for both, resulting in [index, index].
Large array sizes to consider potential time complexity bottlenecks	Binary search ensures a logarithmic time complexity, handling large array sizes efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values that can be present in the `nums` array?
Can the input array `nums` be empty or null?
If the target is not found, should I return `[-1, -1]` specifically, or is there another specified return value for this case?
If the target appears multiple times, are we guaranteed that the array is sorted in non-decreasing order?
Can I assume that the input array `nums` is already sorted in ascending order?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first number in the list.
Check if this number is the target number we are searching for.
If it is, remember this spot as a possible first and last spot and keep going.
Move to the next number in the list.
Again, check if this number is the target number.
If it is, and we haven't found any target numbers yet, mark this as both the first and last spot.
If we've already found the target number, update the last spot to be the current spot.
Continue this process of checking each number one by one until you reach the end of the list.
Once you reach the end of the list, if you never found the target number, report that it's not in the list. If you found the number at least once, report the first and last spots you found.

Code Implementation

def find_first_and_last_brute_force(sorted_numbers, target_number):
    first_position = -1
    last_position = -1

    for index in range(len(sorted_numbers)):
        # Check each number to see if it equals the target
        if sorted_numbers[index] == target_number:

            # If we haven't found the target yet, mark the first position
            if first_position == -1:
                first_position = index
                last_position = index

            # Otherwise, update the last position
            else:
                last_position = index

    return [first_position, last_position]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, use the divide-in-half search to find the very first occurrence of the number.
To do this, if the middle number is too small, only look at the right half. If the middle number is bigger, only look at the left half. If the middle number is our target, check if the number before it is also our target. If it is, keep searching on the left half.
Next, do the same divide-in-half search to find the very last occurrence of the number.
If the middle number is too small, only look at the right half. If the middle number is bigger, only look at the left half. If the middle number is our target, check if the number after it is also our target. If it is, keep searching on the right half.
Once you've found both the first and last positions, you have your answer.

Code Implementation

def find_first_and_last_position(nums, target):
    def find_first(nums, target):
        left_index = 0
        right_index = len(nums) - 1
        first_position = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if nums[middle_index] < target:
                left_index = middle_index + 1
            elif nums[middle_index] > target:
                right_index = middle_index - 1
            else:
                # Potential first occurence found.
                first_position = middle_index

                # Search left side for the first.
                right_index = middle_index - 1

        return first_position

    def find_last(nums, target):
        left_index = 0
        right_index = len(nums) - 1
        last_position = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if nums[middle_index] < target:
                left_index = middle_index + 1
            elif nums[middle_index] > target:
                right_index = middle_index - 1
            else:
                # Potential last occurence found.
                last_position = middle_index

                # Search right side for the last.
                left_index = middle_index + 1

        return last_position

    first_position = find_first(nums, target)
    last_position = find_last(nums, target)

    return [first_position, last_position]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return [-1, -1] if the input array is empty as the target cannot exist.
Target is smaller than the smallest element in the array	Binary search will not find the target and return [-1, -1].
Target is larger than the largest element in the array	Binary search will not find the target and return [-1, -1].
Array with one element and target matches the element	Return [0, 0] if the single element matches the target.
Array with one element and target does not match the element	Return [-1, -1] if the single element does not match the target.
Array with all elements equal to the target	Binary search to find the leftmost and rightmost indices will correctly identify the start and end positions.
Target exists only once in the array	Binary search for leftmost and rightmost will return the same index for both, resulting in [index, index].
Large array sizes to consider potential time complexity bottlenecks	Binary search ensures a logarithmic time complexity, handling large array sizes efficiently.