Example: Kth Largest Element in a Stream with bst - rFronteddu/general_wiki GitHub Wiki

The space complexity of the KthLargest class using a Binary Search Tree (BST) to store the stream of numbers and find the Kth largest element is O(n), where n is the number of elements in the stream. This space is required to store the nodes of the BST.

The time complexity of the KthLargest class depends on the operations performed:

Initialization: The initialization step inserts each element of the nums array into the BST, resulting in a time complexity of O(n log n), where n is the number of elements in the nums array. This is because each insertion operation in a balanced BST takes O(log n) time, and there are n elements to insert.

Adding a new element (add method): Adding a new element involves inserting it into the BST, which takes O(log n) time in the average case for a balanced BST. Additionally, finding the Kth largest element also takes O(log n) time, as it involves traversing down the BST to the appropriate subtree. Therefore, the time complexity of the add method is O(log n).

Overall, the time complexity of initializing the KthLargest class is O(n log n), and the time complexity of adding a new element is O(log n).

class TreeNode {
    int val;
    int count;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.count = 1;
    }
}

class KthLargest {
    private TreeNode root;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int num : nums) {
            root = insert(root, num);
        }
    }

    public int add(int val) {
        root = insert(root, val);
        return kthLargest(root, k);
    }

    private TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        root.count++;
        if (val < root.val) {
            root.left = insert(root.left, val);
        } else {
            root.right = insert(root.right, val);
        }
        return root;
    }

    private int kthLargest(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        int rightCount = root.right != null ? root.right.count : 0;
        if (k == rightCount + 1) {
            return root.val;
        } else if (k > rightCount + 1) {
            return kthLargest(root.left, k - rightCount - 1);
        } else {
            return kthLargest(root.right, k);
        }
    }
}