Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.
For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.
The array [6, 9, 1, 2, 4] does not contain any pivot element.
Simple brute force solution:
For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it’s index, otherwise we return -1.
But this solution takes O(n2) time.
Is there any better approach? Can we do it in O(n) time probably using extra space?
Yes, it can be done using two extra arrays.
For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.
The array [6, 9, 1, 2, 4] does not contain any pivot element.
Simple brute force solution:
For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it’s index, otherwise we return -1.
But this solution takes O(n2) time.
Is there any better approach? Can we do it in O(n) time probably using extra space?
Yes, it can be done using two extra arrays.
- One array stores the maximum element seen so far from the left.
- Second array stores minimum element seen so far from the right
For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4]
We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(n).
Below is the C++ implementation of the above.