#2382

Hard

LeetCode Problem Workspace

Maximum Segment Sum After Removals

Calculate the maximum segment sum after sequential removals using array plus union find for efficient merging of segments.

array union find prefix sum ordered set

Problem Statement

You are given two integer arrays nums and removeQueries, both of length n. Each removeQueries[i] indicates the index in nums to remove. Removing an element splits the array into separate segments of positive numbers.

A segment is a contiguous subsequence of positive integers in nums. The sum of a segment is the total of its elements. Return an array answer of length n where answer[i] is the maximum segment sum after performing the first i removals in removeQueries.

Examples

Example 1

Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]

Output: [14,7,2,2,0]

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]

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.length
1 <= n <= 105
1 <= nums[i] <= 109
0 <= removeQueries[i] < n
All the values of removeQueries are unique.

Solution Approach

Use Reverse Removals with Union Find

Process removeQueries in reverse order to add elements back. Maintain a union find structure to track connected segments. Each union updates the sum of a segment efficiently.

Maintain Segment Sums with a Map

Store segment sums in a dictionary keyed by root indices in union find. When merging two segments, update the sum and track the maximum segment sum at each step.

Leverage Ordered Set for Active Indices

Use an ordered set or balanced tree to quickly identify neighboring segments when adding an element back. This avoids scanning the entire array and keeps updates logarithmic.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to ordered set operations and union find with path compression. Space complexity is O(n) for union find parent arrays and segment sum tracking.

What Interviewers Usually Probe

Expect candidates to identify that brute force scanning after each removal is too slow.
Look for using union find or segment tree to merge contiguous segments efficiently.
Check if candidates handle segment sum updates correctly when neighbors are added back.

Common Pitfalls or Variants

Common pitfalls

Failing to update segment sums correctly after merging two segments.
Iterating removals in forward order causing repeated full scans of the array.
Not handling edge cases when the first or last element is removed.

Follow-up variants

Compute minimum segment sum after removals instead of maximum.
Track the number of segments exceeding a given threshold after each removal.
Perform removals in batches and return the maximum segment sum after each batch.

FAQ

What is the main pattern used in Maximum Segment Sum After Removals?

The key pattern is Array plus Union Find, which allows efficient tracking and merging of contiguous segments after removals.

Can this problem be solved without union find?

Yes, but naive scanning after each removal is O(n^2) and will time out. Union find or ordered set structures make it efficient.

Why is processing removals in reverse beneficial?

Adding elements back in reverse allows merging segments efficiently and avoids recalculating sums from scratch each time.

How do we track maximum segment sums after each removal?

Use a union find with segment sums, updating the sum during unions and maintaining the current maximum.

What common mistakes should I avoid?

Failing to merge neighbor segments correctly, mismanaging segment sums, and iterating in forward order without efficient structures.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def merge(a, b):
            pa, pb = find(a), find(b)
            p[pa] = pb
            s[pb] += s[pa]

        n = len(nums)
        p = list(range(n))
        s = [0] * n
        ans = [0] * n
        mx = 0
        for j in range(n - 1, 0, -1):
            i = removeQueries[j]
            s[i] = nums[i]
            if i and s[find(i - 1)]:
                merge(i, i - 1)
            if i < n - 1 and s[find(i + 1)]:
                merge(i, i + 1)
            mx = max(mx, s[find(i)])
            ans[j - 1] = mx
        return ans

Continue Practicing

#2251 number of flowers in full bloom #2381 shifting letters ii #2389 longest subsequence with limited sum