LeetCode 3780 - Maximum Sum of Three Numbers Divisible by Three

LeetCode Problem 3780

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Here is a comprehensive, detailed solution guide for LeetCode 3780 - Maximum Sum of Three Numbers Divisible by Three, following your requested format:

Problem Understanding

The problem asks us to select exactly three integers from the given integer array nums such that the sum of those three integers is divisible by 3. Among all possible valid triplets, we need to return the maximum sum. If no such triplet exists, the function should return 0.

The input array nums contains integers between 1 and 10^5 with length between 3 and 10^5. This means a brute-force approach that checks all triplets would be computationally infeasible because the number of triplets can be on the order of $O(n^3)$ for large inputs. The constraints guarantee that there are at least three numbers, so selecting three elements is always possible, but divisibility by 3 is not guaranteed.

Edge cases that could cause problems include arrays where all numbers leave the same remainder modulo 3 (e.g., all numbers are 1 mod 3), arrays with duplicates, or arrays where the maximum sum divisible by 3 involves skipping the largest numbers.

Approaches

Brute Force Approach: A naive solution iterates over all possible triplets using three nested loops, computes their sum, and checks divisibility by 3. This is guaranteed to find the correct maximum sum but has a time complexity of $O(n^3)$, which is too slow for $n \sim 10^5$.

Optimal Approach: The key insight is to use the property of numbers modulo 3. Every integer has a remainder of 0, 1, or 2 when divided by 3. Let’s group numbers into three lists based on these remainders:

• mod0: numbers divisible by 3
• mod1: numbers giving remainder 1
• mod2: numbers giving remainder 2

To form a sum divisible by 3, we have these options for three numbers:

1. Three numbers from mod0.
2. One number from each of mod0, mod1, and mod2.
3. Three numbers all from mod1.
4. Three numbers all from mod2.

We can reduce the problem to picking the largest candidates from these groups. Sorting each list in descending order allows us to quickly consider only the top three candidates from each group since any other combination would be smaller.

By evaluating all valid combinations from these candidates, we can compute the maximum sum divisible by 3 in linear time relative to the input size.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Check all triplets explicitly
Optimal	O(n log n)	O(n)	Use modulo groups and sorting to pick best candidates efficiently

Algorithm Walkthrough

1. Initialize three empty lists: mod0, mod1, mod2.
2. Iterate over each number in nums:

• If num % 3 == 0, append to mod0.
• If num % 3 == 1, append to mod1.
• If num % 3 == 2, append to mod2.

3. Sort each list in descending order to prioritize largest numbers.
4. Initialize a variable max_sum = 0.
5. Check all valid triplet combinations:

• If len(mod0) >= 3, compute sum of the top three numbers in mod0 and update max_sum.
• If len(mod1) >= 3, compute sum of the top three numbers in mod1 and update max_sum.
• If len(mod2) >= 3, compute sum of the top three numbers in mod2 and update max_sum.
• If all lists have at least one element, compute mod0[0] + mod1[0] + mod2[0] and update max_sum.

6. Return max_sum.

Why it works: Grouping by modulo 3 ensures we only consider combinations that can form a sum divisible by 3. Sorting ensures that we always select the largest numbers possible in each category. This guarantees the maximum sum is found without enumerating all triplets.

Python Solution

from typing import List

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        mod0, mod1, mod2 = [], [], []
        
        for num in nums:
            if num % 3 == 0:
                mod0.append(num)
            elif num % 3 == 1:
                mod1.append(num)
            else:
                mod2.append(num)
        
        mod0.sort(reverse=True)
        mod1.sort(reverse=True)
        mod2.sort(reverse=True)
        
        max_sum = 0
        
        if len(mod0) >= 3:
            max_sum = max(max_sum, sum(mod0[:3]))
        if len(mod1) >= 3:
            max_sum = max(max_sum, sum(mod1[:3]))
        if len(mod2) >= 3:
            max_sum = max(max_sum, sum(mod2[:3]))
        if mod0 and mod1 and mod2:
            max_sum = max(max_sum, mod0[0] + mod1[0] + mod2[0])
        
        return max_sum

Implementation Explanation: We categorize numbers by remainder, sort each category to prioritize larger numbers, then check all feasible combinations of three numbers that sum to a multiple of 3. The solution is concise, avoids unnecessary combinations, and ensures correctness.

Go Solution

import "sort"

func maximumSum(nums []int) int {
    mod0, mod1, mod2 := []int{}, []int{}, []int{}
    
    for _, num := range nums {
        switch num % 3 {
        case 0:
            mod0 = append(mod0, num)
        case 1:
            mod1 = append(mod1, num)
        case 2:
            mod2 = append(mod2, num)
        }
    }
    
    sort.Sort(sort.Reverse(sort.IntSlice(mod0)))
    sort.Sort(sort.Reverse(sort.IntSlice(mod1)))
    sort.Sort(sort.Reverse(sort.IntSlice(mod2)))
    
    maxSum := 0
    
    if len(mod0) >= 3 {
        sum := mod0[0] + mod0[1] + mod0[2]
        if sum > maxSum {
            maxSum = sum
        }
    }
    if len(mod1) >= 3 {
        sum := mod1[0] + mod1[1] + mod1[2]
        if sum > maxSum {
            maxSum = sum
        }
    }
    if len(mod2) >= 3 {
        sum := mod2[0] + mod2[1] + mod2[2]
        if sum > maxSum {
            maxSum = sum
        }
    }
    if len(mod0) >= 1 && len(mod1) >= 1 && len(mod2) >= 1 {
        sum := mod0[0] + mod1[0] + mod2[0]
        if sum > maxSum {
            maxSum = sum
        }
    }
    
    return maxSum
}

Go-specific Notes: We use slices for dynamic arrays and sort.Sort(sort.Reverse(...)) to sort descending. All other logic mirrors the Python solution. Go does not have built-in slicing with [:3] for arbitrary length checks, so explicit length checks are required.

Worked Examples

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

Step	mod0	mod1	mod2	max_sum
Initial split	[]	[1,4]	[2,3]	0
Sorted	[]	[4,1]	[3,2]	0
Check mod0 ≥ 3	no	-	-	0
Check mod1 ≥ 3	no	-	-	0
Check mod2 ≥ 3	no	-	-	0
Check 1 from each	possible	-	-	4+3+2=9

Return 9.

Example 2: nums = [2,1,5]

Step	mod0	mod1	mod2	max_sum
Initial split	[]	[1]	[2,5]	0
Sorted	[]	[1]	[5,2]	0
Check mod0 ≥ 3	no	-	-	0
Check mod1 ≥ 3	no	-	-	0
Check mod2 ≥ 3	no	-	-	0
Check 1 from each	mod0 empty → impossible	-	-	0

Return 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Splitting into groups is O(n), sorting each group is O(n log n) in total
Space	O(n)	Three lists for modulo groups can each hold up to n elements

This is efficient because we avoid checking all triplets explicitly. Sorting ensures we only consider the largest