Skip to main content
Talentd

Minimum Subarray Length With Distinct Sum At Least K - Solution & Explanation

MediumArrayHash TableSliding Window10 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 109

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Set TrackingO(n²)O(n)Good for understanding the requirement or very small arrays
Sliding Window + Hash MapO(n)O(n)Optimal solution for large inputs and typical interview expectations

Video Solution

Leetcode|Minimum Subarray Length With Distinct Sum At Least K | Java | Bi Weekly Contest173 • Cakot Coding • 340 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Subarray Length With Distinct Sum At Least K easy or hard?
This problem is generally considered Medium difficulty. The main challenge is correctly maintaining the distinct sum while handling duplicate values during window expansion and contraction. Once you recognize the sliding window pattern with frequency tracking, the implementation becomes straightforward.
Minimum Subarray Length With Distinct Sum At Least K Python/Java solution
Most implementations follow the same pattern across languages: maintain two pointers for the window, a hash map for frequencies, and a variable storing the sum of distinct elements. Python typically uses defaultdict or Counter, while Java uses HashMap. The algorithm runs in O(n) time in both languages.
How to solve Minimum Subarray Length With Distinct Sum At Least K in O(n)?
Use two pointers to maintain a sliding window and a hash map to track element frequencies. When a number appears for the first time in the window, add its value to the distinct sum. Once the distinct sum reaches or exceeds k, move the left pointer to shrink the window while updating frequencies and subtracting values when counts reach zero. Track the minimum window length during this process.
What is the best approach for Minimum Subarray Length With Distinct Sum At Least K?
The most efficient solution uses a sliding window combined with a hash map to track element frequencies. As the right pointer expands the window, the algorithm updates the sum of distinct values. When the distinct sum becomes at least k, the left pointer shrinks the window to find the minimum valid length. This approach runs in O(n) time with O(n) space.
Is Minimum Subarray Length With Distinct Sum At Least K asked at Google/Amazon/Meta?
Problems combining sliding window and hash map frequency tracking commonly appear in interviews at companies like Amazon, Google, and Meta. Variants involving minimum window size, distinct elements, or target sums are frequent in coding interviews because they test two-pointer optimization and data structure usage.
What data structure is used in Minimum Subarray Length With Distinct Sum At Least K?
The key data structure is a hash table (hash map) that stores the frequency of each element inside the current window. This allows the algorithm to quickly determine when an element becomes newly distinct or when it should be removed from the distinct sum during window contraction.
What is the time complexity of Minimum Subarray Length With Distinct Sum At Least K?
The optimal sliding window solution runs in O(n) time because each element is added to and removed from the window at most once. Hash map updates and lookups occur in constant time. Space complexity is O(n) in the worst case when all elements in the window are unique.

Ready to solve this problem?

Practice Minimum Subarray Length With Distinct Sum At Least K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays