LeetCode 1262 - Greatest Sum Divisible by Three

LeetCode Problem 1262

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to find the maximum sum of elements from an integer array nums such that the sum is divisible by three. In other words, we are allowed to pick any subset of numbers from the array, and our goal is to maximize the sum of that subset under the condition that the sum modulo 3 equals 0. The array nums has elements ranging from 1 to 10,000 and can be as large as 40,000 elements, so any brute-force approach that tries all subsets will be computationally infeasible.

The constraints imply that a naive solution that checks every subset is not practical due to exponential complexity. The problem guarantees that all elements are positive integers, so the sum is always non-negative. Edge cases to consider include arrays where no combination of numbers is divisible by three, arrays with a single element, and arrays where all elements are already divisible by three.

Approaches

A brute-force approach would involve generating all possible subsets of nums, computing the sum of each subset, and checking if it is divisible by three. While this guarantees the correct answer, the time complexity is O(2^n), which is far too slow for the input constraints (up to 40,000 elements).

The key observation for a more optimal solution is based on modular arithmetic. Any number modulo 3 can be 0, 1, or 2. To maximize a sum divisible by three, we can maintain the maximum sums with remainders 0, 1, and 2 while iterating through the array. For each number, we consider adding it to the existing sums for each remainder and update the maximum possible sums for each remainder. This approach leverages dynamic programming and ensures we only store three variables, giving us a linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all subsets, sum them, and pick the maximum divisible by 3
Optimal	O(n)	O(1)	Use dynamic programming with three variables to track max sums modulo 3

Algorithm Walkthrough

1. Initialize an array dp of size 3 with dp[0] = 0 and dp[1] = dp[2] = -inf. This array will store the maximum sums for remainders 0, 1, and 2.
2. Iterate through each number num in nums.
3. For each number, create a temporary copy of the current dp array called new_dp.
4. For each remainder r in {0, 1, 2}, calculate a potential new sum dp[r] + num.
5. Determine the remainder of this new sum modulo 3.
6. Update new_dp[new_remainder] to be the maximum of its current value and the new sum.
7. After processing all remainders, set dp = new_dp.
8. After iterating through all numbers, dp[0] will contain the maximum sum divisible by three.

Why it works: This works because at each step we consider all possibilities of adding the current number to previously computed sums for each remainder. By keeping only the maximum sum for each remainder, we ensure optimality and avoid redundant calculations. The modulo 3 operation guarantees we track sums divisible by three correctly.

Python Solution

from typing import List

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, float('-inf'), float('-inf')]
        for num in nums:
            new_dp = dp[:]
            for r in range(3):
                new_sum = dp[r] + num
                new_dp[new_sum % 3] = max(new_dp[new_sum % 3], new_sum)
            dp = new_dp
        return dp[0]

The Python implementation initializes a dp array to track maximum sums for each remainder modulo 3. For each number in nums, it calculates potential new sums and updates the maximum for each remainder. At the end, dp[0] contains the maximum sum divisible by 3. Using float('-inf') ensures we correctly handle sums that cannot be formed for certain remainders initially.

Go Solution

func maxSumDivThree(nums []int) int {
    dp := [3]int{0, -1 << 60, -1 << 60}
    for _, num := range nums {
        newDp := dp
        for r := 0; r < 3; r++ {
            newSum := dp[r] + num
            if newSum > newDp[newSum%3] {
                newDp[newSum%3] = newSum
            }
        }
        dp = newDp
    }
    return dp[0]
}

In Go, we use an array of size 3 to track the maximum sums for each remainder. Negative infinity is represented by -1 << 60 to safely handle large negative sums. The logic mirrors Python's approach but uses Go-specific syntax and slice handling.

Worked Examples

Example 1: nums = [3,6,5,1,8]

Step	dp[0]	dp[1]	dp[2]
Initial	0	-inf	-inf
num=3	3	-inf	-inf
num=6	9	-inf	-inf
num=5	9	14	5
num=1	10	15	9
num=8	18	23	19

Return dp[0] = 18.

Example 2: nums = [4]

Step	dp[0]	dp[1]	dp[2]
Initial	0	-inf	-inf
num=4	0	4	-inf

Return dp[0] = 0.

Example 3: nums = [1,2,3,4,4]

Step	dp[0]	dp[1]	dp[2]
Initial	0	-inf	-inf
num=1	0	1	-inf
num=2	3	1	2
num=3	6	4	5
num=4	10	9	9
num=4	12	13	13

Return dp[0] = 12.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number is processed once and we update three remainders
Space	O(1)	Only three values are stored regardless of input size

The linear time complexity arises because we iterate through the array once and perform constant work for each element. The space complexity is constant since we only track three maximum sums.

Test Cases

# test cases
assert Solution().maxSumDivThree([3,6,5,1,8]) == 18  # example 1
assert Solution().maxSumDivThree([4]) == 0           # example 2
assert Solution().maxSumDivThree([1,2,3,4,4]) == 12  # example 3
assert Solution().maxSumDivThree([1,1,1,1]) == 3     # all ones
assert Solution().maxSumDivThree([3,3,3]) == 9       # all divisible by 3
assert Solution().maxSumDivThree([1,2]) == 0         # cannot form divisible by 3
assert Solution().maxSumDivThree([1,2,2,2,2]) == 9   # mix to reach max divisible

Test	Why
[3,6,5,1,8]	Typical case with multiple choices
[4]	Single element not divisible by 3
[1,2,3,4,4]	Mix of numbers with different remainders
[1,1,1,1]	All numbers same remainder 1
[3,3,3]	All numbers divisible by 3
[1,2]	Cannot form sum divisible by 3
[1,2,2,2,2]	Testing combination for maximum sum

Edge Cases

One important edge case is when the array has only one element. If this element is divisible by 3, the result is the element itself; otherwise, it is zero. Another edge case occurs when all elements have the same remainder modulo 3. The algorithm correctly combines or skips elements to form sums divisible by 3, leveraging the dynamic programming update. A third edge case involves large arrays with high numbers close to 10,000. The algorithm handles this efficiently because it only maintains three sums and avoids building any large subsets or storing all possible sums.