3318. Find X-Sum of All K-Long Subarrays I

Description

You are given an array nums of n integers and two integers k and x.

The x-sum of an array is calculated by the following procedure:

• Count the occurrences of all elements in the array.
• Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.
• Calculate the sum of the resulting array.

Note that if an array has less than x distinct elements, its x-sum is the sum of the array.

Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the nums[i..i + k - 1].

 

Example 1:

Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

Output: [6,10,12]

Explanation:

• For subarray [1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2.
• For subarray [1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times.
• For subarray [2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3.

Example 2:

Input: nums = [3,8,7,8,7,5], k = 2, x = 2

Output: [11,15,15,15,12]

Explanation:

Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1].

 

Constraints:

• 1 <= n == nums.length <= 50
• 1 <= nums[i] <= 50
• 1 <= x <= k <= nums.length

 

Solutions

Solution: Hash Map

• Time complexity: O(n*klogk)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
const findXSum = function (nums, k, x) {
  const n = nums.length;
  const countMap = new Map();
  const result = [];

  const getXSum = () => {
    const counts = [...countMap.entries()];

    if (counts.length <= x) {
      return counts.reduce((sum, [num, count]) => sum + num * count, 0);
    }

    let sum = 0;

    counts.sort((a, b) => b[1] - a[1] || b[0] - a[0]);

    for (let index = 0; index < x; index++) {
      const [num, count] = counts[index];

      sum += num * count;
    }

    return sum;
  };

  for (let index = 0; index < k; index++) {
    const num = nums[index];
    const count = countMap.get(num) ?? 0;

    countMap.set(num, count + 1);
  }

  result.push(getXSum());

  for (let index = k; index < n; index++) {
    const removeNum = nums[index - k];
    const removeNumCount = countMap.get(removeNum);

    if (removeNumCount === 1) {
      countMap.delete(removeNum);
    } else {
      countMap.set(removeNum, removeNumCount - 1);
    }

    const num = nums[index];
    const count = countMap.get(num) ?? 0;

    countMap.set(num, count + 1);

    result.push(getXSum());
  }

  return result;
};