Partition Array Into Three Parts With Equal Sum

Partition Array Into Three Parts With Equal Sum

What is this problem about?

The Partition Array Into Three Parts With Equal Sum problem asks whether you can split the array into three non-empty contiguous parts that all have the same sum. The total sum must be divisible by 3, and you must find two valid split points. This easy coding problem tests greedy boundary finding. The array and greedy interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft, Meta, and Bloomberg ask this as a quick screening problem testing sum divisibility and greedy scanning. It validates that candidates can correctly handle the "three parts, not two" condition and the edge case where total%3≠0.

Algorithmic pattern used

Greedy prefix sum scan. Compute total sum. If total%3≠0, return false. Target = total/3. Scan left to right: when prefix sum reaches target, increment partition count and reset for next partition. If 3 partitions found before exhausting the array (with the third being non-empty), return true.

Example explanation

arr=[0,2,1,-6,6,-7,9,1,2,0,1]. Total=9. Target=3.

• Scan: 0,2,3→first partition found. count=1.
• Continue: 1,-6,6,-7,9,1,2,0,1 → prefix sum reaches 3 again at some point. count=2.
• Third part: has remaining elements. return true.

Common mistakes candidates make

• Not handling total%3≠0 (immediate false).
• Requiring exactly three equal parts (last part is whatever remains — don't split it further).
• Triggering on partial sums when third part would be empty.
• Off-by-one: all three parts must be non-empty.

Interview preparation tip

Three-way equal sum partition: first compute if total is divisible by 3. Then find the first two split points greedily (when prefix sum hits target, record split). The third part is implicitly defined. Only 2 splits needed, not 3. Practice similar "partition into k parts with equal sum" problems — they're cleaner than full DP subset sum variants.