Efficiently Finding Ceiling on the Right in Java using Self Balancing BSTs

The given problem of finding the closest greater or equal element on the right for each element in an array can be solved in an efficient way using Self Balancing Binary Search Trees (BST). In Java, TreeSet can be used as a Self Balancing BST implementation.

The given implementation is correct and efficient, but there are some improvements that can be made to make the code more readable and maintainable. Here are some of the improvements that can be made:

1. Use descriptive variable names: Using descriptive variable names can make the code more readable and understandable. In the given implementation, 'ts' can be renamed to 'treeSet' and 'ceilings' can be renamed to 'ceilingValues'.

2. Avoid using ArrayList for a fixed-size output array: In the given implementation, an ArrayList is used to store the ceiling values. Since the size of the output array is fixed and known in advance, it is better to use a regular array instead of an ArrayList. This can improve the performance and memory usage of the program.

3. Use enhanced for loop instead of for loop with index: Using an enhanced for loop can make the code more concise and readable. Instead of using the for loop with an index to iterate over the output array, we can use an enhanced for loop to iterate over the ceilingValues array.

Here's the improved implementation:

java
import java.util.TreeSet;

class CeilingOnRight {
    public static void findCeilingOnRight(int[] arr) {
        int n = arr.length;
        TreeSet<Integer> treeSet = new TreeSet<Integer>();
        int[] ceilingValues = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            Integer ceiling = treeSet.ceiling(arr[i]);
            ceilingValues[i] = ceiling != null ? ceiling : -1;
            treeSet.add(arr[i]);
        }

        for (int ceiling : ceilingValues) {
            System.out.print(ceiling + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = { 10, 5, 11, 10, 20, 12 };
        findCeilingOnRight(arr);
    }
}

The time complexity of the above implementation is O(N*logN), which is more efficient than the simple solution with two nested loops (which has a time complexity of O(N^2)).