Problem of The Day: Maximum Erasure Value

Problem Statement

leetcode problem link

Sliding Window Approach [Accepted]

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        left, right = 0, 0
        N = len(nums)
        freq = defaultdict(int)
        curr_val = 0
        res = 0
        for right in range(N):
            val = nums[right]
            freq[val] += 1

            while left < right and freq[val] > 1:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1

            res = max(res, sum(freq.keys()))
        return res

Editorial

Approach 1: Brute Force

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int n = nums.size(), result = 0;
        unordered_set<int> seen;
        for (int start = 0; start < n; start++) {
            // reset seen and current sum for next subarray
            seen.clear();
            int currentSum = 0;
            for (int end = start; end < n && (seen.find(nums[end]) == seen.end());
                 end++) {
                currentSum += nums[end];
                seen.insert(nums[end]);
            }
            // update result with maximum sum found so far
            result = max(result, currentSum);
        }
        return result;
    }
};

Approach 2: Two Pointer Approach Using Set

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int result = 0, currentSum = 0, start = 0;
        unordered_set<int> seen;
        for (int end = 0; end < nums.size(); end++) {
            // increment start until subarray has unique elements
            while (seen.find(nums[end]) != seen.end()) {
                seen.erase(nums[start]);
                currentSum -= nums[start];
                start++;
            }
            currentSum += nums[end];
            seen.insert(nums[end]);
            // update result with maximum sum found so far
            result = max(result, currentSum);
        }
        return result;
    }
};

Approach 3: Two Pointer Approach Using Boolean Array

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int result = 0, currentSum = 0, start = 0, k = 10001;
        vector<bool> isPresent(k, false);
        for (int end = 0; end < nums.size(); end++) {
            // increment start until subarray has unique elements
            while (isPresent[nums[end]]) {
                isPresent[nums[start]] = false;
                currentSum -= nums[start];
                start++;
            }
            isPresent[nums[end]] = true;
            currentSum += nums[end];
            // update result with maximum sum found so far
            result = max(result, currentSum);
        }
        return result;
    }
};

Approach 4: Two Pointer Approach Using Count Map

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int start = 0, result = 0, currentSum = 0, k = 10001;
        vector<int> countMap(k, 0);
        for (int end = 0; end < nums.size(); end++) {
            int currentElement = nums[end];
            countMap[currentElement]++;
            currentSum += currentElement;
            while (start < end && countMap[currentElement] > 1) {
                countMap[nums[start]]--;
                currentSum -= nums[start];
                start++;
            }
            // update result with maximum sum found so far
            result = max(result, currentSum);
        }
        return result;
    }
};

Approach 5: Using Prefix Sum with HashMap

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int n = nums.size(), result = 0, start = 0;
        unordered_map<int, int> lastIndexMap;
        vector<int> prefixSum(n + 1, 0);

        for (int end = 0; end < n; end++) {
            int currentElement = nums[end];
            prefixSum[end + 1] = prefixSum[end] + currentElement;
            if (lastIndexMap.find(currentElement) != lastIndexMap.end()) {
                start = max(start, lastIndexMap[currentElement] + 1);
            }
            // update result with maximum sum found so far
            result = max(result, prefixSum[end + 1] - prefixSum[start]);
            lastIndexMap[currentElement] = end;
        }
        return result;
    }
};