You are given an integer array nums and an integer k.
Return the minimum length of a subarray whose sum of the distinct values present in that subarray (each value counted once) is at least k. If no such subarray exists, return -1.
Example 1:
Input: nums = [2,2,3,1], k = 4
Output: 2
Explanation:
The subarray [2, 3] has distinct elements {2, 3} whose sum is 2 + 3 = 5, which is at least k = 4. Thus, the answer is 2.
Example 2:
Input: nums = [3,2,3,4], k = 5
Output: 2
Explanation:
The subarray [3, 2] has distinct elements {3, 2} whose sum is 3 + 2 = 5, which is at least k = 5. Thus, the answer is 2.
Example 3:
Input: nums = [5,5,4], k = 5
Output: 1
Explanation:
The subarray [5] has distinct elements {5} whose sum is 5, which is at least k = 5. Thus, the answer is 1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= 109Problem Overview: You are given an integer array and a value k. The goal is to find the smallest subarray whose distinct element sum is at least k. Only unique values inside the current window contribute to the sum, so duplicates should not increase the distinct sum.
Approach 1: Brute Force with Set Tracking (O(n2) time, O(n) space)
The direct approach checks every possible subarray. Start an index i, expand the end index j, and maintain a set (or hash map) to track which elements are already counted. When a new value appears, add it to the set and increase the distinct sum. As soon as the distinct sum reaches k, record the subarray length. This approach clearly models the requirement but performs redundant work because each starting position rebuilds the state from scratch. It becomes slow for large arrays due to the nested iteration.
Approach 2: Sliding Window + Hash Map (O(n) time, O(n) space)
The optimal solution uses a sliding window with two pointers. Expand the right pointer and maintain a frequency map using a hash table. When a number appears for the first time in the window, add its value to the running distinctSum. If it appears again, only increase the frequency without changing the sum. Once distinctSum ≥ k, shrink the window from the left to minimize its length. While shrinking, decrease frequencies and subtract the value from the distinct sum when its count drops to zero.
This works because each element enters and leaves the window at most once. The window dynamically maintains the smallest segment that satisfies the constraint. Hash lookups keep frequency updates constant time, making the entire scan linear.
The algorithm structure is simple: iterate the right pointer across the array, update the frequency map, adjust the distinct sum when a value becomes newly unique, and then move the left pointer while the condition remains satisfied. Each contraction step updates the minimum length.
Recommended for interviews: The sliding window approach is what interviewers expect. Mentioning the brute force method first demonstrates understanding of the problem constraints, but implementing the array sliding window with a hash map shows strong optimization skills and achieves the optimal O(n) runtime.
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.
We continuously move the right pointer r, adding new elements into the window and updating cnt and s. When s is greater than or equal to k, we try to move the left pointer l to shrink the window, updating cnt and s accordingly, until s is less than k. During this process, we record the minimum length of windows that satisfy the condition.
Finally, if ans \gt n, it means no valid window exists, and we return -1; otherwise we return ans.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set Tracking | O(n²) | O(n) | Good for understanding the requirement or very small arrays |
| Sliding Window + Hash Map | O(n) | O(n) | Optimal solution for large inputs and typical interview expectations |
Leetcode|Minimum Subarray Length With Distinct Sum At Least K | Java | Bi Weekly Contest173 • Komal Vhanmane • 314 views views
Watch 6 more video solutions →Practice Minimum Subarray Length With Distinct Sum At Least K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor