Apply Range Overwrite Queries
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given an integer array `nums` of length `n` and a list of range-assignment queries. Each query is a tuple `(left, right, value)`, where `left` and `right` define an inclusive index range, and the operation means:
- for every index `i` such that `left <= i <= right`, set `nums[i] = value`
All queries are applied **in the given order**, so later queries overwrite earlier updates on overlapping positions.
Return the final state of the array after processing all queries.
Your solution should be as efficient as possible.
Example:
- `nums = [1,2,3,4,5]`
- `queries = [(1,3,9), (2,4,7)]`
After the first query: `[1,9,9,9,5]`
After the second query: `[1,9,7,7,7]`
Return `[1,9,7,7,7]`.
You may assume:
- `0 <= left <= right < n`
- `n` and the number of queries can both be large, so a naive `O(n * q)` approach may be too slow.
Overview: This question evaluates a candidate's competency in array manipulation and range-update algorithms, focusing on efficient handling of batch assignments and overlapping updates.
You are given an integer array `nums` and a list of range-assignment queries. Each query is a tuple `(left, right, value)`, meaning every element from index `left` to index `right` inclusive should be set to `value`.
Queries are applied in the given order, so later queries overwrite earlier ones on overlapping positions.
Return the final state of the array after processing all queries.
A naive `O(n * q)` simulation may be too slow for large inputs, so your solution should be as efficient as possible.
Constraints
- 0 <= n <= 200000
- 0 <= q <= 200000, where q = len(queries)
- -10^9 <= nums[i], value <= 10^9
- For every query `(left, right, value)`, `0 <= left <= right < n` when `n > 0`
Examples
Input: ([1, 2, 3, 4, 5], [(1, 3, 9), (2, 4, 7)])
Expected Output: [1, 9, 7, 7, 7]
Explanation: After `(1,3,9)`, the array becomes `[1, 9, 9, 9, 5]`. After `(2,4,7)`, positions 2 through 4 are overwritten, giving `[1, 9, 7, 7, 7]`.
Input: ([5, 6, 7], [])
Expected Output: [5, 6, 7]
Explanation: There are no queries, so the array stays unchanged.
Hints
- Try processing the queries from last to first. The first time you assign an index in reverse order, you already know its final value.
- Use a disjoint-set / union-find style 'next unfilled index' structure so you can skip positions that have already been finalized.
Community answers
Answer by Luna
def apply_range_assignments(
nums: list[int],
queries: list[tuple[int, int, int]]
) -> list[int]:
n = len(nums)
result = nums[:]
parent = list(range(n + 1))
def find(x: int) -> int:
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for left, right, value in reversed(queries):
i = find(left)
while i <= right:
result[i] = value
next_i = find(i + 1)
parent[i] = next_i
i = next_i
return result
Answer by bugsbunny
class RangeQueries{
public:
vector rangeOverwrite(vector& nums, const vector> &queries){
int n = nums.size();
if(queries.size()==0){
return nums;
}
parent.resize(n+1);
for(int i=0;i=0;i--){
int l = queries[i][0];
int r = queries[i][1];
int value = queries[i][2];
int idx = find(l);
while(idx<=r){
nums[idx] = value;
parent[idx] = idx+1;
idx = find(idx);
}
}
return nums;
}
private:
vector parent;
int find(int x){
if(x!=parent[x]){
parent[x] = find(parent[x]);
return parent[x];
}
return x;
}
};