Maximum Sum of Distinct Subarrays With Length K

MediumArrayHash TableSliding Window

Solution

export function maximumSubarraySum(nums: number[], k: number): number {
  const n = nums.length;
  const counter = new Counter(nums.slice(0, k));
 
  let start = 0;
  let subarraySum = nums.slice(0, k).reduce((acc, num) => acc + num, 0);
  let answer = counter.isDistinct ? subarraySum : 0;
  for (let end = k; end < n; end++) {
    counter.sub(nums[start]);
    counter.add(nums[end]);
    subarraySum += nums[end] - nums[start];
    if (counter.isDistinct) {
      answer = Math.max(answer, subarraySum);
    }
    start += 1;
  }
  return answer;
}
 
class Counter {
  private totalCount: number;
  private readonly map: Map<number, number>;
 
  constructor(nums: number[] = []) {
    this.map = new Map();
    this.totalCount = 0;
    nums.forEach((num) => {
      this.add(num);
    });
  }
 
  get(num: number): number {
    return this.map.get(num) ?? 0;
  }
 
  add(num: number) {
    this.totalCount += 1;
    this.map.set(num, this.get(num) + 1);
  }
 
  sub(num: number) {
    this.totalCount -= 1;
    if (this.get(num) <= 1) {
      this.map.delete(num);
    } else {
      this.map.set(num, this.get(num) - 1);
    }
  }
 
  get isDistinct() {
    return this.totalCount === this.map.size;
  }
}

Complexity

  • Time: O(n)O(n)
  • Space: O(k)O(k)