3795. Minimum Subarray Length With Distinct Sum At Least K

MediumArrayHash TableSliding Window

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums and an integer k.

A subarray is a contiguous, non-empty portion of the array. For any subarray, we look at the distinct values it contains (each value is counted only once, regardless of how many times it appears) and add them together to get a sum.

Your task is to find a subarray whose sum of distinct values is at least k, and among all such subarrays, return the one with the minimum length.

If no subarray satisfies this condition, return -1.

Key points to understand:

The subarray must be contiguous (a continuous block of elements from the array).
When computing the sum, duplicate values are only counted once. For example, if a subarray is [2, 2, 3], its distinct sum is 2 + 3 = 5, not 7.
We want the shortest subarray (smallest number of elements) whose distinct sum reaches or exceeds k.
If it is impossible to reach a distinct sum of k with any subarray, the answer is -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Sliding Window?

This problem maps to Sliding Window through a short path in the full flowchart.

Finding the minimum-length subarray whose distinct-sum reaches k requires a sliding window that tracks distinct element frequencies and their sum.

Open in Flowchart

Intuition

We want the shortest subarray whose sum of distinct values is at least k. A natural first idea is to check every possible subarray, but that would be too slow. So we look for a property we can exploit.

The crucial observation is that all values in nums are non-negative (or at least, adding more distinct elements never decreases the distinct sum). This means:

As we extend a window to the right by adding more elements, the distinct sum s can only stay the same or grow.
As we shrink a window from the left by removing elements, the distinct sum s can only stay the same or drop.

This monotonic behavior is exactly what makes a sliding window work. Here is the reasoning:

We grow the window by moving the right pointer r, adding each new element. If the element is appearing for the first time in the window, it contributes to the distinct sum, so we add its value to s.
Once s reaches k, the current window is a valid candidate. We record its length, then try to shrink from the left to see if a shorter window can still satisfy the condition.
When we remove an element from the left, we decrease its count. If its count drops to 0, that value is no longer present in the window, so we subtract it from s.
We keep shrinking while s >= k, updating the best (minimum) length each time.

The key tools we need are:

A counter cnt that tracks how many times each value currently appears in the window. This lets us know whether a value is newly added (count becomes 1) or fully removed (count becomes 0), so we maintain s correctly as the sum of distinct values.
A running sum s of the distinct values in the window, so we never recompute it from scratch.

By sliding both pointers forward only once each, every element enters and leaves the window at most once, giving us an efficient single-pass solution. We start ans at n + 1 as a sentinel; if it never improves, no valid subarray exists and we return -1.

Pattern Learn more about Sliding Window patterns.

Solution Approach

Solution 1: Sliding Window

We use a hash table cnt to record the occurrence count of each element in the current window, and a variable s to record the sum of distinct elements in the current window. We use two pointers l and r to represent the left and right boundaries of the current window, both initially pointing to the beginning of the array. We initialize a variable ans to record the minimum length of a window that satisfies the condition, with an initial value of n + 1, where n is the length of the array.

Step-by-step breakdown:

Initialization. We set up cnt = defaultdict(int) to count occurrences, s = 0 for the current distinct sum, l = 0 for the left pointer, and ans = n + 1 as a sentinel value that means "no valid window found yet".
Expand the window. We iterate the right pointer r over the array using enumerate(nums), where x is the current element. We increase its count with cnt[x] += 1. If this makes cnt[x] == 1, the element is newly added to the window and was not present before, so we add its value to the distinct sum: s += x. If the count was already greater than 1, the value was already counted, so s stays unchanged.
Shrink the window. Whenever s >= k, the current window [l, r] is valid. We update the answer with ans = min(ans, r - l + 1). Then we try to shrink from the left to find a possibly shorter valid window:
- Decrease the count of the leftmost element: cnt[nums[l]] -= 1.
- If this count drops to 0, the value no longer appears in the window, so we remove its contribution: s -= nums[l].
- Move the left pointer forward: l += 1.
We keep repeating this while s >= k loop until the distinct sum falls below k, recording the minimum length at each step.
Return the result. After processing all elements, if ans > n it means the sentinel was never updated and no valid window exists, so we return -1. Otherwise, we return ans.

