Maximum sum of subarray with no duplicates
Filed under Paytm
Free read 1 of 3Confirm if elements are strictly positive and whether subarrays must be contiguous.
The question
Given an array of positive integers, find the maximum sum of a contiguous subarray that contains no duplicate elements.
Constraints
- 1 <= array length <= 10^5
- 1 <= array elements <= 10^4
Examples
- Input
- arr = [1, 2, 3, 1, 4]
- Output
- 10
- Why
- The subarray [2, 3, 1, 4] has no duplicates and sums to 10.
Approach
Confirm if elements are strictly positive and whether subarrays must be contiguous.
Generate all possible subarrays, check each for duplicate elements using a hash set, and compute the sum for valid ones. O(N^3) or O(N^2).
Use a sliding window with a hash map storing the last seen index of each element. Maintain a running sum and update the left boundary when a duplicate is found within the current window.
Array with length 1, or an array with completely unique elements.
Solution
O(N) time, O(N) space
class Solution:
def maximumUniqueSubarraySum(self, nums: list[int]) -> int:
seen = {}
left = 0
max_sum = 0
curr_sum = 0
for right, num in enumerate(nums):
if num in seen and seen[num] >= left:
while left <= seen[num]:
curr_sum -= nums[left]
left += 1
seen[num] = right
curr_sum += num
max_sum = max(max_sum, curr_sum)
return max_sum
Tips
- What they are testing: Test with all unique elements, all identical elements, and subarrays where duplicates appear multiple times.
- Common mistake: Restarting the sliding window completely from the duplicate index rather than adjusting the left pointer past the previous occurrence.
Related Paytm questions
Collected from public candidate posts and coding forums. Updated Nov 2026.