Maximum Erasure Value

Medium
249.

Maximum Erasure Value

Maximum Erasure Value is a medium coding problem on arrays, hash table and sliding window, asked in Amazon and Google interviews.

You are given an array of positive integers nums. Erase one subarray in which all elements are distinct, and score the sum of its elements.

Return the maximum score obtainable.

Example 1

Input
nums = [4,2,4,5,6]
Output
17
Explanation
The best distinct subarray is [4,5,6].

Example 2

Input
nums = [5,2,1,2,5,2,1,2,5]
Output
8
Explanation
Either [5,2,1] or [1,2,5].

Example 3

Input
nums = [7]
Output
7

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumUniqueSubarray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Erasure Value — Solution in Python, Java & C++

Maximum Erasure Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Erasure Value is a medium coding problem on arrays, hash table and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sliding Window
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array of positive integers nums. Erase one subarray in which all elements are distinct, and score the sum of its elements.

Return the maximum score obtainable.

Example 1

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The best distinct subarray is [4,5,6].

Example 2

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: Either [5,2,1] or [1,2,5].

Example 3

Input: nums = [7]
Output: 7

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000

Hints for Maximum Erasure Value

  1. Hint 1

    This is the longest-substring-without-repeats window, scored by sum instead of by length.

  2. Hint 2

    Keep the window's values in a hash set and its running sum alongside.

  3. Hint 3

    When the entering value is already inside, shrink from the left until the duplicate is gone.

How to solve Maximum Erasure Value

It is the longest-substring-without-repeats window, scored by sum: keep a set of the window's values and a running sum, and evict from the left whenever the entering value is already present.

Approach

  1. For each right, while nums[right] is in the set, remove nums[left] from the set and the sum, advance left.
  2. Add nums[right] to the set and the sum.
  3. Update the best with the current sum.

Why it works

The window always holds distinct values, and because every value is positive the best distinct window ending at right is the widest one — exactly what the eviction rule maintains.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Evict until the duplicate is gone, not just one element.

Reference solution

Python

def maximumUniqueSubarray(nums) -> int:
    seen = set()
    left = total = best = 0
    for right, x in enumerate(nums):
        while x in seen:
            seen.discard(nums[left])
            total -= nums[left]
            left += 1
        seen.add(x)
        total += x
        best = max(best, total)
    return best

Java

public static int maximumUniqueSubarray(int[] nums) {
    Set<Integer> inWindow = new HashSet<>();
    int left = 0, sum = 0, best = 0;
    for (int right = 0; right < nums.length; right++) {
        while (inWindow.contains(nums[right])) {
            inWindow.remove(nums[left]);
            sum -= nums[left];
            left++;
        }
        inWindow.add(nums[right]);
        sum += nums[right];
        if (sum > best) best = sum;
    }
    return best;
}

C++

int maximumUniqueSubarray(vector<int>& nums) {
    unordered_set<int> inWindow;
    int left = 0, sum = 0, best = 0;
    for (int right = 0; right < (int) nums.size(); right++) {
        while (inWindow.count(nums[right])) {
            inWindow.erase(nums[left]);
            sum -= nums[left];
            left++;
        }
        inWindow.insert(nums[right]);
        sum += nums[right];
        if (sum > best) best = sum;
    }
    return best;
}

JavaScript

var maximumUniqueSubarray = function(nums) {
    const inWindow = new Set();
    let left = 0, sum = 0, best = 0;
    for (let right = 0; right < nums.length; right++) {
        while (inWindow.has(nums[right])) {
            inWindow.delete(nums[left]);
            sum -= nums[left];
            left++;
        }
        inWindow.add(nums[right]);
        sum += nums[right];
        if (sum > best) best = sum;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets