Three Stack Equal Sum
Description
You are given three stacks of positive integers s1, s2, and s3. Each stack is represented as a list where index 0 is the top of the stack. In one operation you may pop the top of any stack. You may perform any number of operations on any stack. Return the maximum sum you can leave on each stack such that all three stacks have equal sums. If the only achievable equal sum is 0 (by popping every element), return 0.
Examples
s1 = [3,2,1,1,1], s2 = [4,3,2], s3 = [1,1,4,1]5Pop one element off each stack to reach equal suffix sums of 5: s1 becomes [2,1,1,1] (sum 5), s2 becomes [3,2] (sum 5), s3 becomes [4,1] (sum 5).
s1 = [3,10], s2 = [4,5], s3 = [2,1,1,4,1]0Suffix sums of the three stacks share no positive value, so the maximum equal sum is 0.
s1 = [1,2,3], s2 = [4,5,6], s3 = [7,8,9]0Suffix-sum sets of s1, s2, s3 are {0,3,5,6}, {0,6,11,15}, {0,9,17,24}; their intersection is just {0}.
s1 = [5], s2 = [5], s3 = [5]5All three stacks already have the same sum 5, so no pops are needed.
Constraints
- •
1 ≤ s1.length, s2.length, s3.length ≤ 10⁵ - •
0 ≤ stack values ≤ 10⁹ - •
The top of each stack is at index 0.