Skip to content

3795. Minimum Subarray Length With Distinct Sum At Least K

Description

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

Solutions

Solution 1: Sliding Window

We use a hash table \(\textit{cnt}\) to record the occurrence count of each element in the current window, and a variable \(\textit{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 \(\textit{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 \(\textit{cnt}\) and \(\textit{s}\). When \(\textit{s}\) is greater than or equal to \(k\), we try to move the left pointer \(l\) to shrink the window, updating \(\textit{cnt}\) and \(\textit{s}\) accordingly, until \(\textit{s}\) is less than \(k\). During this process, we record the minimum length of windows that satisfy the condition.

Finally, if \(\textit{ans} \gt n\), it means no valid window exists, and we return \(-1\); otherwise we return \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minLength(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        n = len(nums)
        ans = n + 1
        s = l = 0
        for r, x in enumerate(nums):
            cnt[x] += 1
            if cnt[x] == 1:
                s += x
            while s >= k:
                ans = min(ans, r - l + 1)
                cnt[nums[l]] -= 1
                if cnt[nums[l]] == 0:
                    s -= nums[l]
                l += 1
        return -1 if ans > n else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minLength(int[] nums, int k) {
        int n = nums.length;
        int ans = n + 1;
        Map<Integer, Integer> cnt = new HashMap<>();
        int l = 0;
        long s = 0;
        for (int r = 0; r < n; ++r) {
            if (cnt.merge(nums[r], 1, Integer::sum) == 1) {
                s += nums[r];
            }
            while (s >= k) {
                ans = Math.min(ans, r - l + 1);
                if (cnt.merge(nums[l], -1, Integer::sum) == 0) {
                    s -= nums[l];
                }
                ++l;
            }
        }
        return ans > n ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minLength(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = n + 1;
        unordered_map<int, int> cnt;
        int l = 0;
        long long s = 0;
        for (int r = 0; r < n; ++r) {
            int x = nums[r];
            if (++cnt[x] == 1) {
                s += x;
            }
            while (s >= k) {
                ans = min(ans, r - l + 1);
                int y = nums[l];
                if (--cnt[y] == 0) {
                    s -= y;
                }
                ++l;
            }
        }
        return ans > n ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func minLength(nums []int, k int) int {
    n := len(nums)
    ans := n + 1
    cnt := map[int]int{}
    l := 0
    var s int64 = 0
    for r := 0; r < n; r++ {
        cnt[nums[r]]++
        if cnt[nums[r]] == 1 {
            s += int64(nums[r])
        }
        for s >= int64(k) {
            if r-l+1 < ans {
                ans = r - l + 1
            }
            if cnt[nums[l]]--; cnt[nums[l]] == 0 {
                s -= int64(nums[l])
            }
            l++
        }
    }
    if ans > n {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minLength(nums: number[], k: number): number {
    const n = nums.length;
    let ans = n + 1;
    const cnt = new Map<number, number>();
    let l = 0;
    let s = 0;
    for (let r = 0; r < n; ++r) {
        cnt.set(nums[r], (cnt.get(nums[r]) ?? 0) + 1);
        if (cnt.get(nums[r]) === 1) {
            s += nums[r];
        }
        while (s >= k) {
            ans = Math.min(ans, r - l + 1);
            cnt.set(nums[l], (cnt.get(nums[l]) ?? 0) - 1);
            if (cnt.get(nums[l]) === 0) {
                s -= nums[l];
            }
            ++l;
        }
    }
    return ans > n ? -1 : ans;
}

Comments