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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →