Skip to main content

1013. Partition Array Into Three Parts With Equal Sum

easy

Determine whether an array can be split into three contiguous parts with equal sum. A clean prefix-sum + early-exit walk — total / 3 is the partition target.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums. Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]).

Constraints

  • 3 <= arr.length <= 5 * 10^4
  • -10^4 <= arr[i] <= 10^4

Examples

Example 1

Input
arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output
true

Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2

Input
arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output
false

Example 3

Input
arr = [3,3,6,5,-2,2,5,1,-9,4]
Output
true

Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If total sum isn't divisible by 3, the answer is false immediately.

Hint 2

Target per part is total / 3. Walk left to right accumulating a running sum; every time it hits the target, increment a part counter and reset the running sum.

Hint 3

Require the part counter to reach 3 (not just 2) — otherwise the third part is empty.

Hint 4

Watch out: with negatives, the running sum may oscillate above and below target. That's fine — keep walking.

Solution approach

Reveal approach

One-pass prefix-sum with target reset. Compute total = sum(arr). If total % 3 != 0, return false. Set target = total / 3. Walk the array maintaining running_sum and parts_found = 0. For each element x: running_sum += x. When running_sum == target, increment parts_found and reset running_sum = 0. Return parts_found >= 3. The >= 3 check (not == 3) handles arrays whose suffix is all zeros after the third target hit. The early reset on each match guarantees the three parts are contiguous and non-empty. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • prefix-sum
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Partition Array Into Three Parts With Equal Sum and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →