Find maximum sum possible equal sum of three stacks

Problem Statement

Given three stacks of positive integers, remove elements from the top of stacks to make their sums equal. Find the maximum possible equal sum.

Constraints:

• 1 ≤ n1, n2, n3 ≤ 10^5
• 1 ≤ stack[i][j] ≤ 10^9

Example:

• Input:

  • stack1 = [3, 2, 1, 1, 1] (top to bottom)
  • stack2 = [4, 3, 2]
  • stack3 = [1, 1, 4, 1]

• Output: 5

• Explanation:

  • Stack1: Remove 3, keep [2,1,1,1] → sum = 5
  • Stack2: Remove 4,3, keep [2] → sum = 2... that's not 5

  Let me recalculate with bottom to top:

  • Stack1 from bottom: [1,1,1,2,3], top is 3
  • Remove 3,2: remaining [1,1,1] = 3...

  Actually for stacks, indexing matters. Let's say index 0 is top.

Approach 1: Brute Force (Try All Combinations)

Intuition

Try all possible ways of popping elements from each stack and find the maximum sum where all three stacks have equal sum.

Algorithm

1. For each possible number of elements to remove from stack1
2. For each possible number of elements to remove from stack2
3. For each possible number of elements to remove from stack3
4. Check if remaining sums are equal
5. Track maximum equal sum

public class Solution {
    public long maxEqualSum(int[] s1, int[] s2, int[] s3) {
        int n1 = s1.length, n2 = s2.length, n3 = s3.length;
        
        long[] sum1 = new long[n1 + 1];
        long[] sum2 = new long[n2 + 1];
        long[] sum3 = new long[n3 + 1];
        
        for (int i = n1 - 1; i >= 0; i--) {
            sum1[i] = sum1[i + 1] + s1[i];
        }
        for (int i = n2 - 1; i >= 0; i--) {
            sum2[i] = sum2[i + 1] + s2[i];
        }
        for (int i = n3 - 1; i >= 0; i--) {
            sum3[i] = sum3[i + 1] + s3[i];
        }
        
        long maxSum = 0;
        
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                for (int k = 0; k <= n3; k++) {
                    if (sum1[i] == sum2[j] && sum2[j] == sum3[k]) {
                        maxSum = Math.max(maxSum, sum1[i]);
                    }
                }
            }
        }
        
        return maxSum;
    }
}

Complexity Analysis

• Time Complexity: O(n1 × n2 × n3) - Three nested loops
• Space Complexity: O(n1 + n2 + n3) - For prefix sums

Approach 2: Three Pointers (Optimal)

Intuition

Start with full stacks. The stack with the maximum sum should have elements removed (popped from top) until all sums become equal.

Greedy Strategy: Always pop from the stack with the highest current sum. Continue until all sums are equal or a stack becomes empty.

Algorithm

1. Calculate initial sums of all three stacks
2. While sums are not equal:
   • Pop from the stack with maximum sum
   • Update its sum
3. Return the equal sum (or 0 if not possible)

public class Solution {
    public long maxEqualSum(int[] s1, int[] s2, int[] s3) {
        // Calculate initial sums
        long sum1 = 0, sum2 = 0, sum3 = 0;
        for (int x : s1) sum1 += x;
        for (int x : s2) sum2 += x;
        for (int x : s3) sum3 += x;
        
        int i = 0, j = 0, k = 0;
        int n1 = s1.length, n2 = s2.length, n3 = s3.length;
        
        while (i < n1 && j < n2 && k < n3) {
            if (sum1 == sum2 && sum2 == sum3) {
                return sum1;
            }
            
            if (sum1 >= sum2 && sum1 >= sum3) {
                sum1 -= s1[i++];
            } else if (sum2 >= sum1 && sum2 >= sum3) {
                sum2 -= s2[j++];
            } else {
                sum3 -= s3[k++];
            }
        }
        
        if (sum1 == sum2 && sum2 == sum3) {
            return sum1;
        }
        
        return 0;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] s1 = {3, 2, 1, 1, 1};
        int[] s2 = {4, 3, 2};
        int[] s3 = {1, 1, 4, 1};
        System.out.println(sol.maxEqualSum(s1, s2, s3));
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n1 + n2 + n3) - Each element popped at most once
• Space Complexity: O(1) - Only using constant extra space

Variant: Two Stacks

Key Takeaways

1. Greedy Choice: Always reduce the stack with maximum sum
2. Three Pointers: Track position in each stack
3. Convergence: Sums converge towards equality or zero
4. Time Efficiency: O(n) single pass instead of O(n³)
5. No Backtracking: Once an element is removed, it stays removed
6. Edge Case: If no equal sum possible, return 0
7. Application: Resource balancing, load distribution