Kth Largest Element in a Stream

• Initialization (KthLargest(k, nums)):
  • Store the integer k.
  • Create a dynamic list (e.g., ArrayList in Java).
  • Add all elements from the initial nums array into this list.
• Adding an element (add(val)):
  • Add the new value val to the list.
  • Sort the entire list in ascending order.
  • The kth largest element is located at index list.size() - k.
  • Return the element at this index.

The core idea is to maintain a collection of all numbers encountered so far. When a new number arrives, we add it to our collection and then sort the entire collection to re-establish order. Once sorted, finding the kth largest element is a simple matter of accessing the correct index from the end of the sorted list.

For example, if we have the numbers [4, 5, 8, 2] and k=3, and we add 3, our list becomes [4, 5, 8, 2, 3]. Sorting this gives [2, 3, 4, 5, 8]. The 3rd largest element is at index 5 - 3 = 2, which is 4.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class KthLargest {6    private int k;7    private List<Integer> stream;8 9    public KthLargest(int k, int[] nums) {10        this.k = k;11        this.stream = new ArrayList<>();12        for (int num : nums) {13            this.stream.add(num);14        }15    }16 17    public int add(int val) {18        this.stream.add(val);19        Collections.sort(this.stream);20        return this.stream.get(this.stream.size() - k);21    }22}

• Initialization (KthLargest(k, nums)):
  • Store the integer k.
  • Create a dynamic list and populate it with elements from nums.
  • Sort the list once.
• Adding an element (add(val)):
  • Find the correct position to insert val into the sorted list to maintain its order. This can be done with a linear scan or binary search.
  • Insert val at that position. This operation takes linear time in an array-based list as it requires shifting elements.
  • Return the element at index list.size() - k.

We start by sorting the initial array of numbers. When a new number val is added, we don't re-sort everything. Instead, we find the index where val should be inserted to keep the list sorted. While finding this index can be done efficiently in O(log L) time using binary search, the insertion into an ArrayList at a specific index takes O(L) time because all subsequent elements must be shifted one position to the right. After insertion, the kth largest element is found at the same list.size() - k index.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class KthLargest {6    private int k;7    private List<Integer> stream;8 9    public KthLargest(int k, int[] nums) {10        this.k = k;11        this.stream = new ArrayList<>();12        for (int num : nums) {13            this.stream.add(num);14        }15        Collections.sort(this.stream);16    }17 18    public int add(int val) {19        // A simple linear scan to find the insertion point.20        // A binary search would be faster to find the index, but the21        // list.add(index, value) operation is the O(L) bottleneck.22        int i = 0;23        while (i < stream.size() && stream.get(i) < val) {24            i++;25        }26        stream.add(i, val);27        28        return stream.get(stream.size() - k);29    }30}

• Data Structure: Use a Min-Heap (Priority Queue in Java) to store the k largest elements.
• Initialization (KthLargest(k, nums)):
  • Store k.
  • Initialize an empty min-heap.
  • Iterate through the initial nums array and call the add method for each number to populate the heap correctly.
• Adding an element (add(val)):
  • If the heap's size is less than k, add val to the heap.
  • If the heap's size is k, compare val with the smallest element in the heap (the root, accessible via peek()).
  • If val is larger than the root, remove the root (poll()) and add val to the heap (offer()).
  • If val is smaller or equal, do nothing.
  • The kth largest element in the stream is now the root of the min-heap. Return heap.peek().

The key insight is that we only need to keep track of the k largest numbers, not all of them. A min-heap is perfect for this. It's a priority queue that always keeps the smallest element at the root. By maintaining a min-heap of size k, the root will always be the kth largest element seen so far.

When we add a new element val:

1. If the heap isn't full (size < k), we add val.
2. If the heap is full, we check if val is larger than the current kth largest element (heap.peek()). If it is, val deserves to be in our set of k largest numbers. We remove the smallest member of this set (heap.poll()) and add val. Otherwise, val is smaller than the current kth largest, so we can ignore it.

After this process, the root of the heap (heap.peek()) is the answer.

1import java.util.PriorityQueue;2 3class KthLargest {4    private final int k;5    private final PriorityQueue<Integer> minHeap;6 7    public KthLargest(int k, int[] nums) {8        this.k = k;9        this.minHeap = new PriorityQueue<>();10        for (int num : nums) {11            // Use the add method's logic to build the initial heap12            add(num);13        }14    }15 16    public int add(int val) {17        if (minHeap.size() < k) {18            minHeap.offer(val);19        } else if (val > minHeap.peek()) {20            minHeap.poll();21            minHeap.offer(val);22        }23        return minHeap.peek();24    }25}