We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Segment Sum After Removals

Difficulty: Hard

Problem Description

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.

Key Insights

  • Each removal can potentially split segments into smaller segments.
  • The maximum segment sum needs to be recalculated after each removal.
  • Using a union-find data structure can help efficiently manage segments.
  • We maintain active segments and their sums as we process each removal.

Space and Time Complexity

Time Complexity: O(n log n) - for union-find operations and updates. Space Complexity: O(n) - for storing segment sums and union-find structures.

Solution

To solve the problem, we can use a union-find (disjoint set union) data structure to keep track of the segments as we remove elements. Initially, all elements in nums are part of a single segment. When an element is removed, we check the surrounding elements to see if they form new segments. We update the maximum segment sum after each removal by merging the appropriate segments and recalculating their sums.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [0] * size
        self.max_sum = 0

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY
            self.size[rootY] += self.size[rootX]
            self.max_sum = max(self.max_sum, self.size[rootY])

def maxSegmentSumAfterRemovals(nums, removeQueries):
    n = len(nums)
    uf = UnionFind(n)
    answer = []
    active = [True] * n

    for i in range(n):
        idx = removeQueries[i]
        active[idx] = False
        uf.size[idx] = nums[idx]
        if idx > 0 and not active[idx - 1]:
            uf.union(idx, idx - 1)
        if idx < n - 1 and not active[idx + 1]:
            uf.union(idx, idx + 1)
        answer.append(uf.max_sum)

    return answer[::-1]
← Back to All Questions