Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 4

Description

Find X-Sum of All K-Long Subarrays I

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:

Example 2:

Constraints:

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

Solution

class TwoSet {
  using pi = pair<int, int>;
private:
  int limit;
  long long result = 0;
  set<pi, greater<pi>> sum;
  set<pi, greater<pi>> candidates;
  map<int, int> freq;
  void balanceSets() {
    while(sum.size() == limit && *sum.rbegin() < *candidates.begin()) {
      auto toRemove = *sum.rbegin();
      auto toAdd = *candidates.begin();
      sum.erase(toRemove);
      candidates.insert(toRemove);
      sum.insert(toAdd);
      candidates.erase(toAdd);
      result = result - 1LL * toRemove.first * toRemove.second + 1LL * toAdd.first * toAdd.second;
    }
    while(sum.size() < limit && candidates.size()) {
      auto toAdd = *candidates.begin();
      sum.insert(toAdd);
      candidates.erase(toAdd);
      result += 1LL * toAdd.first * toAdd.second;
    }
  }
public:
  long long getSum() { return result; }
  void add(int num) {
    pair<int, int> target = {freq[num], num};
    freq[num] += 1;
    if(sum.count(target)) {
      sum.erase(target);
      target.first += 1;
      result += num;
      sum.insert(target);
    } else if(candidates.count(target)) {
      candidates.erase(target);
      target.first += 1;
      candidates.insert(target);
    } else {
      target.first += 1;
      candidates.insert(target);
    }
    balanceSets();
  }
  void remove(int num) {
    pair<int, int> target = {freq[num], num};
    freq[num] -= 1;
    if(!freq[num]) freq.erase(num);
    if(sum.count(target)) {
      sum.erase(target);
      target.first -= 1;
      result -= num;
      if(target.first) sum.insert(target);
    } else if(candidates.count(target)) {
      candidates.erase(target);
      target.first -= 1;
      if(target.first) candidates.insert(target);
    }
    balanceSets();
  }
  void printState() {
    cout << "sum: ";
    for(auto [f, n] : sum) {
      cout << "[" << n << ", " << f << "], ";
    }
    cout << endl;
    cout << "candidates: ";
    for(auto [f, n] : candidates) {
      cout << "[" << n << ", " << f << "], ";
    }
    cout << endl;
  }

  TwoSet (int x): limit(x) {}
};
class Solution {
  vector<int> quickPass(vector<int>& nums, int x) {
    int len = nums.size();
    vector<int> answer(len - x + 1);
    for(int i = 0; i < x; ++i) {
      answer[0] += nums[i];
    }
    for(int i = 1; i < len - x + 1; ++i) {
      answer[i] = answer[i - 1] - nums[i - 1] + nums[i + x - 1];
    }
    return answer;
  }
public:
  vector<int> findXSum(vector<int>& nums, int k, int x) {
    if(k == x) return quickPass(nums, k);
    TwoSet ts(x);
    for(int i = 0; i < k; ++i) {
      ts.add(nums[i]);
    }
    // ts.printState();
    int len = nums.size();
    vector<int> answer(len - k + 1);
    answer[0] = ts.getSum();
    for(int i = 1; i < len - k + 1; ++i) {
      ts.add(nums[i + k - 1]);
      ts.remove(nums[i - 1]);
      answer[i] = ts.getSum();
    // ts.printState();
    }
    return answer;
  }
};

// Accepted
// 906/906 cases passed (9 ms)
// Your runtime beats 82.32 % of cpp submissions
// Your memory usage beats 56.59 % of cpp submissions (34.2 MB)