Power Update After K-th Largest Insertion II solution and explanation
The problem
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].
For each query:
- Insert
valiintonums. - Let
xbe thekithlargest element in the currentnums. - Update
ptopx % (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 |
Currentnums |
ki |
kithlargest |
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 |
Currentnums |
ki |
kithlargest |
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 * 1041 <= nums[i] <= 1091 <= p <= 1091 <= queries.length <= 2 * 1041 <= vali <= 1091 <= ki <= n + i + 1
Approach overview
Problem Overview: You receive a sequence of insertions and must continuously track the k-th largest element in the structure. After each insertion, a "power" value must be updated based on the current ordering of elements relative to that k-th largest threshold. A naive recomputation quickly becomes too slow as the dataset grows.
Approach 1: Re-sort After Every Insertion (Brute Force) (Time: O(n log n) per update, Space: O(n))
The simplest idea stores all inserted values in a list. After each insertion, sort the entire array and read the element at index n - k to obtain the k-th largest value. Once that value is known, recompute the power metric by iterating through the elements that influence the formula. This approach is easy to reason about and helps confirm correctness for small inputs. The downside is the repeated sort operation, which makes it impractical for large streams of updates.
Approach 2: Min Heap of Size K (Time: O(n log k), Space: O(k))
A more efficient approach maintains a min heap containing only the top k elements seen so far. The smallest element in the heap is always the current k-th largest. When a new value arrives, push it into the heap and remove the smallest element if the heap grows beyond size k. The heap root immediately gives the updated threshold needed to compute the power update. This technique relies on operations such as push and pop, each costing O(log k). Heaps are a common pattern in streaming problems involving order statistics and appear frequently in heap-based interview questions.
Approach 3: Fenwick Tree / Order Statistic Structure (Time: O(n log n), Space: O(n))
When the power update depends on aggregate information about many elements, maintaining only the k largest may not be enough. Instead, compress the value range and store frequencies in a Fenwick Tree (Binary Indexed Tree). Each insertion updates the frequency structure, and a binary search over prefix sums finds the index corresponding to the k-th largest value. Additional Fenwick trees or prefix sums can maintain sums needed for the power calculation. Each update and query runs in O(log n). This pattern is common in problems involving dynamic ranks and appears frequently alongside segment tree and binary search techniques.
Recommended for interviews: The min‑heap solution is usually the expected answer if the task only requires tracking the k-th largest element in a stream. It reduces the complexity from repeated sorting to O(n log k). If the power update depends on aggregated values across the dataset, interviewers often expect a Fenwick Tree or segment tree because it supports fast rank queries and prefix computations. Mentioning the brute force approach first shows baseline reasoning, while presenting the heap or Fenwick solution demonstrates algorithmic optimization skills.
Solution
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.
class Solution:
def powerUpdate(
self, nums: list[int], p: int, queries: list[list[int]]
) -> list[int]:
ans = []
sl = SortedList(nums)
mod = 10**9 + 7
for val, k in queries:
sl.add(val)
p = pow(p, sl[-k], mod)
ans.append(p)
return ans#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_multiset = tree<pair<T, int>, null_type, less<pair<T, int>>,
rb_tree_tag, tree_order_statistics_node_update>;
class Solution {
public:
vector<int> powerUpdate(vector<int>& nums, int p, vector<vector<int>>& queries) {
vector<int> ans;
ordered_multiset<int> sl;
const int mod = 1e9 + 7;
for (int i = 0; i < nums.size(); i++) {
sl.insert({nums[i], i});
}
int next_id = nums.size();
auto mod_pow = [&](long long base, long long exp) -> long long {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
};
for (const auto& query : queries) {
int val = query[0];
int k = query[1];
sl.insert({val, next_id++});
auto it = sl.find_by_order(sl.size() - k);
int kth_largest = it->first;
p = mod_pow(p, kth_largest);
ans.push_back(p);
}
return ans;
}
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Re-sort after every insertion | O(n log n) per update | O(n) | Small inputs or verifying correctness during prototyping |
| Min heap of size k | O(n log k) | O(k) | Streaming insertions where only the k-th largest threshold matters |
| Fenwick tree / order statistic tree | O(n log n) | O(n) | Large datasets requiring rank queries and aggregated power calculations |
Frequently asked questions
Is Power Update After K-th Largest Insertion II easy or hard?
Power Update After K-th Largest Insertion II is classified as a Hard problem because it combines streaming updates with order-statistic queries. Efficient solutions require familiarity with heaps, Fenwick trees, or segment trees and careful complexity management.
Power Update After K-th Largest Insertion II Python/Java solution
In Python, the solution typically uses the heapq module to maintain a min heap of size k. In Java, PriorityQueue provides the same behavior. For advanced implementations, Fenwick trees or segment trees are used to maintain dynamic order statistics.
How to solve Power Update After K-th Largest Insertion II in O(n log n)?
Use coordinate compression and maintain frequencies with a Fenwick Tree. Each insertion updates the tree in O(log n), and a binary search over prefix sums finds the k-th largest value. Additional prefix-sum queries compute any required power updates efficiently.
What is the best approach for Power Update After K-th Largest Insertion II?
The most practical solution maintains the k largest elements using a min heap of size k. Each insertion pushes a value into the heap and removes the smallest if the heap exceeds size k, keeping the root equal to the current k-th largest element. This keeps updates at O(log k) time while using O(k) space.
Is Power Update After K-th Largest Insertion II asked at Google/Amazon/Meta?
Problems involving maintaining the k-th largest element in a dynamic stream appear frequently in interviews at companies such as Google, Amazon, and Meta. Variations often combine heaps with additional data structures like segment trees or prefix sums to track extra metrics.
What data structure is used in Power Update After K-th Largest Insertion II?
Common choices include a min heap for tracking the top k elements and Fenwick Trees or segment trees for maintaining frequency counts and prefix sums. These structures support efficient rank queries and updates required after each insertion.
What is the time complexity of Power Update After K-th Largest Insertion II?
A brute force solution that sorts after every insertion costs O(n log n) per update. The optimized heap approach reduces this to O(log k) per insertion. If the power calculation requires aggregated statistics, Fenwick tree or segment tree solutions typically run in O(log n) per update.