Replace every element with the least greater element on its right

Brute force Approach

🔺A simple way is to run two loops. The outer loop will choose an array of elements one by one from left to right. On its right side, the inner loop will look for the smallest element greater than the selected element. Finally, the outer loop will replace the element chosen with the element discovered by the inner loop. This method's time complexity will be O(n^2).

🔺Using Binary Search Trees would be a difficult solution. Starting from the right, we scan the array and insert each element into the BST. In BST, we replace each added element in the array with its in-order successor. If the added element is the maximum so far (i.e. its inorder successor does not exist), it is replaced by -1.

Algorithm 

🔻 To solve this problem, we are using the above-mentioned BST approach in which we will create two functions. First will be the constructor in which we will assign the null values, and the second function will be the insertion function which inserts the node with the condition given below.

🔻The insertion function has two arguments one is to determine the child of the tree and the other is the value.

🔻We are inserting the node by the following method:

if (node == null)
{
    node = new Node(value);
}
// If the key node is smaller than the root's key, go to left subtree and set successors
// as current node
if (value < node.value)
{
    successor = node;
    node.left = nodeinsertion(node.left, value);
}

else if (value > node.value)
    node.right = nodeinsertion(node.right, value);

return node;
}

🔻 Finally, we will print the array with the element which has the least greater element on its right.

Java code

// Java program to Replace every element with the least greater element on its right
import java.io.*;
import java.util.*;

class BinarySearchTree {

    class Node {
        int value;
        Node left, right;

        Node(int d) {
            value = d;
            left = right = null;
        }
    }

    static Node root;
    static Node successor;

    BinarySearchTree() {
        root = null;
        successor = null;
    }

    Node nodeinsertion(Node node, int value) {

        if (node == null) {
            node = new Node(value);
        }

        // If the key is smaller than root's key, go to left subtree and set successoressor as current node
        if (value < node.value) {
            successor = node;
            node.left = nodeinsertion(node.left, value);
        }

        // Go to right subtree
        else if (value > node.value)
            node.right = nodeinsertion(node.right, value);

        return node;
    }

    // Driver code
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of nodes which you want to insert");
        int arsize = sc.nextInt();
        int arr[] = new int[arsize];
        int n = arr.length;
        System.out.println("Enter the elements of the array");
        for (int i = 0; i < arsize; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println("\n Tree before replace every element with the least greater element on its right");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
            
        // replacing every element with the least greater element on its right
        BinarySearchTree tree = new BinarySearchTree();

        // starting from right to left
        for (int i = n - 1; i >= 0; i--) {
            successor = null;

            // nodeInsertioning current element into BST and finding its inorder successoressor
            root = tree.nodeinsertion(root, arr[i]);

            // Replacing element by its inorder successoressor in BST
            if (successor != null)
                arr[i] = successor.value;
            // No inorder successoressor
            else
                arr[i] = -1;
        }
        System.out.println("\n Tree after replace every element with the least greater element on its right");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

Output    

Complexity analysis

Time complexity

O(N), since we are using a loop to traverse the tree.

Space complexity

O(N), since we are using an array to take the data from the user for each node.

Better Approach

We will be using the Next greater element using the stack algorithm in this approach as it appears to be the better approach to solve the question because it takes O(log(N)) time to execute. 

Algorithm

🔻First, we create an array of pairs called temp and store each element and its index in it.

🔻Sort the array based on the array elements.

🔻Now, using Next Greater Element, get the next greater index for every index of the temp array in an array namely index.

🔻Index[i] now holds the index of next least greater element of the element temp[i].first, and if index[i] is -1, it signifies there is no least greater element of the element temp[i].second on its right side.

🔻Take a result array where result[i] equals a[indexes[temp[i]] .second]] if index[i] is not -1; otherwise, result[i] is -1.

Java Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;
import java.util.*;
import java.io.*;

public class Codingninjas {

    // driver code
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array");
        
        int size = sc.nextInt();
        int[] arr = new int[size];
        
