Find Range Problem Statement

Given a list of integers sorted in ascending order, find the first and the last occurrence of a given target number in the list.

Example One

{
"numbers": [1, 2, 3, 3, 3, 4, 5, 5],
"target": 3
}

Output:

[2, 4]

Example Two

{
"numbers": [2, 3, 5, 10],
"target": 4
}

Output:

[-1, -1]

Notes

• The function returns a list of size two where the elements specify the starting and ending indices of the target value respectively in the given list.
• In case when the target value is not present in the list, return the range as [-1, -1].

Constraints:

• 1 <= size of the given list <= 10⁵
• -10⁹ <= list elements <= 10⁹
• -10⁹ <= target value <= 10⁹

We have provided two solutions.

We will start with a brute force solution and will then look at some observations to arrive at a more optimized solution using the binary search algorithm. Throughout this editorial, we will refer to the input array as numbers, its size as numbers_count and the target integer as target.

Find Range Solution 1: Linear Scan

Let us call the index of the first and last occurrence of the target number as first_index and last_index respectively.

To find the first_index, we will iterate the numbers array from left to right and stop as we find the first occurrence of the target from left. If while iterating, we reach a number greater than target, we don't need to search further as the array is sorted. Similarly, to find the last_index, we will iterate the numbers array from right to left and stop as we find the first occurrence of the target from right.

But what if the target number is not present in the numbers array?

As mentioned in the problem statement, in that case we will return an array of size 2 with both the values equal to -1.

As a constant optimization, instead of running two separate loops for finding out the first and last occurrences of the target, we can find both of them in a single traversal of the array.

For this, we will initialize first_index and last_index as -1 and will simultaneously traverse the array both from the beginning and from the end. Say, we have two iterators left and right with left initialized to 0 and right initialized to numbers_size - 1. In each iteration we will check if numbers[left] or numbers[right] is equal to the target and if any of them is, then we will update the left_index and right_index accordingly. At the end of each iteration, we will increment left and decrement right. We will break the loop when one of the following conditions get satisfied:

• Both first_index and last_index are updated from -1.
• left_index > right_index

Time Complexity

O(numbers_count).

We needed to run two linear loops on the numbers array which in the worst case will scan the entire array once in total.

Auxiliary Space Used

O(1).

We used a constant amount of additional memory.

Space Complexity

O(numbers_count).

Space used for input: O(numbers_count).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(numbers_count).

Code For Find Range Solution 1: Linear Scan

/*
Asymptotic complexity in terms of size of the input array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/

vector<int> find_range(vector<int> &numbers, int target) {
    vector<int> range(2);

    int first_index = -1;
    for (int i = 0; i < numbers.size(); ++i) {
        if (numbers[i] == target) {
            first_index = i;
            break;
        }
        // If the number is greater than target, we do not need to search further as the array is sorted.
        if (numbers[i] > target) {
            break;
        }
    }

    // If first_index is not updated, it means that the target value is not present in the array.
    if (first_index == -1) {
        range[0] = range[1] = -1;
        return range;
    }

    int last_index = -1;
    for (int i = numbers.size() - 1; i >= 0; --i) {
        if (numbers[i] == target) {
            last_index = i;
            break;
        }
    }

    range[0] = first_index;
    range[1] = last_index;
    return range;
}

Find Range Solution 2: Binary Search

Using the fact that the numbers array is sorted, we can use the Binary Search algorithm to find the leftmost and the rightmost index of the target integer in the array. Similar to the first solution, we will refer to the first and last index of the target in the array as first_index and last_index.

To find the first_index, we will perform a modified binary search on the array. In the normal binary search, we stop when we find the target number in the array. Here, instead of stopping, we will store the current index in first_index and continue searching in the left subarray to check if there is another occurrence of target in any of the smaller indices of the array. The reason behind searching in the left subarray is that, if we find the target number on the current index, we cannot be sure whether it is the first occurrence of target or not. We are storing the current index in first_index to cover the case of it being the first occurrence and searching in the left subarray to cover the case of it not being the first occurrence.

Also, we will initialize left_index with -1 to check whether the target is present in the array or not. If it remains equal to -1 after the above modified binary search, it means that the target is not present in the array and we will simply return [-1, -1] in that case.

We can perform a similar modified binary search algorithm to find the last_index as well.

Time Complexity

O(log(numbers_count)).

We perform two binary searches on an array of size numbers_count. So, the time complexity of the function that we are supposed to fill is O(log(numberscount)). Though, the time complexity of the complete code will be O(numberscount) as we will require that amount of time to take the input of numbers_count number of integers.

Auxiliary Space Used

O(1).

We used a constant amount of additional memory.

Space Complexity

O(numbers_count).

Space used for input: O(numbers_count).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(numbers_count).

Code For Find Range Solution 2: Binary Search

/*
Asymptotic complexity in terms of size of the input array \`n\`:
* Time: O(log(n)).
* Auxiliary space: O(1).
* Total space: O(n).
*/

int starting_index(vector<int> &numbers, int target) {
    int low = 0, high = numbers.size() - 1, mid;

    int first_index = -1;

    while (low <= high) {
        mid = (low + high) / 2;

        // If the current element is equal to the target, we will update the first_index and search in the
        // left half to check for a smaller value of first_index.
        if (numbers[mid] == target) {
            first_index = mid;
            high = mid - 1;
        } else if (numbers[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return first_index;
}

int ending_index(vector<int> & numbers, int low, int target) {
    int high = numbers.size() - 1, mid;

    int last_index = -1;

    while (low <= high) {
        mid = (low + high) / 2;

        // If the current element is equal to the target, we will update the last_index and search in the
        // right half to check for a larger value of last_index.
        if (numbers[mid] == target) {
            last_index = mid;
            low = mid + 1;
        } else if (numbers[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return last_index;
}

vector<int> find_range(vector<int> & numbers, int target) {
    vector<int> range(2);

    int first_index = -1;
    first_index = starting_index(numbers, target);

    // If first_index is equal to -1 after the above update,
    // it means that the target value is not present in the array.
    if (first_index == -1) {
        range[0] = range[1] = -1;
        return range;
    }

    int last_index = -1;
    // 'low' for the binary search for finding the ending index can be initialized to 'first_index'
    // as the ending index will be greater than or equal to the 'first_index'.
    last_index = ending_index(numbers, first_index, target);

    range[0] = first_index;
    range[1] = last_index;
    return range;
}

We hope that these solutions to find range problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.