Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

All values are positive, so begin with the total and remove as little as possible to fix its remainder modulo three. To remove remainder one, choose one remainder-one value or two remainder-two values; remainder two is symmetric. Larger removal groups contain avoidable positive subsets summing to a multiple of three.

Approach

Sort the values with remainders one and two into separate lists. If the total is already divisible by three, keep it. Otherwise compare the cheapest available single-value and two-value removals for the required remainder, using the smallest entries of those lists. Subtract the cheaper valid removal. The empty subset is allowed, so this can correctly return zero.

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        r1 = sorted([x for x in nums if x % 3 == 1])
        r2 = sorted([x for x in nums if x % 3 == 2])
        s = sum(nums)
        remove = float('inf')

        if s % 3 != 0:
            if s % 3 == 1:
                if r1:
                    remove = min(remove, r1[0])
                if len(r2) >= 2:
                    remove = min(remove, r2[0] + r2[1])
            else:
                if len(r1) >= 2:
                    remove = min(remove, r1[0] + r1[1])
                if r2:
                    remove = min(remove, r2[0])

        return s if remove == float('inf') else s - remove

Complexity analysis

For n numbers, building and sorting the two remainder lists takes O(n log n) time and O(n) auxiliary space; all subsequent candidate checks are O(1).