        System.out.println("Enter the elements of the array");
        for (int i = 0; i < size; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println("Array before we Replace every element with the least greater element on its right is ");

        ArrayList<int[]> temp = new ArrayList<int[]>();
        for (int i = 0; i < size; i++) {
            temp.add(new int[] { arr[i], i });
        }
        
        // we are sorting the temp according to the first of the pair i.e., value
        Collections.sort(temp, (a, b) -> {
            if (a[0] == b[0])
                return a[1] - b[1];
            return a[0] - b[0];
        });

        int[] arr2 = new int[size];
        Arrays.fill(arr2, -1);
        Stack<Integer> st = new Stack<Integer>();

        for (int i = 0; i < size; i++) {
            if (st.empty() || temp.get(i)[1] < st.peek())
                st.push(temp.get(i)[1]);
            // notice temp[i].second is the index
            // Otherwise, if this index (i.e. temp[i].second) is bigger than the index placed at the top of the stack,
            // we pop all the indexes saved at the top of the stack and make this index 
            // (i.e. temp[i].second) their next greater index.
            else {
                while (!st.empty() && temp.get(i)[1] > st.peek()) {
                    arr2[st.peek()] = temp.get(i)[1];
                    st.pop();
                }
                //   push the current index to the stack
                st.push(temp.get(i)[1]);
            }
            
            // we have initialize a result vector with all -1
            int[] res = new int[size];
            Arrays.fill(res, -1);

            for (int k = 0; k < size; k++) {
                // If there is no greater index after the index temp[i].second, the result is -1.
                // otherwise, the result is the element of the array arr at index indexes[temp[i] .second]
                if (arr2[temp.get(k)[1]] != -1)
                    res[temp.get(k)[1]] = arr[arr2[temp.get(k)[1]]];
            }

        }
        int[] respond = arr2.clone();

        System.out.println("Array after we Replace every element with the least greater element on its right is ");

        for (int j = 0; j < respond.length; j++)
            System.out.print(respond[j] + " ");
        System.out.println();
    }
}

Output

Complexity analysis

Time complexity

O(N), since we are using a loop to traverse the tree.

Space complexity

O(N), since we are using an array to take the data from the user for each node.

Optimized Approach

A different approach to the problem is to state our requirements and then think about them to develop a solution. If we go back through the array, we'll need a data structure(ds) to support:

🔺Insert an element in sorted order into our data structure (so at any point in time the elements in our data structure are sorted).

🔺determining the current element's upper bound (upper bound will give just a greater element from our data structure if present).

Algorithm

🔺First of all, make a tree set data structure to perform the above-discussed approach as it provides a tree data structure for storage with the set interface.

🔺Traversing the array in reverse order to add it to the treeset data structure.

🔺Now we will use the following code to find if an upper bound(higher value) exists in the set then we will store it in the array at the same index.

Integer bound = s.higher(arr[i]);  

if (bound == null)
arr[i] = -1;

else
arr[i] = bound;

🔺If there is no upper bound value then we will store -1 as indicated in the code.

Java Code

//java program to replace every element with the least greater element on its right
import java.util.*;

public class codingninjas2 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array");

        int size = sc.nextInt();
        int[] arr = new int[size];

        System.out.println("Enter the elements of the array");

        for (int i = 0; i < size; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("Array before we Replace every element with the least greater element on its right is ");
        for (int i : arr)
            System.out.print(i + " ");
        System.out.println();

        TreeSet<Integer> s = new TreeSet<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            s.add(arr[i]); // inserting the element into set
            Integer it = s.higher(arr[i]); // finding out upper bound

            if (it == null)
                arr[i] = -1; // if upper_bound not exist then -1

            else
                arr[i] = it; // if upper_bound exists

        }

        System.out.println("Array after we Replace every element with the least greater element on its right is ");
        for (int i : arr)
            System.out.print(i + " ");
        System.out.println();
    }
}

Output

Complexity analysis

Time complexity

O(Nlog(N)), since we are inserting each element in our set and finding the upper bound for each element using a loop to replace every element with the least greater element on its right.

Space complexity

O(N), since we are using an array to take the data from the user for each node.

Frequently Asked Questions

What is the definition of a perfectly balanced tree?

If a tree is empty or the number of nodes in each subtree differs by no more than one, it is perfectly balanced. We know that searching the left or right subtree from any point will take the same amount of time in a perfectly balanced tree.

Is a complete binary tree a perfect binary tree?

All nodes in a full binary tree have either none or two children. All nodes up to level h could have two offspring in a complete binary tree of height h.

What is the height of a tree that is perfectly balanced?

One approach to achieve this is to ensure that our trees are evenly spaced in height. If the left subtree and right subtrees of any node are the same height, the tree is perfectly balanced. It is known that there are twice as many nodes at each level as there were at the preceding level, resulting in H = O(logN).

Conclusion

In this article, we have discussed the binary search tree data structure in brief, examples, approach, and how to replace every element with the least greater element on its right, time, and space complexity for the three approaches.

After reading about how to replace every element with the least greater element on its right, are you not feeling excited to read/explore more articles on the topic of Binary Search Trees? Don't worry; Coding Ninjas has you covered. If you want to practice questions on the binary tree then follow these links: Insertion in BST, Symmetric tree, BST to sorted DLL, Preorder binary tree, Range Sum of BST, Sum of all nodes with smaller values at a distance 'K' from the given node in BST, Reverse a Stack using Recursion, and Preorder traversal.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to check your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!