Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

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

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

Output:

```
[2, 4]
```

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

Output:

```
[-1, -1]
```

- 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
^{5} - -10
^{9}<= list elements <= 10^{9} - -10
^{9}<= target value <= 10^{9}

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`

.

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`

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.

O(1).

We used a constant amount of additional memory.

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

```
/*
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;
}
```

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.

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(numbers*count)).
Though, the time complexity of the complete code will be O(numbers*count) as we will require that amount of time to take the input of `numbers_count`

number of integers.

O(1).

We used a constant amount of additional memory.

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

```
/*
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.

Note: Input and Output will already be taken care of.