Power Update After K-th Largest Insertion I - Solution & Explanation

Problem Overview: You receive a sequence of insertions and must update the system's "power" after determining the k-th largest element among the numbers seen so far. After each insertion, the algorithm must quickly determine the current k-th largest value and update the result accordingly.

Approach 1: Re-sort After Each Insertion (O(n log n) time, O(n) space)

The most direct solution stores all inserted values in an array and sorts the array every time a new number arrives. After sorting in descending order, the k-th element is immediately available and can be used to update the power value. This approach is easy to implement but inefficient because sorting runs in O(n log n) after each insertion. As the stream grows, repeated sorting becomes the bottleneck.

Approach 2: Maintain a Sorted Structure (O(n) insertion, O(n) space)

Instead of sorting the entire list repeatedly, keep the array sorted at all times. For each insertion, locate the correct position using binary search and insert the value while shifting elements to maintain order. The k-th largest element can then be accessed directly by index. Binary search costs O(log n), but the insertion shift requires O(n), so overall insertion becomes linear. This approach improves readability but still struggles with large streams.

Approach 3: Min-Heap of Size k (O(n log k) time, O(k) space)

The optimal approach maintains a min-heap containing only the largest k elements seen so far. Each new value is pushed into the heap. If the heap size exceeds k, remove the smallest element using pop. The heap's root always represents the current k-th largest element. Updating the power becomes constant time because the root is immediately available. Heap insertion and removal both cost O(log k), which keeps the total processing efficient even for large input streams.

This technique appears frequently in problems involving streaming statistics and top-k queries. It relies on the properties of heap structures and priority queues, which are designed for fast insertion and extraction. Similar patterns also show up in priority queue and data structure design problems.

Recommended for interviews: The min-heap solution is what interviewers typically expect. Starting with the brute-force sorting approach shows you understand the problem, but transitioning to a size-k heap demonstrates knowledge of streaming algorithms and optimized data structures. The reduced O(n log k) complexity scales well and clearly communicates algorithmic maturity.