Watch 4 video solutions for Maximum Segment Sum After Removals, a hard level problem involving Array, Union Find, Prefix Sum. This walkthrough by codingMohan has 3,159 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two 0-indexed integer arrays nums and removeQueries, both of length n. For the ith query, the element in nums at the index removeQueries[i] is removed, splitting nums into different segments.
A segment is a contiguous sequence of positive integers in nums. A segment sum is the sum of every element in a segment.
Return an integer array answer, of length n, where answer[i] is the maximum segment sum after applying the ith removal.
Note: The same index will not be removed more than once.
Example 1:
Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1] Output: [14,7,2,2,0] Explanation: Using 0 to indicate a removed element, the answer is as follows: Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1]. Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5]. Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2]. Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2]. Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments. Finally, we return [14,7,2,2,0].
Example 2:
Input: nums = [3,2,11,1], removeQueries = [3,2,1,0] Output: [16,5,3,0] Explanation: Using 0 to indicate a removed element, the answer is as follows: Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11]. Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2]. Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3]. Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments. Finally, we return [16,5,3,0].
Constraints:
n == nums.length == removeQueries.length1 <= n <= 1051 <= nums[i] <= 1090 <= removeQueries[i] < nremoveQueries are unique.Problem Overview: You are given an array nums and a sequence removeQueries. After each removal, the array splits into segments of remaining elements. The task is to report the maximum segment sum after every removal.
The challenge is that removals dynamically break the array into smaller segments. Recomputing segment sums from scratch after every operation would be far too slow. Efficient solutions maintain segment boundaries and sums as elements disappear.
Approach 1: Ordered Set + Prefix Sum Simulation (O(n log n) time, O(n) space)
Precompute prefix sums so any segment sum can be calculated in constant time using prefix[r+1] - prefix[l]. Maintain current segments using an ordered structure such as a balanced tree or sorted set storing segment boundaries. When an index is removed, locate the segment containing it, split that segment into two smaller ones, and update their sums. Track the maximum segment sum with a heap or ordered structure. Each removal performs a logarithmic lookup and update, giving O(n log n) total time and O(n) space. This method relies heavily on efficient range calculations using prefix sum and boundary management with an ordered set.
Approach 2: Reverse Processing with Union-Find (O(n α(n)) time, O(n) space)
The key insight is that handling deletions directly is hard, but additions are easy. Instead of removing elements forward, process the queries in reverse and gradually add elements back. Initially all positions are inactive. When you restore an index, mark it active and merge it with active neighbors using Union Find. Each component represents a contiguous segment, and you maintain its total sum. After each activation, update the maximum segment sum. The answer for removal step i corresponds to the maximum value before the next element is restored. This approach avoids repeated splitting and instead performs efficient merges, resulting in near linear time.
Union-Find stores the parent of each index and the sum of its segment. When activating an index, check the left and right neighbors. If they are active, union the components and update the combined sum. Track the current maximum segment sum during each step.
Recommended for interviews: Reverse processing with Union-Find is the expected solution. It transforms a difficult deletion problem into a sequence of merges and achieves near O(n) performance. The ordered set simulation demonstrates understanding of segment management, but the Union-Find approach shows deeper algorithmic insight and is typically what interviewers look for in hard array problems involving dynamic segments.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Ordered Set + Prefix Sum | O(n log n) | O(n) | When simulating removals directly and maintaining dynamic segment boundaries |
| Reverse Processing with Union-Find | O(n α(n)) | O(n) | Optimal approach for large inputs where segments must merge efficiently |
| Naive Recompute Segments | O(n²) | O(1) | Educational baseline to understand how removals affect segments |