Welcome to Subscribe On Youtube

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

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions