Problem solving with programming: Finding the pivot element

Problem solving with programming: Finding the pivot element

Pages Thursday, August 20, 2015 Finding the pivot element 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. One array stores the maximum element seen so far from the left.

Read full article from Problem solving with programming: Finding the pivot element