Find first and last positions of an element in a sorted array
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

Question

Find first and last positions of an element in a sorted array

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

Accepted Answer

Firstly, I used binary search to find the element and the used linear search from that index to find the range
Interviewer asked me to optimise the solution.
Then, I used binary search 2 times to find lower bound and upper bound of element.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(n)Explanation:

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

Accepted Answer

Binary Search

The given input array is sorted, thus we can apply binary search to the array. Binary search finds any element in O(log(N)), where N is the size of the input array.
Binary search prunes the search space by a factor of 2, in every step. Thus, we choose a mid-index to compare the elements in the current range [LO, HI]. The maximum depth of the binary search call stack is O(log(N)).

Initialise the search space as, LO = 0 and HI = N-1.
To calculate the first occurrence, two conditions need to be checked at mid-value:

If MID == 0, that means it’s the leftmost value in the array and no element lies to its left. Or if the value at mid position equals X, and the value at the MID-1 index is not equal to X. Then, MID is the first occurrence of X in the array, return MID.
Else if X > ARR[MID], that means X will lie in [MID+1, HI] indices of the array.
Else X will lie in [LO, MID-1] indices of the array.

To find the first occurrence of the value X in the sorted array, use the binary search :

Set LO = 0, HI = N-1.
Exit condition for Search function: LO <= HI
For any MID value , where MID = (LO + HI)/2:

a. If MID equals to 0 or if ARR[MID] == X, and X > ARR[MID-1], return MID.

b. Else if, X > ARR[MID], then set LO = MID+1.

c. Else X < ARR[MID], then set HI = MID-1.

4. Else return -1.

To find the last occurrence of X, two conditions need to be checked at mid-value:

If MID == N-1, that is if mid is at last position or if ARR[MID] equals X, and element at next index is higher i.e. ARR[MID+1] > X, which implies that MID is the last occurrence of element X.
Else if X > ARR[MID], that means X will lie in [MID+1, HI] indices of the array.
Else X will lie in [LO, MID-1] indices of the array.

To find the last occurrence of the value X in the sorted array, use the binary search :

Set LO = 0, HI = N-1.
Exit condition for Search function: LO <= HI
For any MID value , where MID = (LO + HI)/2 :

a. If MID equals to N-1 or if ARR[MID] == X, and X < ARR[MID+1], return MID.

b. Else if, X < ARR[MID], then set LO = MID-1.

c. Else X > ARR[MID], then set HI = MID+1.

4. Else return -1.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(logn)Explanation:

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

Since here we are using binary search, therefore the time complexity grows by order of O(log(N)).

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:

Follow Up:

Input Format:

Output Format:

Note:

Constraints:

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer