Replace every element with the least greater element on its right

Problem Statement

Given an array of integers, replace every element with the least greater element on its right side. If there is no greater element, replace it with -1.

Example:

Approach 1: Brute Force (Check All Right Elements)

Intuition

For each element, scan all elements to its right and find the minimum element that is greater than the current element.

Algorithm

1. For each element at index i
2. Initialize least_greater as infinity
3. Check all elements from i+1 to n-1
4. Find minimum element greater than arr[i]
5. Replace arr[i] with least_greater (or -1 if not found)

import java.util.*;

public class Solution {
    public int[] replaceWithLeastGreaterBruteForce(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            int leastGreater = Integer.MAX_VALUE;
            
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i] && arr[j] < leastGreater) {
                    leastGreater = arr[j];
                }
            }
            
            result[i] = (leastGreater == Integer.MAX_VALUE) ? -1 : leastGreater;
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Nested loops
• Space Complexity: O(n) - Result array

Approach 2: Optimal (Using BST - Process from Right)

Intuition

Process array from right to left. Maintain a BST of elements seen so far. For each element, find its inorder successor (least greater element) in the BST, then insert the current element.

Algorithm

1. Process array from right to left
2. For each element, find inorder successor in BST
3. Insert current element into BST
4. Store the successor value (or -1) as result

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        
        if (val < root.val) {
            root.left = insert(root.left, val);
        } else {
            root.right = insert(root.right, val);
        }
        
        return root;
    }
    
    private int findSuccessor(TreeNode root, int val) {
        int successor = -1;
        
        while (root != null) {
            if (val < root.val) {
                successor = root.val;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        
        return successor;
    }
    
    public int[] replaceWithLeastGreaterBST(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        TreeNode root = null;
        
        for (int i = n - 1; i >= 0; i--) {
            result[i] = (root == null) ? -1 : findSuccessor(root, arr[i]);
            root = insert(root, arr[i]);
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n * h) - O(n log n) average, O(n^2) worst case for skewed BST
• Space Complexity: O(n) - BST storage

Approach 3: Optimal (Using Balanced BST / Set)

Intuition

Using a self-balancing BST (like std::set in C++) guarantees O(log n) operations.

Algorithm

1. Use a set/TreeSet to maintain elements seen so far
2. Process from right to left
3. Use upper_bound to find least greater element
4. Insert current element

import java.util.*;

public class Solution {
    public int[] replaceWithLeastGreaterTreeSet(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        TreeSet<Integer> set = new TreeSet<>();
        
        // Process from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Find least greater element
            Integer successor = set.higher(arr[i]);
            
            result[i] = (successor == null) ? -1 : successor;
            
            // Insert current element
            set.add(arr[i]);
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - Each operation is O(log n)
• Space Complexity: O(n) - Set storage

Approach 4: Using Fenwick Tree / Segment Tree

Intuition

For more complex variants or when we need to handle duplicates efficiently, we can use Fenwick Tree or Segment Tree with coordinate compression.

Algorithm

1. Coordinate compress values
2. Process from right to left
3. Use data structure to find minimum in range [arr[i]+1, max]
4. Update data structure with current element

Complexity Analysis

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Key Takeaways

1. Right to left processing: Key insight - maintain elements seen on the right
2. BST for successor: Inorder successor is exactly what we need
3. Balanced BST/Set: Guarantees O(log n) operations
4. Upper bound: Standard library function to find least greater
5. This is a classic application of BST/Set for range queries
6. Can be extended to "greater or equal" by using lower_bound
7. Segment tree approach useful for more complex variants (like handling duplicates differently)