Need Help With This DSA Problem Asked in My NetApp Interview

I was asked a coding question during Round 1 of my NetApp Full Stack Engineer interview, and I wasn't able to figure out the complete approach or write the solution. I understood what the question was asking, but I got stuck while trying to handle the duplicate elements and calculate the maximum sum efficiently.

I'd appreciate it if someone could help me understand the approach and explain the solution step by step.

Problem Statement

Given an integer array nums and an integer k, find the maximum sum of a contiguous subarray containing exactly k elements, such that all the elements in that subarray are distinct.

If no valid subarray exists, return 0.

A valid subarray must satisfy two conditions:

• It must contain exactly k consecutive elements.

• All elements within the subarray must be unique.

Example 1

Input:

nums = [4, 1, 3, 8, 5, 2, 6, 3]
k = 3

Output:

16

Explanation:

We need to examine every contiguous subarray of length 3 and find the one with distinct elements and the maximum sum.

• [4, 1, 3] → Sum = 8

• [1, 3, 8] → Sum = 12

• [3, 8, 5] → Sum = 16

• [8, 5, 2] → Sum = 15

• [5, 2, 6] → Sum = 13

• [2, 6, 3] → Sum = 11

The subarray [3, 8, 5] contains three distinct elements and has the highest sum, which is 16.

Example 2

Input:

nums = [6, 6, 2, 2, 8, 8]
k = 2

Output:

10

Explanation:

Some subarrays contain duplicate elements, such as [6, 6], [2, 2], and [8, 8], so they cannot be considered.

However, [6, 2] and [2, 8] contain distinct elements. Their sums are 8 and 10, respectively. Therefore, the maximum valid sum is 10.

Example 3

Input:

nums = [5, 5, 5, 5]
k = 3

Output:

0

Explanation:

Every contiguous subarray of length 3 contains duplicate elements. Since no valid subarray exists, the answer is 0.

What I'm Struggling With

I tried to think of a way to check each subarray, but I'm not sure how to optimize the solution.