Power Update After K-th Largest Insertion I 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] and the difference between consecutive ki values is always less than 10.
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] <= 1061 <= p <= 1061 <= queries.length <= 2 × 1041 <= vali <= 1061 <= ki <= n + i + 1|ki - ki - 1| < 10fori > 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.
class Solution:
def powerUpdate(
self, nums: list[int], p: int, queries: list[list[int]]
) -> list[int]:
l = SortedList()
r = SortedList(nums)
ans = []
mod = 10**9 + 7
for val, k in queries:
r.add(val)
l.add(r.pop(0))
while len(r) < k:
r.add(l.pop())
while len(r) > k:
l.add(r.pop(0))
x = r[0]
p = pow(p, x, mod)
ans.append(p)
return ansclass Solution {
private void add(TreeMap<Integer, Integer> t, int x) {
t.merge(x, 1, Integer::sum);
}
private void remove(TreeMap<Integer, Integer> t, int x) {
int v = t.get(x);
if (v == 1) {
t.remove(x);
} else {
t.put(x, v - 1);
}
}
private long qpow(long a, int b, int mod) {
long ans = 1;
while (b > 0) {
if ((b & 1) == 1) {
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
public List<Integer> powerUpdate(int[] nums, int p, int[][] queries) {
TreeMap<Integer, Integer> l = new TreeMap<>();
TreeMap<Integer, Integer> r = new TreeMap<>();
int sz1 = 0, sz2 = nums.length;
for (int x : nums) {
add(r, x);
}
int mod = 1_000_000_007;
List<Integer> ans = new ArrayList<>();
for (int[] q : queries) {
int val = q[0];
int k = q[1];
add(r, val);
++sz2;
int v = r.firstKey();
remove(r, v);
--sz2;
add(l, v);
++sz1;
while (sz2 < k) {
v = l.lastKey();
remove(l, v);
--sz1;
add(r, v);
++sz2;
}
while (sz2 > k) {
v = r.firstKey();
remove(r, v);
--sz2;
add(l, v);
++sz1;
}
int x = r.firstKey();
p = (int) qpow(p, x, mod);
ans.add(p);
}
return ans;
}
}class Solution {
public:
using ll = long long;
void add(map<int, int>& mp, int x) {
++mp[x];
}
void remove(map<int, int>& mp, int x) {
if (--mp[x] == 0) {
mp.erase(x);
}
}
ll qpow(ll a, int b, int mod) {
ll ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
vector<int> powerUpdate(vector<int>& nums, int p, vector<vector<int>>& queries) {
map<int, int> l, r;
int sz1 = 0, sz2 = nums.size();
for (int x : nums) {
add(r, x);
}
const int mod = 1e9 + 7;
vector<int> ans;
for (auto& q : queries) {
int val = q[0];
int k = q[1];
add(r, val);
++sz2;
int v = r.begin()->first;
remove(r, v);
--sz2;
add(l, v);
++sz1;
while (sz2 < k) {
v = l.rbegin()->first;
remove(l, v);
--sz1;
add(r, v);
++sz2;
}
while (sz2 > k) {
v = r.begin()->first;
remove(r, v);
--sz2;
add(l, v);
++sz1;
}
int x = r.begin()->first;
p = qpow(p, x, mod);
ans.push_back(p);
}
return ans;
}
};func powerUpdate(nums []int, p int, queries [][]int) []int {
l := redblacktree.New[int, int]()
r := redblacktree.New[int, int]()
merge := func(st *redblacktree.Tree[int, int], x, v int) {
c, _ := st.Get(x)
if c+v == 0 {
st.Remove(x)
} else {
st.Put(x, c+v)
}
}
sz1, sz2 := 0, len(nums)
for _, x := range nums {
merge(r, x, 1)
}
const mod int = 1e9 + 7
qpow := func(a, b int) int {
ans := 1
for b > 0 {
if b&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
b >>= 1
}
return ans
}
ans := make([]int, 0, len(queries))
for _, q := range queries {
val, k := q[0], q[1]
merge(r, val, 1)
sz2++
node := r.Left()
merge(r, node.Key, -1)
sz2--
merge(l, node.Key, 1)
sz1++
for sz2 < k {
node = l.Right()
merge(l, node.Key, -1)
sz1--
merge(r, node.Key, 1)
sz2++
}
for sz2 > k {
node = r.Left()
merge(r, node.Key, -1)
sz2--
merge(l, node.Key, 1)
sz1++
}
x := r.Left().Key
p = qpow(p, x)
ans = append(ans, p)
}
return ans
}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.
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)
x = sl[-k]
p = pow(p, x, 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 comparison
| Approach | Complexity |
|---|---|
| Two Sorted Sets | – |
| Sorted List | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Re-sort After Each Insertion | O(n log n) | O(n) | Simple baseline implementation or very small input sizes |
| Maintain Sorted Array | O(n) | O(n) | When frequent lookups of ranked elements are required |
| Min-Heap of Size k | O(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.