Balanced Boundary Partition — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, you need to partition it into three non-empty contiguous subarrays: Left, Mid, and Right. The partition must satisfy the condition that the sum of the elements in the Left subarray is equal to the sum of the elements in the Right subarray. Your goal is to find the maximum possible sum of the Mid subarray among all valid partitions. If no such partition is possible, return -10^9.
Examples
Input
[1, 2, 3, 2, 1]
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 2, 1], we can partition it into [1, 2], [3], and [2, 1]. The sum of the elements in the Left subarray [1, 2] is 3, which is equal to the sum of the elements in the Right subarray [2, 1]. The sum of the elements in the Mid subarray [3] is 3, which is the maximum possible sum among all valid partitions.
Input
[1, 1, 1, 1, 1]
Output
1
Explanation: Step-by-step: with input [1, 1, 1, 1, 1], we can partition it into [1, 1], [1], and [1, 1]. The sum of the elements in the Left subarray [1, 1] is 2, which is equal to the sum of the elements in the Right subarray [1, 1]. The sum of the elements in the Mid subarray [1] is 1, which is the maximum possible sum among all valid partitions.
Constraints
- 3 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- The cumulative sums and the output fit within a standard 32-bit signed integer.
Optimal Approach & Strategy
Precalculate prefix sums and store the first and last occurrence indices of each sum value in a hash map. For every possible partition, verify if the prefix sum at the start of the right segment matches a prefix sum captured earlier, allowing for O(n) traversal using the map.
Brute Force Approach
Iterate through all possible cut points i and j where 0 < i < j < n-1, calculate the sum of Left (0 to i-1), Mid (i to j-1), and Right (j to n-1). Check if sum(Left) == sum(Right) and update the maximum Mid sum.
Verified Code Solutions
function solution(nums) { let maxSum = -Infinity; for (let i = 1; i < nums.length - 1; i++) { for (let j = i + 1; j < nums.length; j++) { let leftSum = nums.slice(0, i).reduce((a, b) => a + b, 0); let midSum = nums.slice(i, j).reduce((a, b) => a + b, 0); let rightSum = nums.slice(j).reduce((a, b) => a + b, 0); if (leftSum === rightSum) { maxSum = Math.max(maxSum, midSum); } } } return maxSum; }class Solution { public: int solution(vector<int>& nums) { int maxSum = INT_MIN; for (int i = 1; i < nums.size() - 1; i++) { for (int j = i + 1; j < nums.size(); j++) { int leftSum = 0; for (int k = 0; k < i; k++) { leftSum += nums[k]; } int midSum = 0; for (int k = i; k < j; k++) { midSum += nums[k]; } int rightSum = 0; for (int k = j; k < nums.size(); k++) { rightSum += nums[k]; } if (leftSum == rightSum) { maxSum = max(maxSum, midSum); } } } return maxSum; } };class Solution { public int solution(int[] nums) { int maxSum = Integer.MIN_VALUE; for (int i = 1; i < nums.length - 1; i++) { for (int j = i + 1; j < nums.length; j++) { int leftSum = 0; for (int k = 0; k < i; k++) { leftSum += nums[k]; } int midSum = 0; for (int k = i; k < j; k++) { midSum += nums[k]; } int rightSum = 0; for (int k = j; k < nums.length; k++) { rightSum += nums[k]; } if (leftSum == rightSum) { maxSum = Math.max(maxSum, midSum); } } } return maxSum; } }def solution(nums): max_sum = float('-inf') for i in range(1, len(nums) - 1): for j in range(i + 1, len(nums)): left_sum = sum(nums[:i]) mid_sum = sum(nums[i:j]) right_sum = sum(nums[j:]) if left_sum == right_sum: max_sum = max(max_sum, mid_sum) return max_sumfunction solution(nums) { let maxSum = -Infinity; for (let i = 1; i < nums.length - 1; i++) { for (let j = i + 1; j < nums.length; j++) { let leftSum = nums.slice(0, i).reduce((a, b) => a + b, 0); let midSum = nums.slice(i, j).reduce((a, b) => a + b, 0); let rightSum = nums.slice(j).reduce((a, b) => a + b, 0); if (leftSum === rightSum) { maxSum = Math.max(maxSum, midSum); } } } return maxSum; }Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.