3780. Maximum Sum of Three Numbers Divisible by Three

MediumGreedyArraySortingHeap (Priority Queue)

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

Your task is to choose exactly three integers from nums such that their sum is divisible by three.

Return the maximum possible sum of such a triplet. If no such triplet exists, return 0.

Example:

Suppose nums = [2, 6, 3, 5, 1]. One valid choice is the triplet (6, 3, 1), since 6 + 3 + 1 = 10, which is not divisible by 3. A better choice is (6, 5, 1) with sum 12, which is divisible by 3. The maximum valid sum here is 12.

Key Points:

You must pick exactly three numbers (not fewer, not more).
The sum of the three chosen numbers must be divisible by 3 (i.e., sum % 3 == 0).
Among all valid triplets, you want the one with the largest sum.
If it is impossible to form any triplet whose sum is divisible by 3, the answer is 0.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Classifying numbers by remainder modulo 3 and greedily selecting the largest triple that sums to a multiple of 3 relies on modular arithmetic.

Open in Flowchart

Intuition

The condition we care about is that the sum of the three chosen numbers is divisible by 3. A natural observation is that whether a sum is divisible by 3 depends only on the remainders of the numbers when divided by 3, not on the numbers themselves.

So instead of thinking about the actual values directly, we can classify every number by its remainder modulo 3. Each number falls into one of three groups:

g[0]: numbers where x % 3 == 0
g[1]: numbers where x % 3 == 1
g[2]: numbers where x % 3 == 2

If we pick one number from group a and one from group b, then the remainder so far is (a + b) % 3. To make the total sum divisible by 3, the third number must contribute exactly the remainder that "completes the cycle". That missing remainder is c = (3 - (a + b) % 3) % 3, so the third number should come from group g[c].

This means we only need to try every possible pair of group choices (a, b) (there are just 3 × 3 = 9 combinations), and for each one the third group c is fixed automatically.

The next question is: within each chosen group, which element should we take? Since we want the maximum sum, and all numbers in a group are interchangeable in terms of satisfying the divisibility rule, we should always prefer the largest available numbers. By sorting nums first, the largest numbers naturally end up at the back of each group's list, making it easy to grab the biggest candidates.

The only subtlety is that the three groups a, b, and c might overlap (for example, all three picked from the same group). To avoid accidentally reusing the same element, we temporarily remove the elements we've already taken before reaching into the next group, then put them back afterward. This way, each "take the largest remaining" step correctly reflects elements that are still available.

By enumerating all 9 group combinations and always greedily choosing the largest valid elements, we are guaranteed to find the maximum triplet sum that is divisible by 3. If no combination yields three usable elements, the answer stays 0.

Pattern Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

We use a combination of Sorting + Grouping + Enumeration.

Step 1: Sort the array

First, we sort nums in ascending order. This ensures that when we later split the numbers into groups, the largest numbers within each group sit at the end of their list, so we can grab the biggest candidates easily with pop() or by indexing [-1].

nums.sort()

Step 2: Group by remainder modulo 3

We create three lists g[0], g[1], and g[2], and place each number into the group matching its remainder x % 3. Because we iterate over the already-sorted nums, every group's list is also sorted in ascending order.

g = [[] for _ in range(3)]
for x in nums:
    g[x % 3].append(x)

Step 3: Enumerate group pairs (a, b)

We try every combination of choosing a group a for the first element and a group b for the second element. There are only 3 × 3 = 9 combinations to consider, so this is very cheap.

For each pair:

Take the largest element x from g[a] (via pop(), which removes it temporarily).
Take the largest element y from g[b] (also via pop()).
Compute the required third group c = (3 - (a + b) % 3) % 3. This is the remainder needed so that (a + b + c) % 3 == 0.
If g[c] still has an element, take the largest one z = g[c][-1] and update the answer with x + y + z.

ans = 0
for a in range(3):
    if g[a]:
        x = g[a].pop()
        for b in range(3):
            if g[b]:
                y = g[b].pop()
                c = (3 - (a + b) % 3) % 3
                if g[c]:
                    z = g[c][-1]
                    ans = max(ans, x + y + z)
                g[b].append(y)
        g[a].append(x)

Step 4: Handle overlapping groups correctly

The key trick here is the use of pop() and append(). Since a, b, and c may all point to the same group, we must avoid counting one number twice.

We pop() the element x from g[a] so it is no longer available when we later pick from g[b] or g[c].
Similarly, we pop() the element y from g[b].
After checking the pair, we restore the popped elements with append(), so the groups return to their original state before moving on to the next (a, b) combination.

This guarantees that the third element z = g[c][-1] reflects only the elements that are genuinely still available.

Step 5: Return the result

After all 9 combinations have been tried, ans holds the maximum valid triplet sum. If no combination produced three usable elements, ans remains 0.

return ans

Complexity Analysis

Time complexity: O(n × log n), dominated by the sorting step. The grouping is O(n), and the enumeration runs a constant 9 combinations, each doing O(1) work.
Space complexity: O(n), for the three groups that together store all n elements (ignoring the space used by sorting).

Example Walkthrough

Let's trace the solution using nums = [2, 6, 3, 5, 1].

Step 1: Sort the array

After sorting in ascending order:

nums = [1, 2, 3, 5, 6]

Step 2: Group by remainder modulo 3

We walk through each number and drop it into the group matching x % 3. Because the input is already sorted, each group is also sorted ascending:

Number	`x % 3`	Goes to
1	1	`g[1]`
2	2	`g[2]`
3	0	`g[0]`
5	2	`g[2]`
6	0	`g[0]`

Resulting groups:

g[0] = [3, 6]
g[1] = [1]
g[2] = [2, 5]

Step 3 & 4: Enumerate group pairs (a, b)

We start with ans = 0. For each pair (a, b), we pop() x from g[a] and y from g[b], compute the needed third group c = (3 - (a + b) % 3) % 3, and peek at g[c][-1] if available. Here are the key combinations:

`a`	`b`	`x` (pop a)	`y` (pop b)	`c`	`g[c]` after pops	`z`	sum `x+y+z`	divisible by 3?	`ans`
0	0	6	3	0	`[]`	—	—	—	0
0	1	6	1	2	`[2, 5]`	5	12	✅ (12 % 3 = 0)	12
0	2	6	5	1	`[1]`	1	12	✅	12
1	2	1	5	0	`[3, 6]`	6	12	✅	12
2	2	5	2	2	`[]`	—	—	—	12

Notice the pop()/append() trick in action: when a == b == 0, we pop 6 then 3, leaving g[0] empty, so no third element from g[0] is available — correctly preventing reuse. After each pair is checked, both elements are restored.

Step 5: Return the result

After all 9 combinations are tried, ans = 12.

The maximum valid triplet sum divisible by 3 is 12, achieved for instance by (6, 5, 1) — matching the expected output.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def maximumSum(self, nums: List[int]) -> int:
6        # dp[r] = the maximum sum (formed by any subset of processed numbers)
7        # whose total has remainder r modulo 3.
8        # -1 means that remainder state is not yet reachable.
9        dp = [0, -1, -1]
10
11        for num in nums:
12            # Snapshot the current states so each number is used at most once
13            # per update step.
14            new_dp = dp[:]
15            for remainder in range(3):
16                # Skip states that have not been reached yet.
17                if dp[remainder] == -1:
18                    continue
19                # Adding `num` shifts the remainder to (remainder + num) % 3.
20                next_remainder = (dp[remainder] + num) % 3
21                new_dp[next_remainder] = max(new_dp[next_remainder], dp[remainder] + num)
22            dp = new_dp
23
24        # dp[0] holds the maximum sum divisible by 3 (0 if none besides empty set).
25        return dp[0]
26```
27
28**Faithful rewrite of the original approach (group + brute force), with the bug addressed:**
29
30If you prefer to keep the original "group by remainder and combine three" idea, here is a standardized, commented version that correctly handles duplicate-group selection by taking distinct top elements:
31
32```python3
33from typing import List
34
35
36class Solution:
37    def maximumSum(self, nums: List[int]) -> int:
38        # Sort so the largest numbers sit at the end of each remainder group.
39        nums.sort()
40
41        # groups[r] collects all numbers whose value % 3 == r, in ascending order.
42        groups = [[] for _ in range(3)]
43        for value in nums:
44            groups[value % 3].append(value)
45
46        answer = 0
47
48        # Try every pair of remainders (a, b); the third remainder c is forced
49        # so that (a + b + c) % 3 == 0.
50        for a in range(3):
51            if not groups[a]:
52                continue
53            # Take the current largest number from group a.
54            first = groups[a].pop()
55
56            for b in range(3):
57                if not groups[b]:
58                    continue
59                # Take the current largest number from group b
60                # (already excludes `first` since it was popped above).
61                second = groups[b].pop()
62
63                # Required third remainder to make the sum divisible by 3.
64                c = (3 - (a + b) % 3) % 3
65                if groups[c]:
66                    third = groups[c][-1]  # Largest remaining number in group c.
67                    answer = max(answer, first + second + third)
68
69                # Restore group b for the next iteration.
70                groups[b].append(second)
71
72            # Restore group a for the next iteration.
73            groups[a].append(first)
74
75        return answer
76

1class Solution {
2    public int maximumSum(int[] nums) {
3        // Sort ascending so the largest elements end up at the tail of each group.
4        Arrays.sort(nums);
5
6        // Bucket numbers by their remainder modulo 3 (groups 0, 1, 2).
7        // Within each group the values remain in ascending order.
8        List<Integer>[] groups = new ArrayList[3];
9        Arrays.setAll(groups, key -> new ArrayList<>());
10        for (int value : nums) {
11            groups[value % 3].add(value);
12        }
13
14        int answer = 0;
15
16        // Choose the remainder class for the first number.
17        for (int remainderA = 0; remainderA < 3; remainderA++) {
18            if (groups[remainderA].isEmpty()) {
19                continue;
20            }
21            // Take (remove) the largest element from group A so it cannot be reused.
22            int valueA = groups[remainderA].remove(groups[remainderA].size() - 1);
23
24            // Choose the remainder class for the second number.
25            for (int remainderB = 0; remainderB < 3; remainderB++) {
26                if (groups[remainderB].isEmpty()) {
27                    continue;
28                }
29                // Take (remove) the largest remaining element from group B.
30                int valueB = groups[remainderB].remove(groups[remainderB].size() - 1);
31
32                // The third remainder is fixed so that the total sum is divisible by 3:
33                // (remainderA + remainderB + remainderC) % 3 == 0.
34                int remainderC = (3 - (remainderA + remainderB) % 3) % 3;
35
36                if (!groups[remainderC].isEmpty()) {
37                    // Peek the largest remaining element from group C (no removal needed).
38                    int valueC = groups[remainderC].get(groups[remainderC].size() - 1);
39                    answer = Math.max(answer, valueA + valueB + valueC);
40                }
41
42                // Restore element B for the next iteration.
43                groups[remainderB].add(valueB);
44            }
45
46            // Restore element A for the next iteration.
47            groups[remainderA].add(valueA);
48        }
49
50        return answer;
51    }
52}
53```
54
55**Key points of the logic:**
56
571. **Sorting + bucketing:** After sorting, each group's last element is its maximum. This guarantees that when we pick the tail, we always get the largest available candidate of that remainder class.
58
592. **Remove/restore pattern:** Removing `valueA` and `valueB` prevents picking the same physical element twice when remainder classes coincide (e.g., `remainderA == remainderB`). Restoring them afterward keeps the buckets intact for subsequent iterations.
60
613. **Fixed third remainder:** Once two remainders are chosen, the third is determined by `remainderC = (3 - (remainderA + remainderB) % 3) % 3`, ensuring the sum is divisible by 3.
62
63**A note on correctness:** This approach considers picking only the single largest element per remainder class. It does not always handle cases requiring the **second-largest** within the same class (for example, when three numbers must all come from remainder class 0). A more robust alternative is dynamic programming over remainders:
64
65```java
66// dp[r] = max sum of chosen elements whose total % 3 == r
67int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
68for (int x : nums) {
69    int[] next = dp.clone();
70    for (int r = 0; r < 3; r++) {
71        if (dp[r] != Integer.MIN_VALUE) {
72            int nr = (r + x) % 3;
73            next[nr] = Math.max(next[nr], dp[r] + x);
74        }
75    }
76    dp = next;
77}
78// dp[0] is the answer (0 if no valid subset).
79

1class Solution {
2public:
3    int maximumSum(vector<int>& nums) {
4        // Sort in ascending order so the largest values are at the back of each group
5        sort(nums.begin(), nums.end());
6
7        // Group numbers by their remainder modulo 3
8        // groups[0]: numbers with remainder 0
9        // groups[1]: numbers with remainder 1
10        // groups[2]: numbers with remainder 2
11        vector<vector<int>> groups(3);
12        for (int num : nums) {
13            groups[num % 3].push_back(num);
14        }
15
16        int maxSum = 0;
17
18        // Enumerate the remainder of the first picked number
19        for (int remA = 0; remA < 3; ++remA) {
20            if (groups[remA].empty()) {
21                continue;
22            }
23
24            // Pick the largest number from group remA
25            int valueA = groups[remA].back();
26            groups[remA].pop_back();
27
28            // Enumerate the remainder of the second picked number
29            for (int remB = 0; remB < 3; ++remB) {
30                if (groups[remB].empty()) {
31                    continue;
32                }
33
34                // Pick the largest remaining number from group remB
35                int valueB = groups[remB].back();
36                groups[remB].pop_back();
37
38                // The third remainder must make the total sum divisible by 3
39                int remC = (3 - (remA + remB) % 3) % 3;
40
41                if (!groups[remC].empty()) {
42                    // Pick the largest remaining number from group remC
43                    int valueC = groups[remC].back();
44                    maxSum = max(maxSum, valueA + valueB + valueC);
45                }
46
47                // Restore valueB for the next iteration
48                groups[remB].push_back(valueB);
49            }
50
51            // Restore valueA for the next iteration
52            groups[remA].push_back(valueA);
53        }
54
55        return maxSum;
56    }
57};
58

1/**
2 * Finds the maximum sum of three numbers from the array whose sum is divisible by 3.
3 *
4 * Strategy:
5 *  1. Sort the numbers ascending so the largest values are at the end of each bucket.
6 *  2. Bucket numbers by their remainder modulo 3 (remainders 0, 1, 2).
7 *  3. Try every pair of remainders (a, b); the required third remainder c is the one
8 *     that makes (a + b + c) % 3 === 0. Pick the largest available number from each
9 *     bucket and track the maximum valid sum.
10 *
11 * @param nums - The input array of numbers.
12 * @returns The maximum sum divisible by 3, or 0 if no valid triple exists.
13 */
14function maximumSum(nums: number[]): number {
15    // Sort ascending so larger values are positioned at the end of each bucket.
16    nums.sort((a, b) => a - b);
17
18    // Create three buckets, one for each remainder value (0, 1, 2) modulo 3.
19    const buckets: number[][] = Array.from({ length: 3 }, () => []);
20    for (const value of nums) {
21        buckets[value % 3].push(value);
22    }
23
24    let maxSum = 0;
25
26    // Choose the first number from the bucket with remainder `remainderA`.
27    for (let remainderA = 0; remainderA < 3; remainderA++) {
28        if (buckets[remainderA].length === 0) {
29            continue;
30        }
31
32        // Temporarily remove the largest value from bucket A.
33        const valueA = buckets[remainderA].pop()!;
34
35        // Choose the second number from the bucket with remainder `remainderB`.
36        for (let remainderB = 0; remainderB < 3; remainderB++) {
37            if (buckets[remainderB].length === 0) {
38                continue;
39            }
40
41            // Temporarily remove the largest value from bucket B.
42            const valueB = buckets[remainderB].pop()!;
43
44            // Compute the remainder required for the third number so the total
45            // sum is divisible by 3.
46            const remainderC = (3 - ((remainderA + remainderB) % 3)) % 3;
47
48            // If a candidate exists in bucket C, peek at its largest value.
49            if (buckets[remainderC].length > 0) {
50                const valueC = buckets[remainderC][buckets[remainderC].length - 1];
51                maxSum = Math.max(maxSum, valueA + valueB + valueC);
52            }
53
54            // Restore the value removed from bucket B.
55            buckets[remainderB].push(valueB);
56        }
57
58        // Restore the value removed from bucket A.
59        buckets[remainderA].push(valueA);
60    }
61
62    return maxSum;
63}
64

Time and Space Complexity

