Jobs

Interviews

Discussions

Find First and Last Position of Element in Sorted Array

Medium

Google

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

For example:

nums = [5,7,7,8,8,10], target = 8 should return [3,4]
nums = [5,7,7,8,8,10], target = 6 should return [-1,-1]
nums = [], target = 0 should return [-1,-1]

Explain your approach, its time complexity, and handle any potential edge cases.

Find First and Last Position of Element in Sorted Array

Medium

Google

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

For example:

nums = [5,7,7,8,8,10], target = 8 should return [3,4]
nums = [5,7,7,8,8,10], target = 6 should return [-1,-1]
nums = [], target = 0 should return [-1,-1]

Explain your approach, its time complexity, and handle any potential edge cases.

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 are the possible value ranges for the integers in the input array and the target value? Could they be negative?
What should I return if the input array is null or empty?
If the target value appears multiple times consecutively, should I return the first and last index of *all* occurrences, or is any valid range acceptable?
Is the input array guaranteed to be sorted in ascending order, or could it be descending?
Are there any memory constraints I should be aware of, given the potential size of the input array?

Brute Force Solution

Approach

Imagine searching a phone book for someone's name. With the brute force way, you'd simply look at every name, one by one, until you found it. To find the first and last time the name appears, you'd keep looking at every name even after you found the first one until you reach the end.

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

Start at the very beginning of the phone book.
Look at the first name and check if it matches the name you're searching for.
If it matches, remember this position as the first time you saw the name.
Keep looking at the next name in the phone book, even if you already found a match.
Each time you find the name, remember this position as the latest time you've seen it.
Continue until you've looked at every single name in the phone book.
In the end, you'll know the first and last positions where the name appeared.

Code Implementation

def find_first_and_last_brute_force(numbers, target):
    first_position = -1
    last_position = -1

    for index in range(len(numbers)):
        if numbers[index] == target:
            # Record the first occurence
            if first_position == -1:
                first_position = index

            # Continuously update the last position
            last_position = index

    return [first_position, last_position]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the entire input array of size n once, checking each element to find the first and last occurrences of the target value. Even after finding the first occurrence, the algorithm continues to iterate through the remaining elements to find the last occurrence. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in O(n) time complexity, where n is the size of the input array.

Space Complexity

O(1) – The provided algorithm uses a constant amount of extra space. It maintains two variables, one to store the first occurrence of the name and another to store the last occurrence. The space required for these variables does not depend on the size of the input array, N, as no additional data structures that scale with N are used.

Optimal Solution

Approach

The key to solving this problem quickly is to take advantage of the sorted nature of the data. We can efficiently find the first and last positions of the target value by performing two separate searches that cut the search space in half each time.

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

To find the first position, repeatedly divide the list in half, focusing on the left half if the target is found there, and on the right half otherwise.
When the search is narrowed down to a single number, and this number equals the target, that is the first position of the target in the sorted data.
Now to find the last position, repeat the divide and conquer strategy, but this time favor the right half when the target is found.
When the search is narrowed down to a single number, and this number equals the target, that is the last position of the target in the sorted data.
If at any time, the target value is not found during either search, indicate that the target is not present in the sorted data.

Code Implementation

def find_first_and_last_position(
    sorted_array, target_value
):
    first_position = find_first(sorted_array, target_value)
    last_position = find_last(sorted_array, target_value)
    return [first_position, last_position]

def find_first(sorted_array, target_value):
    left_index = 0
    right_index = len(sorted_array) - 1
    first_position = -1

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

        if sorted_array[middle_index] == target_value:
            # Potential first occurrence, keep searching left.
            first_position = middle_index
            right_index = middle_index - 1

        elif sorted_array[middle_index] < target_value:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return first_position

def find_last(sorted_array, target_value):
    left_index = 0
    right_index = len(sorted_array) - 1
    last_position = -1

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

        if sorted_array[middle_index] == target_value:
            # Potential last occurrence, keep searching right.
            last_position = middle_index
            left_index = middle_index + 1

        elif sorted_array[middle_index] < target_value:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return last_position

Big(O) Analysis

Time Complexity

O(log n) – The algorithm performs two binary searches on the sorted array. Each binary search repeatedly halves the search space until the target is found or the search space is exhausted. Since each binary search reduces the problem size by a factor of 2 in each step, the time complexity for each search is O(log n). Therefore, performing two binary searches results in a total time complexity of O(log n) + O(log n), which simplifies to O(log n).

Space Complexity

