DDSA Solutions

Max Equal Sum in 3 Stacks

Problem Overview

Each array is a stack with its top at index 0.

Intuition

Each array is a stack with its top at index 0. The only allowed move is to discard a prefix of tops from any stack. The largest common remaining sum is found by first totaling every stack, then always discarding from the stack that currently holds the largest remaining sum. Shrinking the heaviest stack is the only way the three totals can meet. When all three sums become equal, that shared value is the maximum possible equal sum, because every earlier step only removed mass from a side that was too heavy. If any stack runs out of elements before the sums match, no common positive total exists and the answer is 0.

Algorithm

  1. 1Compute the sum of every element in each of the three stacks.
  2. 2Keep an index at the current top of each stack.
  3. 3While every stack still has elements, return the shared sum when all three totals are equal.
  4. 4Otherwise subtract the current top from the stack with the largest remaining sum and advance that top index.
  5. 5Return 0 when any stack is emptied before the sums match.

Example Walkthrough

Input: s1 = [3, 2, 1, 1, 1], s2 = [4, 3, 2], s3 = [2, 5, 4, 1]

  1. 1. The initial sums are 8, 9, and 12. Remove 2 from s3, then 5 from s3, leaving sums 8, 9, and 5.
  2. 2. Remove 4 from s2 and 3 from s1. The three remaining sums are all 5.
  3. 3. No larger common total survives those forced removals, so the answer is 5.

Output: 5

Common Pitfalls

  • • The first array index is the top. Removals always advance from the front of each list.
  • • Compare the three remaining sums, not the original totals. Only the unpopped suffixes count.
  • • When two stacks tie for the largest sum, either may be reduced. Both keep the same invariant.
  • • An empty stack ends the search with 0. An equal sum of 0 is reported the same way.
Max Equal Sum in 3 Stacks.java
Java
// Approach: Sum each stack, then repeatedly remove the top of the stack
// whose remaining sum is largest. The three sums only meet when they are
// equal, and emptying any stack means no common positive total remains.
// Complexity: O(n1 + n2 + n3) time, O(1) extra space.
import java.util.ArrayList;

class Solution {
    public int maxEqualSum(ArrayList<Integer> s1, ArrayList<Integer> s2,
                           ArrayList<Integer> s3) {
        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.size(), n2 = s2.size(), n3 = s3.size();

        while (i < n1 && j < n2 && k < n3) {
            if (sum1 == sum2 && sum2 == sum3) {
                return (int) sum1;
            }
            if (sum1 >= sum2 && sum1 >= sum3) {
                sum1 -= s1.get(i++);
            } else if (sum2 >= sum3) {
                sum2 -= s2.get(j++);
            } else {
                sum3 -= s3.get(k++);
            }
        }
        return 0;
    }
}
Was this solution helpful?