Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2461.html

2461. Maximum Sum of Distinct Subarrays With Length K

  • Difficulty: Medium.
  • Related Topics: Array, Hash Table, Sliding Window.
  • Similar Questions: Max Consecutive Ones III, Longest Nice Subarray, Optimal Partition of String.

Problem

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

  • The length of the subarray is k, and

  • All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A **subarray is a contiguous non-empty sequence of elements within an array.**

  Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

  Constraints:

  • 1 <= k <= nums.length <= 105

  • 1 <= nums[i] <= 105

Solution (Java, C++, Python)

  • class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> cnt = new HashMap<>(k);
        long s = 0;
        for (int i = 0; i < k; ++i) {
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
            s += nums[i];
        }
        long ans = 0;
        for (int i = k; i < n; ++i) {
            if (cnt.size() == k) {
                ans = Math.max(ans, s);
            }
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
            cnt.put(nums[i - k], cnt.getOrDefault(nums[i - k], 0) - 1);
            if (cnt.get(nums[i - k]) == 0) {
                cnt.remove(nums[i - k]);
            }
            s += nums[i];
            s -= nums[i - k];
        }
        if (cnt.size() == k) {
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

  • class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> cnt;
        long long s = 0, ans = 0;
        for (int i = 0; i < k; ++i) {
            cnt[nums[i]]++;
            s += nums[i];
        }
        for (int i = k; i < n; ++i) {
            if (cnt.size() == k) ans = max(ans, s);
            cnt[nums[i]]++;
            cnt[nums[i - k]]--;
            if (cnt[nums[i - k]] == 0) cnt.erase(nums[i - k]);
            s += nums[i];
            s -= nums[i - k];
        }
        if (cnt.size() == k) ans = max(ans, s);
        return ans;
    }
};

  • class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        cnt = Counter(nums[:k])
        s = sum(nums[:k])
        ans = 0
        for i in range(k, n):
            if len(cnt) == k:
                ans = max(ans, s)
            cnt[nums[i]] += 1
            cnt[nums[i - k]] -= 1
            s += nums[i]
            s -= nums[i - k]
            if cnt[nums[i - k]] == 0:
                cnt.pop(nums[i - k])
        if len(cnt) == k:
            ans = max(ans, s)
        return ans


  • func maximumSubarraySum(nums []int, k int) int64 {
	n := len(nums)
	cnt := map[int]int{}
	s, ans := 0, 0
	for i := 0; i < k; i++ {
		cnt[nums[i]]++
		s += nums[i]
	}
	for i := k; i < n; i++ {
		if len(cnt) == k {
			ans = max(ans, s)
		}
		cnt[nums[i]]++
		cnt[nums[i-k]]--
		if cnt[nums[i-k]] == 0 {
			delete(cnt, nums[i-k])
		}
		s += nums[i]
		s -= nums[i-k]
	}
	if len(cnt) == k {
		ans = max(ans, s)
	}
	return int64(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

  • function maximumSubarraySum(nums: number[], k: number): number {
    const n = nums.length;
    const cnt: Map<number, number> = new Map();
    let s = 0;
    for (let i = 0; i < k; ++i) {
        cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
        s += nums[i];
    }
    let ans = cnt.size === k ? s : 0;
    for (let i = k; i < n; ++i) {
        cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
        s += nums[i];
        cnt.set(nums[i - k], cnt.get(nums[i - k])! - 1);
        s -= nums[i - k];
        if (cnt.get(nums[i - k]) === 0) {
            cnt.delete(nums[i - k]);
        }
        if (cnt.size === k) {
            ans = Math.max(ans, s);
        }
    }
    return ans;
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions