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.
Quick Answer: 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.