Tejav
#3795

Minimum Subarray Length With Distinct Sum At Least K

Medium
ArrayHash TableSliding WindowHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Use a sliding window to dynamically adjust the subarray size while maintaining the sum of distinct elements. This is efficient and avoids unnecessary recalculations.

⚙️

Algorithm

3 steps
  1. 1Step 1: Initialize two pointers (left and right) and a hash map to track distinct sums.
  2. 2Step 2: Expand the right pointer to include new elements and update the distinct sum.
  3. 3Step 3: When the distinct sum is at least k, move the left pointer to minimize the window while maintaining the sum.
solution.py15 lines
1def minSubarrayLen(nums, k):
2    left, min_len, distinct_sum = 0, float('inf'), 0
3    freq = {}
4    for right in range(len(nums)):
5        if nums[right] not in freq:
6            distinct_sum += nums[right]
7        freq[nums[right]] = freq.get(nums[right], 0) + 1
8        while distinct_sum >= k:
9            min_len = min(min_len, right - left + 1)
10            freq[nums[left]] -= 1
11            if freq[nums[left]] == 0:
12                distinct_sum -= nums[left]
13                del freq[nums[left]]
14            left += 1
15    return min_len if min_len != float('inf') else -1
ℹ

Complexity note: The sliding window approach allows us to traverse the array in linear time, maintaining a hash map for distinct elements.

  • 1Sliding window efficiently manages subarray size.
  • 2Hash map tracks distinct elements and their counts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.