algoadvance

Leetcode 1013. Partition Array Into Three Parts With Equal Sum

Problem Statement

You are given an integer array arr of length n that contains only positive integers. The task is to check if the array can be partitioned into three non-empty contiguous subarrays such that the sum of the elements in all three subarrays is equal.

Clarifying Questions

  1. Input constraints: Are all elements in the array guaranteed to be positive integers?
    • Yes, they are positive integers.
  2. Subarray definition: Are the subarrays required to be contiguous?
    • Yes, the partitions must be contiguous subarrays.
  3. Array length: What is the expected range of the array length n?
    • Typical constraints might be 1 ≤ arr.length ≤ 50000.
  4. Output: Should the function return a boolean indicating whether such a partition is possible?
    • Yes.

Strategy

  1. Calculate the total sum of the array.
  2. Check if the total sum can be divided into three equal integers: If not, return false.
  3. Iterate through the array to find two partitions such that each part has an equal sum.
  4. Keep track of the cumulative sum and count how many times we hit the required sum (i.e., total_sum / 3) before the end of the array.

Code

public class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = 0;
        for (int num : arr) {
            totalSum += num;
        }
        
        if (totalSum % 3 != 0) {
            return false;
        }
        
        int targetSum = totalSum / 3;
        int currentSum = 0;
        int partitionCount = 0;

        for (int i = 0; i < arr.length; i++) {
            currentSum += arr[i];
            if (currentSum == targetSum) {
                partitionCount++;
                currentSum = 0;
                // If we found all 3 partitions
                if (partitionCount == 2) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Time Complexity

This solution efficiently checks whether the array can be divided into three parts with equal sum using linear time and constant space, making it suitable for large input sizes as specified in typical constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI