Replace each element with the least greater element on its right
Problem
Replace each element with the smallest element to its right that is greater than it, or −1 if none exists.
Example 1
Input: [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28] Output: [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]
Also asked as: Replace every element with the least greater element on its right
Test cases
Case 1
Input: [8,58,71,18,31,32,63,92,43,3,91,93,25,80,28] Expected: [18,63,80,25,32,43,80,93,80,25,93,-1,28,-1,-1]
Case 2
Input: [1,2,3] Expected: [2,3,-1]
Case 3
Input: [3,2,1] Expected: [-1,-1,-1]
Case 4
Input: [2,2] Expected: [-1,-1]
View solutionHide solution1 approach
1. Insert right-to-left into a BST, read the successor
Time O(n·h)Space O(n)
Process the array from the end. Insert each value into a BST; on the way down, the last node you turned left from is its least greater element.
function replaceWithLeastGreater(a) { let root = null; const res = Array(a.length).fill(-1); const insert = (val, i) => { let succ = null, node = root, parent = null, dir = ''; while (node) { parent = node; if (val < node.val) { succ = node; node = node.left; dir = 'left'; } else { node = node.right; dir = 'right'; } } const fresh = { val, left: null, right: null }; if (!parent) root = fresh; else parent[dir] = fresh; if (succ) res[i] = succ.val; }; for (let i = a.length - 1; i >= 0; i--) insert(a[i], i); return res;}