Skip to main content
Talentd

Maximize Subarray Sum After Removing All Occurrences of One Element - Solution & Explanation

HardArrayDynamic ProgrammingSegment Tree3 min readAsked at: Google, Rubrik
Practice this problem

Problem Statement

You are given an integer array nums.

You can do the following operation on the array at most once:

  • Choose any integer x such that nums remains non-empty on removing all occurrences of x.
  • Remove all occurrences of x from the array.

Return the maximum subarray sum across all possible resulting arrays.

 

Example 1:

Input: nums = [-3,2,-2,-1,3,-2,3]

Output: 7

Explanation:

We can have the following arrays after at most one operation:

  • The original array is nums = [-3, 2, -2, -1, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = -3 results in nums = [2, -2, -1, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = -2 results in nums = [-3, 2, -1, 3, 3]. The maximum subarray sum is 2 + (-1) + 3 + 3 = 7.
  • Deleting all occurences of x = -1 results in nums = [-3, 2, -2, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = 3 results in nums = [-3, 2, -2, -1, -2]. The maximum subarray sum is 2.

The output is max(4, 4, 7, 4, 2) = 7.

Example 2:

Input: nums = [1,2,3,4]

Output: 10

Explanation:

It is optimal to not perform any operations.

 

Constraints:

  • 1 <= nums.length <= 105
  • -106 <= nums[i] <= 106

Approach Overview

Problem Overview: You get an integer array nums. Pick exactly one value x and remove all its occurrences from the array. After the removal, the array closes the gaps. Your goal is to compute the maximum possible subarray sum in the resulting array.

Approach 1: Try Removing Each Value + Kadane (O(n * u) time, O(1) space)

The most direct approach is to simulate the operation for every distinct value in the array. For a candidate value x, iterate through the array and skip all elements equal to x. While scanning the remaining elements, run Kadane’s algorithm to compute the maximum subarray sum. Repeat this process for every unique value u. This approach clearly demonstrates the problem mechanics but becomes slow when the array contains many distinct values because the entire array is scanned repeatedly.

Approach 2: Segment Tree with Temporary Updates (O(n log n) time, O(n) space)

A more scalable strategy uses a segment tree that stores the standard maximum subarray metrics: sum, maxPrefix, maxSuffix, and maxSubarray. First build the tree over the original array. Then group indices by value. For a value x, temporarily update all its positions in the tree to 0, which simulates removing those elements while allowing adjacent segments to merge. After applying these updates, the root node immediately gives the maximum subarray sum of the modified array. Record the result, then revert the updates before testing the next value.

This works because replacing removed elements with 0 preserves continuity of the subarray while eliminating their contribution. The segment tree recomputes prefix/suffix merges in O(log n) per update, making the total cost proportional to the number of elements processed.

Recommended for interviews: Interviewers typically expect a solution that avoids recomputing Kadane for every value. Explaining the brute force approach shows you understand the effect of removing a value. Implementing the optimized version with a segment tree and concepts from dynamic programming demonstrates stronger algorithmic thinking and reduces the complexity to O(n log n).

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Try Removing Each Value + KadaneO(n * u)O(1)Useful for understanding the problem or when the number of distinct values is very small
Segment Tree with Temporary UpdatesO(n log n)O(n)Best general solution for large arrays with many distinct values

Video Solution

3410. Maximize Subarray Sum After Removing All Occurrences of One Element (Leetcode Hard) • Programming Live with Larry • 1,062 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximize Subarray Sum After Removing All Occurrences of One Element easy or hard?
This problem is classified as Hard because it combines multiple ideas: maximum subarray computation, value grouping, and efficient updates using a segment tree or advanced dynamic programming. Handling all possible values efficiently is the main challenge.
Maximize Subarray Sum After Removing All Occurrences of One Element Python/Java solution
Most implementations build a segment tree over the array and group indices by value using a hash map. Each value’s indices are updated to zero, the tree’s max subarray value is queried, and the updates are reverted. The same strategy works consistently in Python, Java, C++, and Go.
How to solve Maximize Subarray Sum After Removing All Occurrences of One Element in O(n)?
A pure O(n) implementation is difficult because the maximum subarray must be recomputed after removing each value type. Most competitive solutions rely on a segment tree or advanced dynamic programming ideas, which lead to an O(n log n) time complexity while still handling large inputs efficiently.
What is the best approach for Maximize Subarray Sum After Removing All Occurrences of One Element?
The most efficient approach uses a Segment Tree that stores maximum subarray information (sum, prefix, suffix, and max subarray). For each distinct value, temporarily replace its positions with 0, query the tree for the maximum subarray sum, and then revert the changes. This reduces the overall complexity to O(n log n).
Is Maximize Subarray Sum After Removing All Occurrences of One Element asked at Google/Amazon/Meta?
Problems combining maximum subarray logic with structural modifications frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving Kadane’s algorithm, dynamic programming, and segment trees are common in high‑level algorithm rounds.
What data structure is used in Maximize Subarray Sum After Removing All Occurrences of One Element?
The optimal solution typically uses a Segment Tree to maintain maximum subarray metrics while performing temporary updates. The approach also relies on Kadane-style dynamic programming concepts to reason about maximum subarray sums.
What is the time complexity of Maximize Subarray Sum After Removing All Occurrences of One Element?
The optimized solution runs in O(n log n) time using a segment tree with point updates. Each element may be updated and reverted once, and every update takes O(log n). The brute force alternative can reach O(n^2) in the worst case if the array contains many unique values.

Ready to solve this problem?

Practice Maximize Subarray Sum After Removing All Occurrences of One Element with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Subarray

Next

Maximum Subarray Sum with One Deletion