Skip to main content
Talentd

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

MediumPremiumFree on FleetCode11 min readAsked at: Google
Practice this problem

Problem Statement

You are given an integer array nums and an integer p.

You are also given a 2D integer array queries, where each queries[i] = [vali, ki] and the difference between consecutive ki values is always less than 10.

For each query:

  • Insert vali into nums.
  • Let x be the kith largest element in the current nums.
  • Update p to px % (109 + 7).

Return an array ans where the ans[i] represents the value of p after processing the ith query.

 

Example 1:

Input: nums = [2], p = 4, queries = [[3,1],[1,2]]

Output: [64,4096]

Explanation:

i vali Current
nums		 ki kith
largest		 p New p = pk % (109 + 7)
0 3 [2, 3] 1 3 4 43 % (109 + 7) = 64
1 1 [2, 3, 1] 2 2 64 642 % (109 + 7) = 4096

Thus, ans = [64, 4096].

Example 2:

Input: nums = [7,5], p = 6, queries = [[4,3],[7,2]]

Output: [1296,220296870]

Explanation:

i vali Current​​​​​​​
nums		 ki kith
largest		 p New p = pk % (109 + 7)
0 4 [7, 5, 4] 3 4 6 64 % (109 + 7) = 1296
1 7 [7, 5, 4, 7] 2 7 1296 12967 % (109 + 7) = 220296870

Thus, ans = [1296, 220296870]

 

Constraints:

  • 1 <= nums.length <= 2 × 104
  • 1 <= nums[i] <= 106
  • ​​​​​​​1 <= p <= 106
  • 1 <= queries.length <= 2 × 104
  • ​​​​​​​1 <= vali <= 106
  • 1 <= ki <= n + i + 1
  • |ki - ki - 1| < 10 for i > 0

Approach Overview

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.

Approach 1: Two Sorted Sets

We use two sorted sets, l and r, to maintain the current array nums. All elements in l are less than or equal to those in r, and the number of elements in r is equal to k_i.

For each query, we insert val_i into r, then move the smallest element in r to l until the size of r becomes k_i. At this point, the smallest element in r is the k_i-th largest element in the current nums. We then use fast exponentiation to update p as p^x bmod (10^9 + 7), and append the updated p to the answer array.

The time complexity is O((n + m) log (n + m)), and the space complexity is O(n + m), where n and m are the lengths of nums and queries, respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 2: Sorted List

We use a sorted list sl to maintain the current array nums. For each query, we insert val_i into sl, then find the k_i-th largest element x in sl. Using fast exponentiation, we update p to p^x bmod (10^9 + 7), and append the updated p to the answer array.

The time complexity is O((n + m) log (n + m)), and the space complexity is O(n + m), where n and m are the lengths of nums and queries, respectively.

Code

PythonC++

Python

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two Sorted Sets—
Sorted List—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Re-sort After Each InsertionO(n log n)O(n)Simple baseline implementation or very small input sizes
Maintain Sorted ArrayO(n)O(n)When frequent lookups of ranked elements are required
Min-Heap of Size kO(n log k)O(k)Best general solution for streaming k-th largest queries

Frequently Asked Questions

Is Power Update After K-th Largest Insertion I easy or hard?
The problem is generally classified as Medium difficulty. The core idea—tracking the k-th largest element—requires understanding heap behavior and streaming updates. Developers familiar with priority queues can implement the optimal solution quickly.
Power Update After K-th Largest Insertion I Python/Java solution
Python solutions typically use the heapq module to maintain a min-heap, while Java implementations use PriorityQueue. In both languages, the algorithm inserts each new value, removes the smallest element if the heap exceeds size k, and reads the heap root to determine the k-th largest element.
How to solve Power Update After K-th Largest Insertion I in O(n log k)?
Maintain a min-heap containing at most k elements. Insert every new value into the heap and remove the smallest element if the heap grows beyond size k. After each insertion, the heap's root represents the current k-th largest element, which can be used to update the power value immediately.
What is the best approach for Power Update After K-th Largest Insertion I?
The most efficient approach uses a min-heap (priority queue) that stores only the largest k elements seen so far. Each insertion pushes a value into the heap and removes the smallest if the size exceeds k. The heap root always represents the k-th largest element, allowing constant-time access for power updates. This results in O(n log k) time and O(k) space.
Is Power Update After K-th Largest Insertion I asked at Google/Amazon/Meta?
Variants of k-th largest element streaming problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often test the ability to maintain running statistics using heaps or priority queues. The same technique appears in problems such as 'Kth Largest Element in a Stream'.
What data structure is used in Power Update After K-th Largest Insertion I?
A min-heap (priority queue) is the primary data structure used to track the k largest elements efficiently. The heap keeps the smallest among those k elements at the root, which corresponds to the current k-th largest value in the full dataset.
What is the time complexity of Power Update After K-th Largest Insertion I?
Using the optimal min-heap approach, each insertion requires O(log k) time because heap operations are logarithmic in the heap size. Processing n insertions therefore takes O(n log k). The space complexity is O(k) since the heap stores only the k largest elements.

Ready to solve this problem?

Practice Power Update After K-th Largest Insertion I with our built-in code editor and test cases.

Practice on FleetCode