Find First and Last Position of Element in Sorted Array

Easy

0/40

Average time to solve is 20m

133 upvotes

Asked in companies

Problem statement

You are given a non-decreasing array 'arr' consisting of 'n' integers and an integer 'x'. You need to find the first and last position of 'x' in the array.

Note:

1. The array follows 0-based indexing, so you need to return 0-based indices.
2. If 'x' is not present in the array, return {-1 -1}.
3. If 'x' is only present once in the array, the first and last position of its occurrence will be the same.

Example:

Input:  arr = [1, 2, 4, 4, 5],  x = 4

Output: 2 3

Explanation: The given array’s 0-based indexing is as follows:
 1      2     4     4     5
 ↓      ↓     ↓     ↓     ↓
 0      1     2     3     4

So, the first occurrence of 4 is at index 2, and the last occurrence of 4 is at index 3.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains the integer 'n', denoting the size of the sorted array.
The second line contains 'n' space-separated integers denoting the array elements.
The third line contains the value 'x', whose first and last position of occurrence you need to find.

Output Format:

The only line of output should contain two space-separated integers, where the first and second integer will be the first and the last position of occurrence of 'x', respectively, in the array.

Constraints:

 1 <= n <= 10^4
-10^9 <= arr[i] <= 10^9
-10^9 <= x <= 10^9
 Time Limit: 1sec

Expected Time Complexity:

Try to solve the problem in O(log(N)) time complexity.

Sample Input 1:

5
-10 -5 -5 -5 2
-5

Sample Output 1:

1 3

Explanation for Sample Input 1:

The given array’s 0-based indexing is as follows:
-10    -5    -5    -5     2
 ↓      ↓     ↓     ↓     ↓
 0      1     2     3     4

So, the first occurrence of -5 is at index 1, and the last occurrence of -5 is at index 3.

Sample Input 2:

4
1 2 3 4
-1

Sample Output 2:

-1 -1

Explanation for Sample Input 2:

The given array 'arr' is:[1, 2, 3, 4] and 'x' = -1.
In this case 'x' is not present in the array.
Hence, we return {-1,-1}.

Hint 1

Hint 2

Naively find first and the last occurrence.

Approaches (2)

Approach 1

Approach 2

Naively find first and the last occurrence

Create two storage variables ‘IDX1’ and ‘IDX2’ to store the first and last position of occurrence and initialise them to -1.
Iterate through the array, if you encounter an array element equal to value ‘X’, and ‘IDX1’ = ‘IDX2’ = -1 previously, then update ‘IDX1’, ‘IDX2’ to the current index.
If ‘IDX1’ != -1 and you encounter an array element equal to value ‘X’, then only update ‘IDX2’ as then you had already recorded the first occurrence
Finally, return ‘IDX1’ and ‘IDX2’.

Time Complexity

O(N), where ‘N’ is the size of the sorted array.

Since here a linear search is being used for traversing and searching through all the ‘N’ elements of the sorted array, therefore, the worst-case time complexity becomes O(N).

Space Complexity

O(1), as we are using constant extra memory.

(100% EXP penalty)

Find First and Last Position of Element in Sorted Array

Console