Maximum Erasure Value | Leetcode 1695 | Two Pointer | Live coding session

Here is the solution to "Maximum Erasure Value" leetcode question. Hope you have a great time going through it.

Chapters
1) 0:00 Explaining the problem out loud
2) 1:00 Test case 1
2) 3:00 Test case 2
4) 8:00 Coding it up

For discussion/feedback

PS : Please increase the speed to 1.25X

[divyankmadan]

This solution is best available over internet, spent 3 hours hopping from one solution to another finally found yours

[NirmalSilwal]

brute force solution - O(N^2) time

public int maximumUniqueSubarray(int[] nums) {
// edge cases
if (nums == null || nums.length < 1) return 0;
if (nums.length == 1) return nums[0];

int maxsum = 0; // since nums[i] are positive,
Set<Integer> set = null; // to track each unique subarray

for (int i = 0; i < nums.length; i++) {

set = new HashSet<>(); // reset for each subarray from ith position
int currentsum = 0; // compute subarray sum

for (int j = i; j < nums.length; j++) {

if (!set.contains(nums[j])){
set.add(nums[j]);
currentsum += nums[j];
maxsum = Math.max(maxsum, currentsum);
} else
break;
}
}
return maxsum;
}




optimal solution - O(N) time

public int maximumUniqueSubarray(int[] nums) {
// edge cases
if (nums == null || nums.length < 1) return 0;
if (nums.length == 1) return nums[0];

int maxsum = 0;
Set<Integer> set = new HashSet<>();
int currentsum = 0;

// two pointers
int start = 0, end = 0;

while (end < nums.length) {
if (!set.contains(nums[end])) {
set.add(nums[end]);
currentsum += nums[end];
maxsum = Math.max(maxsum, currentsum);
end++;
} else {
currentsum -= nums[start];
set.remove(nums[start]);
start++;
}
}

return maxsum;
}

[abhishekvishwakarma]

This is just similar to Longest substring without repeating characters that way I got hint to solve this😁

[santoshvarma]

Is this approach also called as sliding window with variable window size?

[RupinderSingh-gshz]

what is the time complexity of remove operation of hashset as it is taking 40 ms to execute