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

#php #leetcode #algorithms #programming

Difficulty: Easy

Topics: Array, Hash Table, Sliding Window, Heap (Priority Queue), Weekly Contest 419

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 subarray¹ 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

Hint:

Implement the x-sum function. Then, run x-sum on every subarray of nums of size k.

Solution:

We need to calculate the x-sum for every contiguous subarray of length k in the given array nums. The x-sum of an array is defined as the sum of all elements that belong to the top x most frequent elements. If there are ties in frequency, the element with the larger value is considered more frequent. If there are fewer than x distinct elements, the x-sum is simply the sum of all elements in the subarray.

Approach

Sliding Window Technique: We use a sliding window of size k to iterate through all possible subarrays of length k in nums.
Frequency Counting: For each window, we count the frequency of each element using a hash map.
Sorting by Frequency and Value: We sort the distinct elements in the window based on their frequencies (descending) and their values (descending) to determine the top x elements.
Calculate x-sum: We compute the sum of all elements in the window that are among the top x elements identified in the previous step.

Let's implement this solution in PHP: 3318. Find X-Sum of All K-Long Subarrays I

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $x
 * @return Integer[]
 */
function findXSum($nums, $k, $x) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
// Example 1
$nums = array(1, 1, 2, 2, 3, 4, 2, 3);
$k = 6;
$x = 2;
print_r(findXSum($nums, $k, $x));
// Output: [6, 10, 12]

// Example 2
$nums = array(3, 8, 7, 8, 7, 5);
$k = 2;
$x = 2;
print_r(findXSum($nums, $k, $x));
// Output: [11, 15, 15, 15, 12]
?>

Explanation:

Initialization: We initialize the result array to store the x-sum for each window.
Sliding Window: For each starting index i from 0 to n - k, we extract the subarray of length k starting at i.
Frequency Map: We count the occurrences of each element in the current window using a hash map.
Sorting: We sort the distinct elements in the window first by their frequency in descending order, and then by their value in descending order to handle ties.
Top x Elements: We select the top x elements from the sorted distinct elements.
Sum Calculation: We iterate through the window and sum all elements that are in the top x elements.
Store Result: The computed sum for the current window is stored in the result array.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!