Maximum Number of Ways to Partition an Array LeetCode solution in C++

1
class Solution {
2
 public:
3
  int waysToPartition(vector<int> &nums, int k) {
4
    unordered_map<long long int, int> left;
5
    unordered_map<long long int, int> right;
6

7
    long long int sum = accumulate(nums.begin(), nums.end(), 0L);
8
    long long int leftSum = 0;
9
    int n = nums.size();
10

11
    for (int i = 0; i < n - 1; i++) {
12
      leftSum += nums[i];
13
      long long int rightSum = sum - leftSum;
14
      long long int difference = leftSum - rightSum;
15
      right[difference]++; // storing difference count in right, since no
16
                           // difference exist in left
17
    }
18

19
    int res = right[0]; // Point Zero difference are the partition points
20
    leftSum = 0;
21
    for (int i = 0; i < n; i++) {
22
      long long int D = k - nums[i];
23
      res = max(res,
24
                right[-D] + left[D]); // We can run a few test cases and see that if we
25
                                      // replace arr[i] by k, the difference D, the left side
26
                                      // including i,each element decreases by D while the
27
                                      // right Side each element increases by D, so we find -D
28
                                      // on right Side... WHY?? if right side is increasing by
29
                                      // D, we need to find -D since this will result in
30
                                      // -D+D=0, which are our partition points, since point 0
31
                                      // signifies a partition where leftSum==rightSum,
32
                                      // similarly, left side decreases by D, so we find +D on
33
                                      // left since this will result in zero as well.
34

35
      leftSum += nums[i];
36
      long long int rightSum = sum - leftSum;
37
      left[leftSum - rightSum]++;  // Now since we are moving our i forward, we
38
                                   // are gonna change the next i point, so we
39
                                   // are placing leftSum-RightSum on left side
40
      right[leftSum - rightSum]--; // From right we are gonna decrease it and
41
                                   // transfer to left side
42
      if (right[leftSum - rightSum] == 0) {
43
        right.erase(leftSum - rightSum);
44
      }
45
    }
46
    return res;
47
  }
48
};