First and Last Position of an element in Sorted Array

Posted: 30 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a sorted array ARR consisting of N integers and an integer X. You need to find the first and last position of occurrence 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.

Follow Up:

Try to solve the problem in O(log(N)) time complexity.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains the integer N, denoting the size of the sorted array.

The second line of each test case contains N space-separated integers denoting the array elements.

The third and last line of each test case contains the value X, whose first and last position of occurrence you need to find.
Output Format:
The only line of output of each test case 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.
Note:
Just implement the given function. You do not need to print anything, it has already been taken care of.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
-10^9 <= ARR[i] <= 10^9
-10^9 <= X <= 10^9

Time Limit: 1sec
Approach 1
  • 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.
Try Problem