Skip to content

2025. Maximum Number of Ways to Partition an Array 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int waysToPartition(vector<int>& nums, int k) {
    const int n = nums.size();
    const long sum = accumulate(nums.begin(), nums.end(), 0L);
    long prefix = 0;
    // count of sum(A[0..k)) - sum(A[k..n)) for k in [0..i)
    unordered_map<long, int> l;
    // count of sum(A[0..k)) - sum(A[k..n)) for k in [i..n)
    unordered_map<long, int> r;

    for (int pivot = 1; pivot < n; ++pivot) {
      prefix += nums[pivot - 1];
      const long suffix = sum - prefix;
      ++r[prefix - suffix];
    }

    int ans = r[0];
    prefix = 0;

    for (const int num : nums) {
      ans = max(ans, l[k - num] + r[num - k]);
      prefix += num;
      const long suffix = sum - prefix;
      const long diff = prefix - suffix;
      --r[diff];
      ++l[diff];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int waysToPartition(int[] nums, int k) {
    final int n = nums.length;
    final long sum = Arrays.stream(nums).asLongStream().sum();
    long prefix = 0;
    // count of sum(A[0..k)) - sum(A[k..n)) for k in [0..i)
    Map<Long, Integer> l = new HashMap<>();
    // count of sum(A[0..k)) - sum(A[k..n)) for k in [i..n)
    Map<Long, Integer> r = new HashMap<>();

    for (int pivot = 1; pivot < n; ++pivot) {
      prefix += nums[pivot - 1];
      final long suffix = sum - prefix;
      r.merge(prefix - suffix, 1, Integer::sum);
    }

    int ans = r.getOrDefault(0L, 0);
    prefix = 0;

    for (final int num : nums) {
      final long change = (long) k - num;
      ans = Math.max(ans, l.getOrDefault(change, 0) + r.getOrDefault(-change, 0));
      prefix += num;
      final long suffix = sum - prefix;
      final long diff = prefix - suffix;
      r.merge(diff, -1, Integer::sum);
      l.merge(diff, 1, Integer::sum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def waysToPartition(self, nums: list[int], k: int) -> int:
    n = len(nums)
    summ = sum(nums)
    prefix = 0
    # Count of sum(A[0..k)) - sum(A[k..n)) for k in [0..i)
    l = collections.Counter()
    # Count of sum(A[0..k)) - sum(A[k..n)) for k in [i..n)
    r = collections.Counter()

    for pivot in range(1, n):
      prefix += nums[pivot - 1]
      suffix = summ - prefix
      r[prefix - suffix] += 1

    ans = r[0]
    prefix = 0

    for num in nums:
      ans = max(ans, l[k - num] + r[num - k])
      prefix += num
      suffix = summ - prefix
      diff = prefix - suffix
      r[diff] -= 1
      l[diff] += 1

    return ans