Maximum Erasure Value (Longest Unique Subarray Sum)
-
Arrays
- Find the Largest Element in an Array
- Find the Second Largest Element in an Array
- Reverse an Array In Place
- Check if an Array Is Sorted
- Remove Duplicates from a Sorted Array
- Move Zeroes to the End of an Array
- Rotate an Array by K Positions
- Two Sum
- Maximum Subarray Sum (Kadane's Algorithm)
- Best Time to Buy and Sell Stock
- Sort an Array of 0s, 1s and 2s (Dutch National Flag)
- Find the Missing Number in an Array
- Find the Duplicate Number in an Array
- Union of Two Sorted Arrays
- Intersection of Two Sorted Arrays
- Prefix Sum Array and Range Sum Queries
- Majority Element (Boyer-Moore Voting Algorithm)
- Merge Overlapping Intervals
- Next Permutation
- Product of Array Except Self
- Subarray Sum Equals K
- Merge Two Sorted Arrays In Place
- Maximum Product Subarray
- 3Sum: Find All Triplets That Sum to Zero
- Trapping Rain Water
- Container With Most Water
- Rotate Image (Matrix 90 Degree Rotation)
- Spiral Matrix Traversal
- Set Matrix Zeroes
- Kth Largest Element in an Array (Quickselect)
-
Strings
- Reverse a String In Place
- Check if a String Is a Palindrome
- Check if Two Strings Are Anagrams
- Count Frequency of Characters in a String
- First Non-Repeating Character in a String
- Reverse Words in a Sentence
- Check if a String Contains Only Digits
- Remove Duplicate Characters from a String
- Longest Substring Without Repeating Characters
- Group Anagrams
- Valid Parentheses
- String to Integer (atoi)
- Longest Common Prefix
- Implement strStr() - Naive Pattern Matching
- Run-Length Encoding of a String
- Check if a String Is a Rotation of Another
- Longest Palindromic Substring
- Minimum Window Substring
- Zigzag Conversion
- KMP Pattern Matching Algorithm
- Rabin-Karp Pattern Matching Algorithm
- Z-Algorithm for Pattern Matching
- Longest Palindromic Subsequence
- Edit Distance Between Two Strings
- Word Break Problem
- Decode Ways
- String Compression (In-Place)
- Count and Say
- Roman to Integer
- Integer to Roman
- Valid Palindrome II (At Most One Deletion)
- Longest Repeating Character Replacement
- Multiply Two Numbers Represented as Strings
- Why Strings Are Immutable (Interview Concept)
- Time Complexity of Common String Operations (Interview Co...
-
Sliding Window
- Maximum Sum Subarray of Size K (Fixed Window)
- Average of All Subarrays of Size K
- Maximum Number of Vowels in a Substring of Length K
- First Negative Integer in Every Window of Size K
- K Radius Subarray Averages
- Max Consecutive Ones
- Max Consecutive Ones III (At Most K Flips)
- Longest Subarray With Sum At Most K
- Minimum Size Subarray Sum
- Fruit Into Baskets (Longest Subarray With At Most 2 Disti...
- Longest Subarray With At Most K Distinct Elements
- Subarray Product Less Than K
- Maximum Average Subarray I
- Sliding Window Maximum (Monotonic Deque)
- Find All Anagrams in a String (Sliding Window)
- Repeated DNA Sequences (Fixed Window Hashing)
- Longest Turbulent Subarray
- Maximum Erasure Value (Longest Unique Subarray Sum)
- Longest Continuous Increasing Subsequence
- Grumpy Bookstore Owner
- Maximum Points You Can Obtain from Cards
- Binary Subarrays With Sum (Exactly K Trick)
- Count Number of Nice Subarrays (Exactly K Odd Numbers)
- Continuous Subarray Sum (Multiple of K)
- Minimum Operations to Reduce X to Zero
- Maximum Frequency After K Increments
- Sliding Window Median
- Substring With Concatenation of All Words
- Count Complete Subarrays in an Array
- Number of Subarrays With Bounded Maximum
- Maximum Sum of Distinct Subarrays With Length K
- Shortest Subarray With Sum At Least K (With Negatives)
- Fixed-Size vs Variable-Size Sliding Window (Interview Con...
- When to Use Sliding Window vs Two Pointers (Interview Con...
- Recognizing a Sliding Window Problem (Interview Concept)
-
Two Pointers
- Two Sum II - Input Array Is Sorted
- Valid Palindrome (Two Pointer Check)
- Reverse Vowels of a String
- Remove Element In Place
- Move Zeroes Using Two Pointers
- 3Sum Closest
- 4Sum
- Sort Array By Parity
- Squares of a Sorted Array
- Merge Two Sorted Arrays (Two Pointer)
- Intersection of Two Arrays II
- Backspace String Compare
- Trapping Rain Water (Two Pointer Approach)
- Container With Most Water (Two Pointer Approach)
- Partition Labels
- Sort Colors (Dutch National Flag Two Pointer)
- Remove Duplicates from Sorted Array II
- Linked List Cycle Detection (Fast and Slow Pointers)
- Middle of the Linked List
- Palindrome Linked List Check
- Boats to Save People
- Valid Triangle Number
- Minimum Number of Swaps to Make Sequences Increasing
- Sentence Similarity Using Two Pointers
- Shortest Distance to a Character
- Interleaving String Check
- DNA Complement Matching
- Is Subsequence Check (Two Pointer)
- Interview Concept: Same Direction vs Opposite Direction Two Pointers
- Interview Concept: Fast and Slow Pointer Technique Explained
-
Searching & Binary Search
- Binary Search (Classic Iterative)
- Binary Search (Recursive)
- Search Insert Position
- First and Last Position of Element in Sorted Array
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II (With Duplicates)
- Find Minimum in Rotated Sorted Array
- Find Peak Element
- Sqrt(x) Using Binary Search
- Koko Eating Bananas
- Capacity To Ship Packages Within D Days
- Split Array Largest Sum
- Median of Two Sorted Arrays
- Search a 2D Matrix
- Search a 2D Matrix II
- Find K Closest Elements
- Kth Smallest Element in a Sorted Matrix
- Aggressive Cows (Binary Search on Answer)
- Allocate Minimum Number of Pages
- Single Element in a Sorted Array
- Find the Smallest Divisor Given a Threshold
- Binary Search on a Function (Ternary Search Alternative)
- Count of Smaller Numbers After Self
- Time Based Key-Value Store
- Guess Number Higher or Lower
- H-Index II
- Find Right Interval
- Random Pick with Weight
- Interview Concept: Lower Bound vs Upper Bound Binary Search
- Interview Concept: Binary Search on Answer Pattern Explained
-
Sorting
- Bubble Sort Implementation
- Selection Sort Implementation
- Insertion Sort Implementation
- Merge Sort Implementation
- Quick Sort Implementation
- Heap Sort Implementation
- Counting Sort Implementation
- Radix Sort Implementation
- Bucket Sort Implementation
- Sort an Array (Built-in vs Custom Comparator)
- Merge Intervals Using Sorting
- Largest Number Formed from an Array
- Custom Sort String
- Sort Characters By Frequency
- Kth Largest Element (Sorting Approach)
- Relative Sort Array
- Wiggle Sort
- Wiggle Sort II
- H-Index (Sorting Approach)
- Meeting Rooms (Can Attend All Meetings)
Problem
Find the maximum sum of a contiguous subarray whose elements are all unique.
Input: nums = [4,2,4,5,6]
Output: 17 ([2,4,5,6])Python Solution
def maximum_unique_subarray(nums):
seen = set()
left = 0
window_sum = 0
best = 0
for right, num in enumerate(nums):
while num in seen:
seen.remove(nums[left])
window_sum -= nums[left]
left += 1
seen.add(num)
window_sum += num
best = max(best, window_sum)
return bestC++ Solution
int maximumUniqueSubarray(vector<int>& nums) {
unordered_set<int> seen;
int left = 0, windowSum = 0, best = 0;
for (int right = 0; right < nums.size(); right++) {
while (seen.count(nums[right])) {
seen.erase(nums[left]);
windowSum -= nums[left];
left++;
}
seen.insert(nums[right]);
windowSum += nums[right];
best = max(best, windowSum);
}
return best;
}Java Solution
class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> seen = new HashSet<>();
int left = 0, windowSum = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
while (seen.contains(nums[right])) {
seen.remove(nums[left]);
windowSum -= nums[left];
left++;
}
seen.add(nums[right]);
windowSum += nums[right];
best = Math.max(best, windowSum);
}
return best;
}
}Complexity
Time: O(n) the left pointer only moves forward, so total shrink operations are bounded by n. Space: O(n) for the set in the worst case, when all elements are unique.