Shelf Brace Anchors
Index of the nearest strictly greater value to the left of each array element
A library is testing adjustable braces for books arranged in a single row. The books are numbered from left to right, starting at index 0, and heights[i] is the height of book i.
Each book's brace must attach to a book somewhere to its left that is strictly taller. If several books qualify, the brace attaches to the nearest one: the qualifying book with the largest index. Books of equal height cannot serve as anchors for one another.
Return an integer list anchors of the same length as heights, where anchors[i] is the index of the anchor for book i, or -1 if no qualifying book exists. The books do not move, and choosing an anchor does not change any height.
Examples
Example 1
Input: heights = [4,2,2,5,3] Output: [-1,0,0,-1,3]
The two height-2 books both anchor to the first book: equal-height books cannot anchor to one another. The height-5 book has no taller book to its left, and the final book anchors to that height-5 book.
Example 2
Input: heights = [9,7,5,2] Output: [-1,0,1,2]
Every book after the first is shorter than its immediate left neighbor, so that neighbor is its nearest qualifying anchor.
Example 3
Input: heights = [6,6,6] Output: [-1,-1,-1]
All books have equal height. Since an anchor must be strictly taller, none of the books has an anchor.
Constraints
- 0 <= heights.length <= 12000
- 1 <= heights[i] <= 1000000
Indices are zero-based. An empty row produces an empty list.
Hints
Show hint 1Hint 1
Keep indices of books that could still be the nearest taller anchor for a later book.
Show hint 2Hint 2
Before choosing the current book's anchor, discard candidate indices whose heights are less than or equal to the current height.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the solution change if equal-height books could also serve as anchors?
- How would you find the nearest strictly taller book to the right instead?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem