{x}
blog image

Maximum Segment Sum After Removals

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

Solution Explanation

This problem requires finding the maximum segment sum after each removal query. A segment is defined as a contiguous sequence of positive integers. The solution uses a Union-Find data structure to efficiently track segments and their sums after each removal.

Algorithm:

  1. Initialization:

    • p: A parent array for the Union-Find structure. Initially, each element is its own parent (p[i] = i).
    • s: An array to store the sum of each segment. Initially, all are 0.
    • ans: An array to store the results (maximum segment sums after each query).

  2. Iteration (Reverse Order): The code iterates through the removeQueries array in reverse order. This is crucial because it allows us to build up the segments from the final state (all elements removed) to the initial state.

  3. Removal and Segment Update:

    • For each query, the element at index removeQueries[j] is effectively "removed" by assigning its sum to s[i] = nums[i].
    • The code checks the neighbors of the removed element (i-1 and i+1). If a neighbor has a positive sum (it's part of a segment), it merges the segments using the merge function (Union-Find operation).
    • The merge function uses path compression for efficiency in Union-Find.

  4. Maximum Segment Sum:

    • After merging, s[find(i)] gives the sum of the segment containing element i.
    • mx keeps track of the global maximum segment sum encountered so far.
    • ans[j-1] is updated with the current maximum segment sum mx.

  5. Result: The ans array is returned.

Time Complexity:

The main loop iterates n times (where n is the length of nums and removeQueries). The find and merge operations in the Union-Find structure take (amortized) O(α(n)) time, where α(n) is the inverse Ackermann function, which is practically a constant for all reasonable input sizes. Therefore, the overall time complexity is O(n).

Space Complexity:

The space complexity is dominated by the arrays p, s, and ans, all of which have size O(n). Therefore, the space complexity is O(n).

Code Explanation (Python):

The Python code directly implements the algorithm described above. The find function finds the root of a set in the Union-Find structure. The merge function unions two sets by setting the parent of one root to the other. The main part of the code performs the removal and segment updates iteratively.

Code Explanation (Other Languages):

The Java, C++, and Go codes implement the same algorithm with similar data structures and logic, ensuring efficient handling of the Union-Find operations and the iterative process of segment merging. The core concepts remain the same across all languages.