Maximum Erasure Value
MedPrompt
You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.
Return the maximum score you can get by erasing exactly one subarray.
An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).
Example 1:
Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].Example 2:
Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward but naive approach. The idea is to generate every possible contiguous subarray of the input array nums. For each of these subarrays, we first check if it contains only unique elements. If it does, we then calculate its sum and update the maximum score found so far if the current sum is greater.
Algorithm
- Initialize
maxScoreto 0. - Use a nested loop to generate all possible start
iand endjindices of a subarray. - For each subarray
nums[i...j], create a third loop fromk = itoj. - Inside the third loop, use a
HashSetto check for uniqueness. If a duplicate is found, the subarray is invalid. - If the subarray is unique after checking all its elements, calculate its sum.
- Update
maxScore = max(maxScore, currentSum). - After all subarrays are checked, return
maxScore.
Walkthrough
We can implement this using three nested loops. The outer two loops, with indices i and j, define the start and end of a subarray. The third loop, with index k, iterates through this subarray nums[i...j]. Inside this innermost loop, we use a HashSet to keep track of the elements we've seen in the current subarray. If we encounter an element that's already in the set, we know the subarray is not unique. If the loop completes without finding duplicates, we calculate the sum and update our global maximum score. This process is repeated for all O(n^2) possible subarrays.
import java.util.HashSet;import java.util.Set; class Solution { public int maximumUniqueSubarray(int[] nums) { int maxScore = 0; for (int i = 0; i < nums.length; i++) { for (int j = i; j < nums.length; j++) { Set<Integer> uniqueElements = new HashSet<>(); int currentSum = 0; boolean isUnique = true; // Check for uniqueness and calculate sum for subarray nums[i...j] for (int k = i; k <= j; k++) { if (!uniqueElements.add(nums[k])) { isUnique = false; break; } currentSum += nums[k]; } if (isUnique) { maxScore = Math.max(maxScore, currentSum); } } } return maxScore; }}Complexity
Time
O(n^3). There are O(n^2) subarrays, and for each subarray, we iterate through its elements to check for uniqueness and calculate the sum, which takes up to O(n) time.
Space
O(n), as the `HashSet` can store up to `n` elements for a subarray of length `n`.
Trade-offs
Pros
Simple to understand and conceptualize.
Cons
Extremely inefficient due to three nested loops.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
This approach improves upon the pure brute-force method by being slightly more intelligent. Instead of re-generating and re-validating each subarray from scratch, we can fix the starting point of a subarray and extend it to the right one element at a time. We maintain a running sum and check for uniqueness as we expand.
Algorithm
- Initialize
maxScoreto 0. - Loop
ifrom0ton-1(this will be the starting index of our subarrays). - Inside this loop, initialize an empty
HashSetcalledseenand acurrentSumto 0. - Start a second loop with
jfromiton-1. - In the inner loop, check if
nums[j]is already inseen.- If it is, this means the subarray
nums[i...j]contains a duplicate. We break the inner loop and move to the next starting indexi+1. - If it's not, we add
nums[j]toseen, add its value tocurrentSum, and updatemaxScore = max(maxScore, currentSum).
- If it is, this means the subarray
- Return
maxScoreafter the loops complete.
Walkthrough
We use two nested loops. The outer loop fixes the starting index i of a potential subarray. For each i, the inner loop extends the subarray by moving an ending index j from i to the end of the array. We use a HashSet to keep track of the elements in the current subarray nums[i...j] and a variable to maintain its sum. As we increment j, we check if nums[j] would be a duplicate. If it is, we know that any further subarray starting at i will also contain this duplicate, so we can stop and move to the next starting position i+1. If nums[j] is unique, we add it to our set and sum, and update the maximum score.
import java.util.HashSet;import java.util.Set; class Solution { public int maximumUniqueSubarray(int[] nums) { int maxScore = 0; for (int i = 0; i < nums.length; i++) { Set<Integer> seen = new HashSet<>(); int currentSum = 0; for (int j = i; j < nums.length; j++) { if (seen.contains(nums[j])) { // Subarray from i is no longer unique, break and try from i+1 break; } seen.add(nums[j]); currentSum += nums[j]; maxScore = Math.max(maxScore, currentSum); } } return maxScore; }}Complexity
Time
O(n^2). The two nested loops lead to a quadratic time complexity. The operations inside the inner loop (HashSet add/contains) take O(1) on average.
Space
O(n). The `HashSet` can store up to `n` elements in the worst-case scenario where all elements in the array are unique.
Trade-offs
Pros
More efficient than the O(n^3) brute-force approach.
Reduces redundant computations by building subarrays incrementally.
Cons
This approach is still too slow for large inputs as specified by the problem constraints (n <= 10^5) and will likely time out.
The most efficient solution uses the sliding window pattern. This technique is ideal for problems involving contiguous subarrays. We maintain a 'window' (a subarray) that is always guaranteed to have unique elements. We try to expand this window to the right as much as possible. When we encounter a duplicate element, we shrink the window from the left until it becomes valid again. Throughout this process, we keep track of the sum of the current window's elements and update the maximum score.
Algorithm
- Initialize two pointers,
left = 0andright = 0. - Initialize
maxScore = 0,currentSum = 0. - Use a
HashSetnamedwindowElementsto store elements in the current windownums[left...right]. - Iterate with the
rightpointer from0ton-1. - Inside the loop, check if
nums[right]is already inwindowElements.- If it is, it's a duplicate. Shrink the window from the left: repeatedly subtract
nums[left]fromcurrentSum, removenums[left]fromwindowElements, and incrementleft, untilnums[right]is no longer in the set.
- If it is, it's a duplicate. Shrink the window from the left: repeatedly subtract
- Now that the window is valid, expand it: add
nums[right]tocurrentSumandwindowElements. - The current window
nums[left...right]is unique. UpdatemaxScore = max(maxScore, currentSum). - After the loop, return
maxScore.
Walkthrough
We use two pointers, left and right, to define the boundaries of our sliding window. A HashSet is used to efficiently check for the existence of an element in the current window. We iterate through the array with the right pointer to expand the window. If nums[right] is already in our set, it means we have a duplicate. To fix this, we shrink the window from the left by incrementing the left pointer and removing nums[left] from the set and the running sum. We repeat this until the element at nums[right] is no longer a duplicate in the window nums[left...right-1]. After ensuring uniqueness, we add nums[right] to the window (and the set/sum). At each step after expansion, the window is valid, so we update our maximum score. Since each element is visited by the left and right pointers at most once, the overall time complexity is linear.
import java.util.HashSet;import java.util.Set; class Solution { public int maximumUniqueSubarray(int[] nums) { int n = nums.length; Set<Integer> windowElements = new HashSet<>(); int maxScore = 0; int currentSum = 0; int left = 0; for (int right = 0; right < n; right++) { // Shrink the window from the left if the new element is already present while (windowElements.contains(nums[right])) { currentSum -= nums[left]; windowElements.remove(nums[left]); left++; } // Expand the window from the right currentSum += nums[right]; windowElements.add(nums[right]); // Update the maximum score with the sum of the current unique subarray maxScore = Math.max(maxScore, currentSum); } return maxScore; }}Complexity
Time
O(n). Both the `right` and `left` pointers traverse the array at most once, and each element is added to and removed from the `HashSet` at most once. All set operations take O(1) on average.
Space
O(k), where `k` is the number of unique values in the input array. Given the constraint `1 <= nums[i] <= 10^4`, the space is at most O(10001). In the general case, it's O(min(n, k)).
Trade-offs
Pros
Optimal time complexity of O(n), making it very efficient for large inputs.
Efficient use of space.
Cons
Can be slightly more complex to implement correctly compared to brute-force methods.
Solutions
Solution
class Solution: def maximumUniqueSubarray(self, nums: List[int]) -> int: d = defaultdict(int) s = list(accumulate(nums, initial=0)) ans = j = 0 for i, v in enumerate(nums, 1): j = max(j, d[v]) ans = max(ans, s[i] - s[j]) d[v] = i return ansclass Solution {public int maximumUniqueSubarray(int[] nums) { int[] d = new int[10001]; int n = nums.length; int[] s = new int[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } int ans = 0, j = 0; for (int i = 1; i <= n; ++i) { int v = nums[i - 1]; j = Math.max(j, d[v]); ans = Math.max(ans, s[i] - s[j]); d[v] = i; } return ans; }}class Solution {public: int maximumUniqueSubarray(vector<int> &nums) { int d[10001]{}; int n = nums.size(); int s[n + 1]; s[0] = 0; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } int ans = 0, j = 0; for (int i = 1; i <= n; ++i) { int v = nums[i - 1]; j = max(j, d[v]); ans = max(ans, s[i] - s[j]); d[v] = i; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.