O(1) – The algorithm, as described, uses a divide and conquer strategy, implying the use of binary search. While not explicitly stated, the explanation suggests an iterative approach to binary search rather than a recursive one. Therefore, no extra space is used for a call stack. The only extra space required is for storing a few index variables like the start, end, and middle indices for binary search during both the first and last position searches. These variables occupy constant space, irrespective of the input array's size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return [-1, -1] immediately as the target cannot exist in an empty array.
Target is smaller than the smallest element in the array	Binary search will narrow the search space and eventually determine that the target is not found, returning [-1, -1].
Target is larger than the largest element in the array	Binary search will narrow the search space and eventually determine that the target is not found, returning [-1, -1].
Array contains a single element equal to the target	Binary search will find the element, and the start and end indices will be the same.
Array contains a single element not equal to the target	Binary search will not find the element, returning [-1, -1].
Array contains all elements equal to the target	Binary searches for the start and end will correctly identify the first and last indices of the repeated target values.
Array contains duplicate numbers, but none are the target	Binary search will narrow the search space and eventually determine that the target is not found, returning [-1, -1].
Target is present only at the start or end of the array	The binary search strategy handles this case, as it correctly identifies the first and last occurrence independent of array position.

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 are the possible value ranges for the integers in the input array and the target value? Could they be negative?
What should I return if the input array is null or empty?
If the target value appears multiple times consecutively, should I return the first and last index of *all* occurrences, or is any valid range acceptable?
Is the input array guaranteed to be sorted in ascending order, or could it be descending?
Are there any memory constraints I should be aware of, given the potential size of the input array?

Brute Force Solution

Approach

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

Start at the very beginning of the phone book.
Look at the first name and check if it matches the name you're searching for.
If it matches, remember this position as the first time you saw the name.
Keep looking at the next name in the phone book, even if you already found a match.
Each time you find the name, remember this position as the latest time you've seen it.
Continue until you've looked at every single name in the phone book.
In the end, you'll know the first and last positions where the name appeared.

Code Implementation

def find_first_and_last_brute_force(numbers, target):
    first_position = -1
    last_position = -1

    for index in range(len(numbers)):
        if numbers[index] == target:
            # Record the first occurence
            if first_position == -1:
                first_position = index

            # Continuously update the last position
            last_position = index

    return [first_position, last_position]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

To find the first position, repeatedly divide the list in half, focusing on the left half if the target is found there, and on the right half otherwise.
When the search is narrowed down to a single number, and this number equals the target, that is the first position of the target in the sorted data.
Now to find the last position, repeat the divide and conquer strategy, but this time favor the right half when the target is found.
When the search is narrowed down to a single number, and this number equals the target, that is the last position of the target in the sorted data.
If at any time, the target value is not found during either search, indicate that the target is not present in the sorted data.

Code Implementation

def find_first_and_last_position(
    sorted_array, target_value
):
    first_position = find_first(sorted_array, target_value)
    last_position = find_last(sorted_array, target_value)
    return [first_position, last_position]

def find_first(sorted_array, target_value):
    left_index = 0
    right_index = len(sorted_array) - 1
    first_position = -1

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

        if sorted_array[middle_index] == target_value:
            # Potential first occurrence, keep searching left.
            first_position = middle_index
            right_index = middle_index - 1

        elif sorted_array[middle_index] < target_value:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return first_position

def find_last(sorted_array, target_value):
    left_index = 0
    right_index = len(sorted_array) - 1
    last_position = -1

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

        if sorted_array[middle_index] == target_value:
            # Potential last occurrence, keep searching right.
            last_position = middle_index
            left_index = middle_index + 1

        elif sorted_array[middle_index] < target_value:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return last_position

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return [-1, -1] immediately as the target cannot exist in an empty array.
Target is smaller than the smallest element in the array	Binary search will narrow the search space and eventually determine that the target is not found, returning [-1, -1].
Target is larger than the largest element in the array	Binary search will narrow the search space and eventually determine that the target is not found, returning [-1, -1].
Array contains a single element equal to the target	Binary search will find the element, and the start and end indices will be the same.
Array contains a single element not equal to the target	Binary search will not find the element, returning [-1, -1].
Array contains all elements equal to the target	Binary searches for the start and end will correctly identify the first and last indices of the repeated target values.
Array contains duplicate numbers, but none are the target	Binary search will narrow the search space and eventually determine that the target is not found, returning [-1, -1].
Target is present only at the start or end of the array	The binary search strategy handles this case, as it correctly identifies the first and last occurrence independent of array position.