Balanced Boundary Partition — Problem Statement & Solution Guide

ArraysMediumcumulative-array-sum

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Balanced Boundary Partition problem optimally.

TopicArrays

Patterncumulative-array-sum

TimeO(n)

SpaceO(n)

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.

DSA Pattern Breakdown

"Balanced Boundary Partition"

medium

WHY DOES IT MATTER?

Balancing two boundaries while maximizing a middle segment is a classic two‑pointer / hash‑map pattern for linear‑time partition problems.

OPTIMIZATION CHALLENGE

The key is reducing the quadratic search over (i, j) pairs to a single pass by pre‑computing suffix sums and using constant‑time lookups.

REAL-WORLD CONNECTION

It mirrors load‑balancing where two edge servers must handle equal traffic, leaving the core network to carry the remaining load.

Cache the earliest index for each suffix sum; when scanning left to right, stop as soon as you find a matching right index that respects the non‑empty middle constraint.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to finding two equal‑sum boundaries that partition the array into three contiguous parts. By using prefix and suffix sums we can represent any possible left and right subarray sum in O(1) time, turning the search into a set‑membership problem.

Naïve enumeration of all (i, j) pairs is O(n^2) and quickly exceeds limits for n up to 10^5. The optimal paradigm leverages a single left‑to‑right sweep while maintaining a hash map of suffix sums to their earliest index, achieving linear time and allowing us to pick the smallest feasible left sum, which maximizes the middle sum.

Interview Questions on This Problem

Q1How does using prefix and suffix sums convert the problem into O(n) time?

Prefix sums give the sum of any left segment in O(1), and suffix sums give the sum of any right segment. By storing suffix sums in a hash map we can check equality with a left sum in constant time per index.

Q2Why do we aim to minimize the left sum rather than maximize the middle sum directly?

Mid sum = total – 2·leftSum, so maximizing Mid is equivalent to minimizing leftSum under the equality constraint. The smallest feasible left sum yields the largest possible middle segment.

Q3What edge case must be handled when the array contains all zeros?

All partitions satisfy leftSum = rightSum = 0, but we must still enforce non‑empty subarrays, so i must be ≤ n‑3 and j ≥ i+2. The answer becomes the total sum, which is zero.

Examples

Example 1

Input

[1, 2, 3, 2, 1]

Output

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.

Example 2

Input

[1, 1, 1, 1, 1]

Output

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

Pre‑compute suffix sums in a hash map, then iterate i from left, checking map for matching right sum with index ≥ i+2, tracking the minimal left sum.

Brute Force Approach

Try every possible split i and j, compute left, mid, right sums and keep the best where left == right.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

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_sum

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; }

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.