375. Maximum Sum Possible With Equal Sum of Three Stacks

You are given three stacks of positive integers, each given as an array listing its elements from top to bottom. In one move you may remove the top element of any one stack. Repeatedly remove the top element of whichever stack currently has the strictly largest total sum, until all three stacks have equal total sum. Print that common sum (print 0 if they all end up empty).

Input: Three stacks are each given as a line with the stack's size followed by a line of that many space-separated integers, listed from top to bottom (six lines total for the three stacks). Output: Print a single integer - the common sum all three stacks are reduced to (0 if all end up empty).

1 <= size of each stack <= 10^5

If all three stacks eventually become completely empty, the answer is 0 - handled naturally by the simulation, since 'all equal' includes the case where all three sums have dropped to zero.

Repeatedly pop from whichever of three stacks has the largest sum until all three sums are equal, then report that common sum. Brute force: Try every possible combination of how many elements to pop from each stack and check which combination gives equal sums - this is combinatorially expensive, when the direct greedy 'always pop the current largest' simulation reaches the answer efficiently. Optimised: Since popping from a NON-largest stack can never help close the gap toward equality (it would only make that stack even smaller relative to the others), always popping the current STRICTLY largest stack is the only productive move at every step - this greedy simulation directly and efficiently converges to the equal-sum state.

Precompute, for each of the three stacks, a prefix-sum array (from the top down) so the remaining sum after popping any number of elements can be looked up in O(1) instead of re-summed. Maintain a pointer into each stack's prefix-sum array, starting at the full sum, and repeatedly find the stack with the strictly largest current remaining sum and advance its pointer by one, equivalent to popping its top, stopping when all three current sums match. Looking up remaining sums via the precomputed arrays avoids re-scanning stack contents on every step, at the cost of the extra arrays. Time: O(n1+n2+n3) Space: O(n1+n2+n3)

Compute the initial total sum of each stack once with a single pass over each, and keep only these three numbers as running variables rather than full prefix-sum arrays. Repeatedly compare the three running totals, and whichever is strictly the largest gets reduced by subtracting its own current top element's value, moving that stack's internal top pointer down by one, with no array lookup or resumming needed. Continue until all three running totals are equal, the same process as before but using only three scalar variables instead of three extra arrays. Time: O(n1+n2+n3) Space: O(1)

Compute the total sum of each of the three stacks by adding up all their elements. Repeatedly identify which stack currently has the strictly largest total, pop its top element, and then recompute all three totals completely from scratch by re-summing their remaining elements. Continue this pop-and-recompute cycle until all three totals are equal, at which point that common value is the answer. Recomputing full sums after every single pop makes this far more expensive than necessary. Time: O((n1+n2+n3)^2) Space: O(1)

1. If the three current sums aren't already equal, popping from a stack that ISN'T the current largest can never help close the gap between sums. 2. Repeatedly pop the top of whichever stack has the STRICTLY largest sum right now. 3. Stop once no single stack is strictly the largest (either all three are equal, or all are empty) - that common sum is the answer.

Time: O(n1+n2+n3) - each pop operation permanently removes one element, so the total number of pops across the whole simulation is bounded by the combined size of all three stacks. Space: O(1) extra space beyond three running sum trackers (assuming the stacks themselves are given as arrays with a movable top index).

stacks that already start with equal sums (zero pops needed), one stack having to be popped all the way to empty, and stack sizes at their maximum of 10^5 to confirm the repeated-pop simulation runs efficiently.

Be ready to explain why popping the non-largest stack is NEVER useful - it's a simple but important justification for why this greedy simulation converges correctly rather than needing a more complex search.