LeetCode 2382: Maximum Segment Sum After Removals

Meta Data

#

Difficulty: hard First Attempt: 2026-07-26

• Submissions: Time Limit Exceeded ×2 → Accepted → Wrong Answer → Accepted

Approach

#

Removing elements one by one splits segments, but Union-Find can only merge. Work backward (Union-Find, work backward): start with everything removed and add elements back in reverse order, merging with existing neighbors on the left and right.

• Each root stores its segment sum total[root].
• In reverse, segments only grow and sums only increase (all numbers are positive), so a single variable holds the current maximum.
• The answer after the i-th removal is the maximum before removeQueries[i] is added back.

My Attempts

#

Solution

#

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        parent = list(range(n))
        total = [0] * n
        alive = [False] * n

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        res, best = [], 0
        for i in reversed(removeQueries):
            res.append(best)                       # the answer before i is added back
            alive[i] = True
            total[i] = nums[i]
            for j in (i - 1, i + 1):
                if 0 <= j < n and alive[j]:
                    rj, ri = find(j), find(i)
                    parent[rj] = ri
                    total[ri] += total[rj]
            best = max(best, total[find(i)])
        return res[::-1]

Complexity

#

Time O(n · α(n)), space O(n).

Mistakes to Avoid

#

• Do not recompute the maximum over all sets each step.
• With lazy deletion, decrement the matching count whenever one is popped.
• Record the answer before adding back, and reverse at the end.

Interview Explanation

#

Removal splits segments and Union-Find cannot split, so I add elements back in reverse, merging with existing neighbors and storing sums at the root. All numbers are positive, so the maximum only grows and a single variable holds it. The maximum before each addition is the answer for that removal, reversed at the end. Time O(n α(n)).