Find element smaller than left and greater than right elements
Filed under Amazon
Free read 2 of 3Understand whether boundary elements (first and last) can be valid and how duplicate values are handled.
The question
Given an unsorted array of integers, find an element such that all elements to its left are smaller than or equal to it, and all elements to its right are greater than or equal to it. Return the index of such an element, or -1 if no such element exists.
Constraints
- 3 <= array length <= 10^5
- Array elements fit within standard integer limits
Examples
- Input
- arr = [5, 1, 4, 3, 6, 8, 10, 7, 9]
- Output
- 4
- Why
- For element 6 (index 4), left elements [5, 1, 4, 3] are all smaller, and right elements [8, 10, 7, 9] are all greater.
Approach
Understand whether boundary elements (first and last) can be valid and how duplicate values are handled.
For every element, iterate through all elements to its left and right to check the conditions. Time complexity is O(n^2).
Create a suffix minimum array where each entry stores the minimum value to the right. Then iterate from left to right while maintaining a running maximum of elements seen so far. The first element where running_max <= suffix_min[i] is our answer.
Arrays that are sorted in ascending or descending order where no valid element exists.
Tips
- What they are testing: Test arrays where the valid element is at the very beginning or end, and arrays with strictly increasing or decreasing orders.
- Common mistake: Using a nested loop resulting in O(n^2) time complexity instead of utilizing prefix and suffix tracking.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.