Watch 7 video solutions for Minimum Subarray Length With Distinct Sum At Least K, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Komal Vhanmane has 314 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |