Is Maximum Sum of Three Numbers Divisible by Three easy or hard?

This problem is typically rated Medium because the brute force solution is obvious but inefficient. The challenge is recognizing the modular arithmetic property that determines which remainder combinations produce a sum divisible by three.

Maximum Sum of Three Numbers Divisible by Three Python/Java solution

The standard implementation sorts the array, groups numbers by remainder (num % 3), and evaluates valid combinations such as (0,0,0) or (0,1,2). This logic is straightforward to implement in Python, Java, C++, Go, or TypeScript with O(n log n) time complexity.

How to solve Maximum Sum of Three Numbers Divisible by Three in O(n)?

An O(n) strategy is possible if you only track the top few values in each remainder group instead of sorting the entire array. Maintain the largest candidates for remainder 0, 1, and 2 while scanning the array once. Then evaluate the valid remainder combinations to compute the maximum divisible sum.

What is the best approach for Maximum Sum of Three Numbers Divisible by Three?

The most practical approach is sorting the array and grouping numbers by their remainder modulo 3. Valid combinations are (0,0,0), (1,1,1), (2,2,2), and (0,1,2). After sorting, choose the largest numbers from the required groups to maximize the sum. This solution runs in O(n log n) time and O(n) space.

Is Maximum Sum of Three Numbers Divisible by Three asked at Google/Amazon/Meta?

Problems involving modular arithmetic, greedy selection, and triplet combinations frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test recognizing remainder patterns and optimizing beyond brute force enumeration.

What data structure is used in Maximum Sum of Three Numbers Divisible by Three?

Common implementations use arrays or lists to group numbers by remainder modulo 3. Some solutions also use a max heap (priority queue) to efficiently retrieve the largest values from each group. Sorting is another common technique to simplify selection.

What is the time complexity of Maximum Sum of Three Numbers Divisible by Three?

The brute force approach checks every triplet and takes O(n^3) time. The optimized solution sorts the array and groups numbers by remainder, giving O(n log n) time due to sorting and O(n) additional space. Heap-based implementations also run in O(n log n).

Description Hints 4 Solution Video 13:45

3780. Maximum Sum of Three Numbers Divisible by Three

Medium46.7% acceptance1 company

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 1:

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

Output: 9

Explanation:

The valid triplets whose sum is divisible by 3 are:

(4, 2, 3) with a sum of 4 + 2 + 3 = 9.
(2, 3, 1) with a sum of 2 + 3 + 1 = 6.

Thus, the answer is 9.

Example 2:

Input: nums = [2,1,5]

Output: 0

Explanation:

No triplet forms a sum divisible by 3, so the answer is 0.

Constraints:

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Split numbers into groups by x % 3.

Hint 2

Only four valid combinations for sum % 3 == 0.

Hint 3

Possible combinations are 0 + 0 + 0, 1 + 1 + 1, 2 + 2 + 2, 0 + 1 + 2.

Hint 4

Sort groups descending, try each combo using top values.

13:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumSum(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[4,2,3,1]

Input

[2,1,5]

Your code is saved on this device.Solution