Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

Description 

Solution: Sliding Window w/ Two Pointers & Set

Maintain a sliding window of unique numbers with maximum size of k.
We can store the numbers in the window in a hashset.
When we move the right pointer up, move the left pointer up until:

  • all numbers in the window are unique
  • the window size <= k

Time Complexity: O(n) 246ms
Space Complexity: O(k) 71.5MB

var maximumSubarraySum = function(nums, k) {
  let set = new Set(), sum = 0;
  let ans = 0, n = nums.length;
  for (let j = 0, i = 0; j < n; j++) {
    sum += nums[j];
    while (set.has(nums[j]) || j - i >= k) {
      sum -= nums[i];
      set.delete(nums[i]);
      i++;
    }
    set.add(nums[j]);
    if (j - i + 1 === k) ans = Math.max(ans, sum);
  }
  return ans;
};

Comments

Popular posts from this blog

Minimum Number of Operations to Sort a Binary Tree by Level - BFS & Cycle Counting Explained [JS]

Beautiful Towers II - Monotonic Increasing Stack [JS]

Reschedule Meetings for Maximum Free Time I - Sliding Window - Constant Space [JS]

Count Subarrays With Median K - Count Left & Right Balance [JS]