Why it works correctly: Because values are non-negative, the distinct sum is monotonic with respect to the window size — extending the window never decreases s, and shrinking never increases it. This guarantees the sliding window explores all minimal-length candidates without missing any. The cnt table is essential to distinguish between adding a new distinct value versus a duplicate, ensuring s always reflects the sum of distinct values only.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. Each element is added to the window once (by r) and removed at most once (by l), so each pointer traverses the array a single time.
Space complexity: O(n), for the hash table cnt that may store up to n distinct values in the worst case.

Example Walkthrough

Let's trace through the sliding window solution with a concrete example.

Input: nums = [2, 1, 2, 3], k = 5

Goal: Find the shortest subarray whose sum of distinct values is at least 5.

Initial setup: cnt = {}, s = 0, l = 0, ans = 5 (since n = 4, sentinel is n + 1 = 5).

We move the right pointer r across the array one element at a time.

r = 0, x = 2

cnt[2] = 1 → newly added, so s += 2 → s = 2.
s (2) < k (5), window not valid yet. No shrink.
Window [2], distinct sum = 2.

r = 1, x = 1

cnt[1] = 1 → newly added, so s += 1 → s = 3.
s (3) < k (5), not valid. No shrink.
Window [2, 1], distinct sum = 3.

r = 2, x = 2

cnt[2] = 2 → duplicate, count was already 1, so s stays 3.
s (3) < k (5), not valid. No shrink.
Window [2, 1, 2], distinct sum = 2 + 1 = 3 (the second 2 adds nothing).

r = 3, x = 3

cnt[3] = 1 → newly added, so s += 3 → s = 6.
s (6) >= k (5) → window [l=0, r=3] is valid!
- Update ans = min(5, 3 - 0 + 1) = 4.
- Shrink from left: remove nums[0] = 2. cnt[2] drops from 2 to 1. Count is still > 0, so 2 is still present — s stays 6. Move l = 1.
- Still s (6) >= k (5) → window [l=1, r=3] is valid.
  - Update ans = min(4, 3 - 1 + 1) = 3.
  - Shrink again: remove nums[1] = 1. cnt[1] drops from 1 to 0. Count hit 0, so 1 is removed — s -= 1 → s = 5. Move l = 2.
- Still s (5) >= k (5) → window [l=2, r=3] is valid.
  - Update ans = min(3, 3 - 2 + 1) = 2.
  - Shrink again: remove nums[2] = 2. cnt[2] drops from 1 to 0. Count hit 0, so 2 is removed — s -= 2 → s = 3. Move l = 3.
- Now s (3) < k (5) → stop shrinking.

End of array. ans = 2, which is <= n, so we return 2.

Verification: The window [2, 3] (indices 2 and 3) has distinct sum 2 + 3 = 5 >= 5 and length 2. No shorter valid subarray exists, confirming the answer.

Key takeaways from the trace:

At r = 2, the duplicate 2 was correctly ignored thanks to cnt[2] already being 1.
During shrinking, removing the first 2 did not drop s because another 2 remained (cnt[2] was still > 0), showing why the count table is essential.
The window only shrank to exactly the point where s fell below k, capturing the minimal length 2.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4
5class Solution:
6    def minLength(self, nums: List[int], k: int) -> int:
7        # Frequency of each value within the current window
8        count = defaultdict(int)
9        n = len(nums)
10        # Initialize answer to an impossible large length (sentinel)
11        ans = n + 1
12        # distinct_sum: sum of distinct values in the window
13        # left: left boundary of the sliding window
14        distinct_sum = left = 0
15
16        # Expand the window by moving the right boundary
17        for right, x in enumerate(nums):
18            count[x] += 1
19            # If x just entered the window (first occurrence), add it to the distinct sum
20            if count[x] == 1:
21                distinct_sum += x
22
23            # Shrink the window from the left while the condition still holds
24            while distinct_sum >= k:
25                # Update the minimum window length
26                ans = min(ans, right - left + 1)
27                # Remove the leftmost element from the window
28                count[nums[left]] -= 1
29                # If that value no longer appears in the window, subtract it from the distinct sum
30                if count[nums[left]] == 0:
31                    distinct_sum -= nums[left]
32                left += 1
33
34        # If ans was never updated, no valid subarray exists
35        return -1 if ans > n else ans
36

1class Solution {
2    public int minLength(int[] nums, int k) {
3        // Total number of elements in the input array
4        int length = nums.length;
5
6        // Initialize the answer to an impossible value (larger than any valid window length)
7        int minWindowLength = length + 1;
8
9        // Map to record the frequency of each distinct value within the current window
10        Map<Integer, Integer> countMap = new HashMap<>();
11
12        // Left boundary of the sliding window
13        int left = 0;
14
15        // Sum of the distinct values currently present in the window
16        long distinctSum = 0;
17
18        // Expand the window by moving the right boundary one step at a time
19        for (int right = 0; right < length; ++right) {
20            // Increase the count of nums[right]; if it just became 1,
21            // it is a newly added distinct value, so add it to distinctSum
22            if (countMap.merge(nums[right], 1, Integer::sum) == 1) {
23                distinctSum += nums[right];
24            }
25
26            // Shrink the window from the left while the distinct sum meets the threshold
27            while (distinctSum >= k) {
28                // Update the answer with the current window length
29                minWindowLength = Math.min(minWindowLength, right - left + 1);
30
31                // Decrease the count of nums[left]; if it dropped to 0,
32                // the value no longer exists in the window, so subtract it from distinctSum
33                if (countMap.merge(nums[left], -1, Integer::sum) == 0) {
34                    distinctSum -= nums[left];
35                }
36
37                // Move the left boundary forward to continue shrinking
38                ++left;
39            }
40        }
41
42        // If no valid window was found, return -1; otherwise return the minimum length
43        return minWindowLength > length ? -1 : minWindowLength;
44    }
45}
46

1class Solution {
2public:
3    int minLength(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // ans stores the minimum valid window length; initialize beyond the max possible
7        int ans = n + 1;
8
9        // distinctCount maps each value to its frequency inside the current window
10        unordered_map<int, int> distinctCount;
11
12        // left boundary of the sliding window
13        int left = 0;
14
15        // sum of DISTINCT values currently present in the window
16        long long distinctSum = 0;
17
18        // Expand the window by moving the right boundary
19        for (int right = 0; right < n; ++right) {
20            int current = nums[right];
21
22            // If this value enters the window for the first time, add it to the distinct sum
23            if (++distinctCount[current] == 1) {
24                distinctSum += current;
25            }
26
27            // Shrink the window from the left while it remains valid
28            while (distinctSum >= k) {
29                // Update the best (shortest) window length found so far
30                ans = min(ans, right - left + 1);
31
32                int leftValue = nums[left];
33
34                // If removing this element drops its count to zero,
35                // the value no longer exists in the window, so subtract it
36                if (--distinctCount[leftValue] == 0) {
37                    distinctSum -= leftValue;
38                }
39
40                // Move the left boundary forward
41                ++left;
42            }
43        }
44
45        // If ans was never updated, no valid window exists -> return -1
46        return ans > n ? -1 : ans;
47    }
48};
49

1/**
2 * Finds the minimum length of a subarray whose sum of distinct values is >= k.
3 * Uses a sliding window where `distinctSum` tracks the sum of unique values
4 * currently present in the window (each unique value contributes once).
5 *
6 * @param nums - The input array of numbers.
7 * @param k - The target threshold for the sum of distinct values.
8 * @returns The minimum valid subarray length, or -1 if none exists.
9 */
10function minLength(nums: number[], k: number): number {
11    const n: number = nums.length;
12
13    // Initialize answer to an impossible-large value (n + 1) to detect "no solution".
14    let minLen: number = n + 1;
15
16    // Map each value to how many times it appears in the current window.
17    const countMap: Map<number, number> = new Map<number, number>();
18
19    // Left boundary of the sliding window.
20    let left: number = 0;
21
22    // Sum of distinct values currently inside the window.
23    let distinctSum: number = 0;
24
25    // Expand the window by moving the right boundary one step at a time.
26    for (let right = 0; right < n; ++right) {
27        const rightValue: number = nums[right];
28
29        // Increment the occurrence count of the incoming value.
30        const newCount: number = (countMap.get(rightValue) ?? 0) + 1;
31        countMap.set(rightValue, newCount);
32
33        // If this value just became present (first occurrence), add it to the distinct sum.
34        if (newCount === 1) {
35            distinctSum += rightValue;
36        }
37
38        // Shrink the window from the left while the distinct sum meets the threshold.
39        while (distinctSum >= k) {
40            // Record the current window length as a candidate answer.
41            minLen = Math.min(minLen, right - left + 1);
42
43            const leftValue: number = nums[left];
44
45            // Decrement the occurrence count of the outgoing value.
46            const remainingCount: number = (countMap.get(leftValue) ?? 0) - 1;
47            countMap.set(leftValue, remainingCount);
48
49            // If this value is no longer present, remove it from the distinct sum.
50            if (remainingCount === 0) {
51                distinctSum -= leftValue;
52            }
53
54            // Advance the left boundary.
55            ++left;
56        }
57    }
58
59    // If minLen was never updated below n + 1, no valid subarray exists.
60    return minLen > n ? -1 : minLen;
61}
62

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers, l and r, where n is the length of the array nums.

The outer loop iterates over each element with the right pointer r, running exactly n times.
The inner while loop advances the left pointer l. Although it is nested, l only moves forward and never resets, so across the entire execution it advances at most n times in total.
Each operation inside the loops (dictionary updates, sum adjustments, and min comparisons) takes O(1) time on average.

Therefore, both pointers traverse the array at most once, giving an amortized total of O(n) operations.

Space Complexity: O(n)

The defaultdict named cnt stores the count of distinct elements within the current window. In the worst case, when all elements are unique, it can hold up to n key-value pairs. Hence, the extra space required is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to use a counter and incorrectly tracking the distinct sum

The most common mistake is using a simple set to track which values are in the window, instead of a frequency counter. While a set correctly tells you whether a value is present, it cannot tell you how many copies exist. When shrinking the window from the left, you need to know whether removing the leftmost element actually eliminates the last occurrence of that value.

Buggy approach:

# WRONG: using a set loses occurrence counts
seen = set()
distinct_sum = left = 0
for right, x in enumerate(nums):
    if x not in seen:
        seen.add(x)
        distinct_sum += x
    while distinct_sum >= k:
        ans = min(ans, right - left + 1)
        # BUG: blindly removing nums[left] from the set is wrong
        # if nums[left] appears again later in the window!
        seen.discard(nums[left])
        distinct_sum -= nums[left]
        left += 1

For an input like nums = [2, 2, 3], when the left pointer removes the first 2, the set incorrectly discards 2 entirely and subtracts it from distinct_sum, even though a second 2 is still inside the window. This corrupts both seen and distinct_sum.

Solution: Use a frequency counter and only subtract a value when its count drops to 0, as the reference code does:

count[nums[left]] -= 1
if count[nums[left]] == 0:          # last copy removed
    distinct_sum -= nums[left]
left += 1

Symmetrically, only add to distinct_sum when a value's count rises to exactly 1 (its first occurrence).

Pitfall 2: Assuming the sliding window works with negative numbers

The sliding window relies on monotonicity: extending the window never decreases the distinct sum, and shrinking never increases it. This only holds when all values are non-negative.

If nums could contain negative values, adding a new distinct negative number would decrease distinct_sum, breaking the invariant. In that case, shrinking the window when distinct_sum >= k may skip valid shorter windows, producing wrong answers.

Solution: Confirm the constraint that values are non-negative before applying this technique. If negatives are allowed, the sliding window is invalid and you must fall back to a different approach (e.g., examining subarrays with prefix-based or more exhaustive methods).

Pitfall 3: Mishandling the "no valid subarray" sentinel

A subtle off-by-one trap is the final return check. The sentinel is initialized to n + 1, and a valid window length can be at most n. Using a wrong comparison such as ans >= n instead of ans > n would incorrectly return -1 for a valid full-array answer of length n.

Solution: Initialize the sentinel strictly larger than any possible valid length (n + 1) and compare with strict inequality:

return -1 if ans > n else ans

This guarantees a full-length valid subarray (length n) is still correctly reported.

Pitfall 4: Updating the answer only after the shrink loop finishes

Some implementations update ans only once, after the while loop, using the final shrunken window. This can either record a window where distinct_sum < k (invalid) or miss the smallest valid length.

Solution: Update ans = min(ans, right - left + 1) inside the while distinct_sum >= k loop, before shrinking. This ensures every valid window length is considered while the condition still holds.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering