Maximum Number of Ways to Partition an Array

// Accepted solution for LeetCode #2025: Maximum Number of Ways to Partition an Array
class Solution {
    public int waysToPartition(int[] nums, int k) {
        int n = nums.length;
        int[] s = new int[n];
        s[0] = nums[0];
        Map<Integer, Integer> right = new HashMap<>();
        for (int i = 0; i < n - 1; ++i) {
            right.merge(s[i], 1, Integer::sum);
            s[i + 1] = s[i] + nums[i + 1];
        }
        int ans = 0;
        if (s[n - 1] % 2 == 0) {
            ans = right.getOrDefault(s[n - 1] / 2, 0);
        }
        Map<Integer, Integer> left = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int d = k - nums[i];
            if ((s[n - 1] + d) % 2 == 0) {
                int t = left.getOrDefault((s[n - 1] + d) / 2, 0)
                    + right.getOrDefault((s[n - 1] - d) / 2, 0);
                ans = Math.max(ans, t);
            }
            left.merge(s[i], 1, Integer::sum);
            right.merge(s[i], -1, Integer::sum);
        }
        return ans;
    }
}

// Accepted solution for LeetCode #2025: Maximum Number of Ways to Partition an Array
func waysToPartition(nums []int, k int) (ans int) {
	n := len(nums)
	s := make([]int, n)
	s[0] = nums[0]
	right := map[int]int{}
	for i := range nums[:n-1] {
		right[s[i]]++
		s[i+1] = s[i] + nums[i+1]
	}
	if s[n-1]%2 == 0 {
		ans = right[s[n-1]/2]
	}
	left := map[int]int{}
	for i, x := range nums {
		d := k - x
		if (s[n-1]+d)%2 == 0 {
			t := left[(s[n-1]+d)/2] + right[(s[n-1]-d)/2]
			if ans < t {
				ans = t
			}
		}
		left[s[i]]++
		right[s[i]]--
	}
	return
}

# Accepted solution for LeetCode #2025: Maximum Number of Ways to Partition an Array
class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        n = len(nums)
        s = [nums[0]] * n
        right = defaultdict(int)
        for i in range(1, n):
            s[i] = s[i - 1] + nums[i]
            right[s[i - 1]] += 1

        ans = 0
        if s[-1] % 2 == 0:
            ans = right[s[-1] // 2]

        left = defaultdict(int)
        for v, x in zip(s, nums):
            d = k - x
            if (s[-1] + d) % 2 == 0:
                t = left[(s[-1] + d) // 2] + right[(s[-1] - d) // 2]
                if ans < t:
                    ans = t
            left[v] += 1
            right[v] -= 1
        return ans

// Accepted solution for LeetCode #2025: Maximum Number of Ways to Partition an Array
/**
 * [2025] Maximum Number of Ways to Partition an Array
 *
 * You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:
 *
 * 	1 <= pivot < n
 * 	nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
 *
 * You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.
 * Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.
 *  
 * Example 1:
 *
 * Input: nums = [2,-1,2], k = 3
 * Output: 1
 * Explanation: One optimal approach is to change nums[0] to k. The array becomes [<u>3</u>,-1,2].
 * There is one way to partition the array:
 * - For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.
 *
 * Example 2:
 *
 * Input: nums = [0,0,0], k = 1
 * Output: 2
 * Explanation: The optimal approach is to leave the array unchanged.
 * There are two ways to partition the array:
 * - For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
 * - For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.
 *
 * Example 3:
 *
 * Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
 * Output: 4
 * Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,<u>-33</u>,-20,-15,15,-16,7,19,-10,0,-13,-14].
 * There are four ways to partition the array.
 *
 *  
 * Constraints:
 *
 * 	n == nums.length
 * 	2 <= n <= 10^5
 * 	-10^5 <= k, nums[i] <= 10^5
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/maximum-number-of-ways-to-partition-an-array/
// discuss: https://leetcode.com/problems/maximum-number-of-ways-to-partition-an-array/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn ways_to_partition(nums: Vec<i32>, k: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2025_example_1() {
        let nums = vec![2, -1, 2];
        let k = 3;

        let result = 1;

        assert_eq!(Solution::ways_to_partition(nums, k), result);
    }

    #[test]
    #[ignore]
    fn test_2025_example_2() {
        let nums = vec![0, 0, 0];
        let k = 1;

        let result = 2;

        assert_eq!(Solution::ways_to_partition(nums, k), result);
    }

    #[test]
    #[ignore]
    fn test_2025_example_3() {
        let nums = vec![22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14];
        let k = -33;

        let result = 4;

        assert_eq!(Solution::ways_to_partition(nums, k), result);
    }
}

// Accepted solution for LeetCode #2025: Maximum Number of Ways to Partition an Array
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #2025: Maximum Number of Ways to Partition an Array
// class Solution {
//     public int waysToPartition(int[] nums, int k) {
//         int n = nums.length;
//         int[] s = new int[n];
//         s[0] = nums[0];
//         Map<Integer, Integer> right = new HashMap<>();
//         for (int i = 0; i < n - 1; ++i) {
//             right.merge(s[i], 1, Integer::sum);
//             s[i + 1] = s[i] + nums[i + 1];
//         }
//         int ans = 0;
//         if (s[n - 1] % 2 == 0) {
//             ans = right.getOrDefault(s[n - 1] / 2, 0);
//         }
//         Map<Integer, Integer> left = new HashMap<>();
//         for (int i = 0; i < n; ++i) {
//             int d = k - nums[i];
//             if ((s[n - 1] + d) % 2 == 0) {
//                 int t = left.getOrDefault((s[n - 1] + d) / 2, 0)
//                     + right.getOrDefault((s[n - 1] - d) / 2, 0);
//                 ans = Math.max(ans, t);
//             }
//             left.merge(s[i], 1, Integer::sum);
//             right.merge(s[i], -1, Integer::sum);
//         }
//         return ans;
//     }
// }