Time Complexity: O(n log n)

The analysis proceeds through the main operations:

Sorting: The first step nums.sort() sorts the array, which takes O(n log n) time, where n is the length of the array nums.
Distributing into groups: The loop for x in nums iterates over all elements and places each into one of three buckets based on x % 3. This takes O(n) time in total.
Triple nested traversal: The triple loop over a, b, c runs over the 3 remainder groups. Since a and b each range over only 3 values, this constitutes a constant 3 × 3 = 9 combinations. Within each, operations like pop(), append(), and accessing g[c][-1] are all O(1). Hence this entire block costs O(1) time, independent of n.

The dominant term is the sorting step, so the overall time complexity is O(n log n).

Space Complexity: O(n)

The auxiliary array g consists of three lists that together store all n elements of nums, requiring O(n) extra space. The sorting may also use up to O(log n) or O(n) auxiliary space depending on the implementation. Therefore, the overall space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

WRONG for this problem — picks any-size subset, not exactly 3!

dp = [0, -1, -1] for num in nums: new_dp = dp[:] for remainder in range(3): if dp[remainder] == -1: continue next_remainder = (dp[remainder] + num) % 3 new_dp[next_remainder] = max(new_dp[next_remainder], dp[remainder] + num) dp = new_dp return dp[0] # could be a sum of 5, 10, or 0 elements!


For `nums = [2, 6, 3, 5, 1]`, this DP returns `2+6+3+5+1 = 17` (the whole array sums to 17, but the best divisible-by-3 subset is `6+3+5+1+2 = 17`? actually `2+6+3+5+1=17`, not divisible; the subset answer would be `6+3+5+1=15`). The expected answer for the *triplet* problem is `12`. The two answers differ because the constraint count differs.

**Solution:** Track the **number of elements chosen** as an extra dimension of the DP state, so you only read off the answer when exactly three have been picked.

```python
from typing import List

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        NEG = float('-inf')
        # dp[count][remainder] = max sum using exactly `count` elements
        # with that remainder mod 3.
        dp = [[NEG] * 3 for _ in range(4)]
        dp[0][0] = 0

        for num in nums:
            # Iterate counts in descending order so each num is used once.
            for count in range(2, -1, -1):
                for r in range(3):
                    if dp[count][r] == NEG:
                        continue
                    nr = (r + num) % 3
                    dp[count + 1][nr] = max(dp[count + 1][nr], dp[count][r] + num)

        return dp[3][0] if dp[3][0] != NEG else 0

Pitfall 2: Counting the same element twice in the group approach

When a, b, and c point to the same remainder group, a naive implementation may select the same physical element for two (or three) of the slots. For example, with a = b = c = 0 and groups[0] = [9] (a single element), you might wrongly form a "triplet" 9 + 9 + 9.

# BUGGY: doesn't remove the chosen element before picking again
for a in range(3):
    x = groups[a][-1]          # peek, not pop
    for b in range(3):
        y = groups[b][-1]      # may be the SAME element as x
        c = (3 - (a + b) % 3) % 3
        z = groups[c][-1]      # may reuse x or y again
        answer = max(answer, x + y + z)

Solution: Use pop() to temporarily remove a chosen element so it cannot be reselected, then append() it back afterward — exactly as the faithful rewrite does. This guarantees the three picks are distinct list positions.

first = groups[a].pop()        # remove so b/c can't reuse it
second = groups[b].pop()       # remove so c can't reuse it
c = (3 - (a + b) % 3) % 3
if groups[c]:
    third = groups[c][-1]
    answer = max(answer, first + second + third)
groups[b].append(second)       # restore
groups[a].append(first)        # restore

Pitfall 3: Wrong formula for the third remainder

A subtle arithmetic slip is writing c = (3 - (a + b)) % 3 instead of c = (3 - (a + b) % 3) % 3. When a + b > 3 (e.g., a = 2, b = 2), the inner % 3 is essential.

# WRONG for a=2, b=2: (3 - 4) % 3 = (-1) % 3 = 2  -> works by luck in Python,
# but in languages without floored modulo this gives a negative index.
c = (3 - (a + b)) % 3

# CORRECT and portable:
c = (3 - (a + b) % 3) % 3

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering