Last Updated: 30 Oct, 2020
Find First and Last Position of Element in Sorted Array
Easy
Asked in companies
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.
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.
Approaches
- 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’.
- 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.
Similar problems