algoadvance

Leetcode 2913. Subarrays Distinct Element Sum of Squares I

Problem Statement

You are given an array of integers nums and an integer k. A subarray is a contiguous non-empty sequence of elements within an array. The distinct element sum of squares of a subarray is the sum of squares of its distinct elements. Return the sum of the distinct element sum of squares for all subarrays of length k or more in the input array nums.

Example:

For nums = [1, 2, 1, 2, 3] and k = 2, we consider all subarrays of length 2 or more:

  1. [1, 2] -> (1^2 + 2^2) = 1 + 4 = 5
  2. [1, 2, 1] -> (1^2 + 2^2) = 1 + 4 = 5 (1 is counted once)
  3. [2, 1, 2] -> (2^2 + 1^2) = 4 + 1 = 5 (1 is counted once)
  4. [1, 2, 3] -> (1^2 + 2^2 + 3^2) = 1 + 4 + 9 = 14
  5. [1, 2, 1, 2] -> (1^2 + 2^2) = 1 + 4 = 5 (1 is counted once)

The total sum would be 5 + 5 + 5 + 14 + 5 = 34.

Clarifying Questions

  1. Input Constraints:
    • What are the constraints on the length of nums (n)?
    • Are the elements of nums guaranteed to be positive integers?
  2. Output:
    • Should the result be a single integer representing the sum of the distinct element sum of squares of all subarrays of length k or more?
  3. Edge Cases:
    • What should we return if k is larger than the length of nums?
    • What if nums contains duplicate elements within subarrays? Are we ensuring that only unique elements’ squares are considered?

Strategy

To solve this problem, we need to consider the following steps:

  1. Sliding Window Technique:
    • Use a sliding window to navigate through all subarrays of lengths starting from k to n.
    • Maintain a frequency map to keep track of occurrences of elements within the current window.
    • Use this map to compute the sum of squares of distinct elements efficiently.
  2. Handling Duplicates:
    • As we move the sliding window, keep an active count of the elements. Adjust the count as elements enter and exit the window. Count the squares only once per unique element.
  3. Summation of Results:
    • Sum the results of the distinct element sum of squares of all valid subarrays.

Code

#include <vector>
#include <unordered_map>
#include <cmath>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int subarraysDistinctElementSumOfSquares(vector<int>& nums, int k) {
        if (nums.empty() || k > nums.size()) {
            return 0;
        }

        int n = nums.size();
        int totalSum = 0;

        // Function to calculate the sum of squares of unique elements in the window
        auto calculateSumOfSquares = [](unordered_map<int, int>& freqMap) {
            int sum = 0;
            for (auto& [key, value] : freqMap) {
                if (value > 0)
                    sum += key * key;
            }
            return sum;
        };

        // Sliding window to calculate required sum of squares
        for (int size = k; size <= n; ++size) {
            unordered_map<int, int> freqMap;
            int currentSum = 0;

            for (int i = 0; i < size; ++i) {
                freqMap[nums[i]]++;
            }
            currentSum = calculateSumOfSquares(freqMap);
            totalSum += currentSum;

            for (int i = size; i < n; ++i) {
                freqMap[nums[i - size]]--;
                freqMap[nums[i]]++;

                currentSum = calculateSumOfSquares(freqMap);
                totalSum += currentSum;
            }
        }

        return totalSum;
    }
};

Time Complexity

Thus, the overall time complexity would be approximately O(n^2) for larger dimensions of n and small window sizes starting from k.

This solution ensures that we efficiently compute the required sum of squares of distinct elements in each valid subarray and sum them up for the result.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI