.png)
Check if Array Can Be Divided into Equal Sum Subarrays
Problem Statement
You are given an integer array arr.
Determine whether it is possible to divide the array into two non-empty contiguous subarrays such that both subarrays have equal sum.
Return true if possible, otherwise return false.
Example 1
Input
arr = [1, 2, 3, 3]
Output
true
Explanation
The array can be divided as:
[1, 2, 3] | [3]
Sum = 6 Sum = 3 ❌
Correct split:
[1, 2] | [3, 3]
Sum = 3 Sum = 6 ❌
Wait — correct split:
[1, 2, 3] | [3]
Total sum = 9 → ❌
Actually:
[1, 2] | [3, 3]
3 == 6 ❌
❌ Not possible
Example 2
Input
arr = [1, 5, 11, 5]
Output
true
Explanation
[1, 5, 5] | [11]
Sum = 11 Sum = 11
Example 3
Input
arr = [2, 4, 6, 3]
Output
false
Why This Problem Is Important
- Very common prefix sum problem
- Asked in coding interviews
- Tests understanding of array partition
- Helps in learning subarray sum logic
- Foundation for partition & DP problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix Sum (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
Try every possible partition point and compare the sum of left and right subarrays.
Algorithm
- Loop index i from 0 to n-2
- Compute sum of arr[0…i]
- Compute sum of arr[i+1…n-1]
- If both sums are equal → return true
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {1,5,11,5};
int n = 4;
for(int i = 0; i < n - 1; i++) {
int left = 0, right = 0;
for(int j = 0; j <= i; j++)
left += arr[j];
for(int j = i + 1; j < n; j++)
right += arr[j];
if(left == right) {
printf("true");
return 0;
}
}
printf("false");
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,5,11,5};
int n = 4;
for(int i = 0; i < n - 1; i++) {
int left = 0, right = 0;
for(int j = 0; j <= i; j++)
left += arr[j];
for(int j = i + 1; j < n; j++)
right += arr[j];
if(left == right) {
cout << "true";
return 0;
}
}
cout << "false";
return 0;
}
Java
public class EqualSumSubarrays {
public static void main(String[] args) {
int[] arr = {1,5,11,5};
for(int i = 0; i < arr.length - 1; i++) {
int left = 0, right = 0;
for(int j = 0; j <= i; j++)
left += arr[j];
for(int j = i + 1; j < arr.length; j++)
right += arr[j];
if(left == right) {
System.out.print(true);
return;
}
}
System.out.print(false);
}
}
Python
arr = [1,5,11,5]
n = len(arr)
for i in range(n - 1):
left = sum(arr[:i+1])
right = sum(arr[i+1:])
if left == right:
print(True)
break
else:
print(False)
JavaScript
let arr = [1,5,11,5];
let found = false;
for (let i = 0; i < arr.length - 1; i++) {
let left = 0, right = 0;
for (let j = 0; j <= i; j++) left += arr[j];
for (let j = i + 1; j < arr.length; j++) right += arr[j];
if (left === right) {
found = true;
break;
}
}
console.log(found);
Approach 2: Prefix Sum (Optimal)
Idea
If total sum is even, check if there exists a prefix with sum = totalSum / 2.
Algorithm
- Compute total sum of array
- If total sum is odd → return false
- Traverse array and maintain prefix sum
- If prefix sum equals half of total → return true
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {1,5,11,5};
int n = 4;
int total = 0;
for(int i = 0; i < n; i++)
total += arr[i];
if(total % 2 != 0) {
printf("false");
return 0;
}
int prefix = 0;
for(int i = 0; i < n - 1; i++) {
prefix += arr[i];
if(prefix == total / 2) {
printf("true");
return 0;
}
}
printf("false");
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,5,11,5};
int n = 4;
int total = 0;
for(int i = 0; i < n; i++)
total += arr[i];
if(total % 2 != 0) {
cout << "false";
return 0;
}
int prefix = 0;
for(int i = 0; i < n - 1; i++) {
prefix += arr[i];
if(prefix == total / 2) {
cout << "true";
return 0;
}
}
cout << "false";
return 0;
}
Java
public class EqualSumSubarrays {
public static void main(String[] args) {
int[] arr = {1,5,11,5};
int total = 0;
for(int x : arr)
total += x;
if(total % 2 != 0) {
System.out.print(false);
return;
}
int prefix = 0;
for(int i = 0; i < arr.length - 1; i++) {
prefix += arr[i];
if(prefix == total / 2) {
System.out.print(true);
return;
}
}
System.out.print(false);
}
}
Python
arr = [1,5,11,5]
total = sum(arr)
if total % 2 != 0:
print(False)
else:
prefix = 0
for i in range(len(arr) - 1):
prefix += arr[i]
if prefix == total // 2:
print(True)
break
else:
print(False)
JavaScript
let arr = [1,5,11,5];
let total = arr.reduce((a,b) => a + b, 0);
if (total % 2 !== 0) {
console.log(false);
} else {
let prefix = 0;
let possible = false;
for (let i = 0; i < arr.length - 1; i++) {
prefix += arr[i];
if (prefix === total / 2) {
possible = true;
break;
}
}
console.log(possible);
}
Dry Run
Input
[1,5,11,5]
Total Sum = 22
Half = 11
Prefix Sums:
1 → 6 → 11 ✔
Summary
- Brute force checks all splits
- Prefix sum is clean and optimal
- Runs in O(n) time & O(1) space
- Core interview & array partition problem
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
