436. Replace Every Element With the Least Greater Element on Its Right

Given an array of n integers, replace every element with the smallest element to its right that is strictly greater than it, or -1 if no such element exists. Print the resulting array, space-separated. The first line has n, the second line has the array.

Input: First line contains the integer n. Second line contains n space-separated integers of the array. Output: Print the resulting array, space-separated, where each element is replaced by the smallest strictly greater element to its right, or -1 if none exists.

1 <= n <= 10^5

Processing RIGHT TO LEFT (rather than left to right) is essential - it ensures that by the time you query for any element's answer, the ordered structure already contains exactly the elements to its right, nothing more and nothing less.

For every number in an array, find the SMALLEST number to its right that's still bigger than it - or -1 if none exists. Brute force: For every element, scan everything to its right directly, checking for the smallest value greater than it - this costs O(n²), too slow for large arrays. Optimised: Maintaining a self-balancing BST (or ordered-set structure) as you scan right-to-left lets each 'find the smallest value greater than X' query run in O(log n) time via a standard BST successor-search, and each insertion is also O(log n) - this is exactly why the problem is categorized under BSTs, even though it looks like a pure array problem on the surface.

Process the array from right to left while maintaining a self-balancing ordered structure (such as a balanced BST / ordered set) that guarantees logarithmic-time operations regardless of input order. For each arr[i], query the structure for the smallest stored value strictly greater than arr[i] (a ceiling/successor query), record that as the answer, then insert arr[i] into the structure. Because the structure stays balanced by construction, every query and insertion is guaranteed O(log n) even on adversarial input, giving a reliable worst-case bound rather than just an average-case one. Time: O(n log n) Space: O(n)

Process the array from right to left while maintaining an ordinary (not necessarily balanced) binary search tree of the elements seen so far. For each arr[i], first query the current tree for its in-order successor of arr[i] (the smallest stored value strictly greater than arr[i]) using the standard BST successor-search technique, record that as the answer, then insert arr[i] into the tree so it's available for elements further to the left. Because the tree isn't kept balanced, this performs well on average but can degrade to linear time per operation on adversarial (e.g. sorted) input, since the tree can become a skewed chain. Time: O(n log n) average, O(n^2) worst case Space: O(n)

For each index i, scan every index j to its right (from i+1 to n-1) and track the smallest value encountered so far that is strictly greater than arr[i], updating the running minimum as the scan proceeds. After the inner scan finishes, that tracked minimum (or -1 if none was found) is the answer for position i. This directly implements the definition with two nested loops and no auxiliary data structure. Time: O(n^2) Space: O(1) extra (excluding output array)

1. Process the array from RIGHT to LEFT, maintaining a self-balancing BST (or an equivalent ordered-set structure) of every value seen so far (to the current element's right). 2. For the current element, its answer is the SMALLEST value in that structure strictly greater than it - a 'find successor' query on the ordered set. 3. After answering, insert the current element into the structure before moving further left.

Time: O(n log n) - each of the n elements requires one O(log n) successor query and one O(log n) insertion into the ordered structure. Space: O(n), for the ordered-set structure holding all previously-processed elements.

Test with n=1 (answer is always -1, nothing to its right), a strictly decreasing array (every position answers -1), a strictly increasing array (only the last element is -1), and n=10^5 for performance.

Be ready to explain WHY this problem, despite looking like a pure array problem, is naturally solved with a BST-like structure - the 'find smallest value greater than X' operation is precisely what a BST's successor-search operation provides efficiently.