Replace every element with the least greater element on its right

The problem, simply

You get an array of numbers. Replace each number with the smallest number that is bigger than it and sits somewhere to its right. If no number to its right is bigger, write -1.

Note the difference from "next greater element": we do not want the first bigger number to the right, we want the smallest bigger one anywhere to the right.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each number, scan everything to its right and keep the smallest number that is bigger.

1. For each i, start with best = infinity.
2. For each j > i, if a[j] > a[i] and a[j] < best, set best = a[j].
3. Write best, or -1 if it stayed at infinity.

class Solution {
    public int[] leastGreater(int[] a) {
        int n = a.length;
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            int best = Integer.MAX_VALUE;
            boolean found = false;
            for (int j = i + 1; j < n; j++) {
                if (a[j] > a[i] && a[j] <= best) {
                    best = a[j];
                    found = true;
                }
            }
            out[i] = found ? best : -1;
        }
        return out;
    }
}

How long it takes: about n * n / 2 comparisons, O(n^2). Extra room besides the answer: O(1).

Way 2: the clever way

Read the array from right to left. Keep a BST of the numbers already read, which are exactly the numbers to the right of the current one.

1. For i from the last index down to 0, insert a[i] into the BST with a normal walk: smaller goes left, otherwise right.
2. During the walk, every time you go left at a spot, that spot is bigger than a[i]. Remember it as succ. A later left turn is always at a smaller spot, so the last one is the smallest bigger number.
3. The answer for i is succ, or -1 if you never turned left.

class Solution {
    private int succ;                                  // the last left turn of this insert

    public int[] leastGreater(int[] a) {
        int[] out = new int[a.length];
        TreeNode root = null;
        for (int i = a.length - 1; i >= 0; i--) {     // read from the right
            succ = -1;
            root = insert(root, a[i]);
            out[i] = succ;
        }
        return out;
    }

    private TreeNode insert(TreeNode node, int x) {
        if (node == null) return new TreeNode(x);
        if (x < node.val) {
            succ = node.val;                           // bigger than x: a candidate
            node.left = insert(node.left, x);
        } else {
            node.right = insert(node.right, x);        // equal or smaller: not bigger
        }
        return node;
    }
}

How long it takes: each insert walks one road, O(h), so O(n h) in total. That is O(n log n) when the tree stays bushy, but a sorted input makes a stick and O(n^2). Extra room: the tree, O(n).

Another way: a balanced tree from the library

Java's TreeSet is a self balancing BST, so its height stays about log n whatever the input. higher(x) gives the smallest number strictly bigger than x. Since repeats do not matter for this question, a set is enough.

import java.util.*;

class Solution {
    public int[] leastGreater(int[] a) {
        int[] out = new int[a.length];
        TreeSet<Integer> right = new TreeSet<>();      // numbers to the right of i
        for (int i = a.length - 1; i >= 0; i--) {
            Integer up = right.higher(a[i]);          // smallest number bigger than a[i]
            out[i] = (up == null) ? -1 : up;
            right.add(a[i]);
        }
        return out;
    }
}

This is a guaranteed O(n log n) with O(n) room. In an interview, write this one, and explain that it is the same left turn idea inside a red black tree.

Watch out for

• Treating equal as bigger. Use strict x < node.val for a left turn, and send equal numbers right.
• Reading from the left. The tree must hold only numbers to the right of i, so read from the right end.
• Forgetting to reset succ to -1 before each insert.

What interviewers ask next

• Count how many numbers to the right are smaller (LeetCode 315). Same backwards insert, but each spot stores the size of its left side, and every right turn adds that size plus one.
• The largest smaller number to the right. Mirror it: the last right turn wins, or use TreeSet.lower.
• Why does a plain BST risk O(n^2)? An already sorted input makes every insert walk the full stick. A balanced tree or shuffling avoids it.
• Can it be done in O(n log n) without a tree? Yes: sort the indices by value, then for each value find the next index to the right in sorted order using a stack, as in "next greater element" on the sorted list of indices.

Remember this

Grown-up words: the kids already inside are a BST of the suffix, the last left turn is the inorder successor of the new value, higher is the ceiling-above query of a balanced BST, and reading backwards is a right to left sweep.