Replace each element with the least greater element on its right

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}