Maximum Erasure Value - Practice Coding Problems

Maximum Erasure Value - Problem

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.

A subarray 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).

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,4,5,6]

› Output: 17

💡 Note: The optimal subarray is [2,4,5,6] with all unique elements and sum = 2+4+5+6 = 17

Example 2 — Single Element

$ Input: nums = [5,2,1,2,5,2,1,2,5]

› Output: 8

💡 Note: The optimal subarray is [5,2,1] with sum = 5+2+1 = 8

Example 3 — All Unique

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

› Output: 10

💡 Note: All elements are unique, so we take the entire array: 1+2+3+4 = 10

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with possible duplicates: [4,2,4,5,6]

Find Unique Subarrays

Identify all contiguous subarrays with unique elements

Maximum Sum

Return sum of optimal subarray: 17

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently find the longest unique subarray with maximum sum

Asked in

a Amazon 25 M Microsoft 18 G Google 12

The key insight is to use a sliding window with a hash set to maintain unique elements efficiently. The optimal approach uses two pointers that expand and contract the window, achieving O(n) time complexity while tracking the maximum sum of any subarray with unique elements.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Hash Set	O(n)	O(n)	Use expanding and contracting window to maintain unique elements
Brute Force - Check All Subarrays	O(n³)	O(n)	Try every possible subarray and check if elements are unique

Sliding Window with Hash Set — Algorithm Steps

Step 1: Use left and right pointers with hash set to track elements
Step 2: Expand right pointer, add element to set and sum
Step 3: When duplicate found, contract left until duplicate removed
Step 4: Track maximum sum throughout the process

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Right

Add new elements to window

Contract Left

Remove duplicates from left

Track Maximum

Update best sum continuously

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int numsSize) {
    int left = 0;
    int maxSum = 0;
    int currentSum = 0;
    bool seen[100001] = {false};
    
    for (int right = 0; right < numsSize; right++) {
        while (seen[nums[right]]) {
            seen[nums[left]] = false;
            currentSum -= nums[left];
            left++;
        }
        
        seen[nums[right]] = true;
        currentSum += nums[right];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    
    return maxSum;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[10000];
    int size = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is added and removed from set at most once

✓ Linear Growth

Space Complexity

O(n)

Hash set stores at most n unique elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Hash Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler