Watch 7 video solutions for Maximum Sum of Three Numbers Divisible by Three, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Study Placement has 418 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i] <= 105Problem Overview: Given an integer array, pick exactly three numbers whose total sum is divisible by 3. Among all valid triplets, return the maximum possible sum. If no such combination exists, return -1 or the defined failure value depending on the implementation.
Approach 1: Brute Force Triplets (O(n^3) time, O(1) space)
The most direct method checks every possible combination of three elements. Use three nested loops and compute nums[i] + nums[j] + nums[k] for all unique triplets. For each sum, verify whether sum % 3 == 0 and track the maximum valid value. This approach guarantees correctness but becomes impractical when n grows because it evaluates O(n^3) combinations. It’s useful only for understanding the problem constraints or validating optimized solutions.
Approach 2: Sorting + Grouping + Enumeration (O(n log n) time, O(n) space)
This is the practical solution used in most implementations. First sort the array in descending order using techniques from sorting. Then group numbers based on their remainder when divided by 3 (num % 3). The key observation: a sum of three numbers is divisible by 3 when their remainders form one of these combinations: (0,0,0), (1,1,1), (2,2,2), or (0,1,2).
After grouping, enumerate valid remainder combinations and compute the best possible sum using the largest elements from each group. Because the array is sorted, you always pull the highest values first. This reduces the search space dramatically while still guaranteeing the optimal result. The technique combines ideas from array manipulation and simple greedy selection.
Approach 3: Priority Queue by Remainder Groups (O(n log n) time, O(n) space)
Instead of sorting the entire array, push numbers into three max-heaps based on their remainder (0, 1, 2). Heaps allow efficient retrieval of the largest elements in each group. Then evaluate the same valid remainder patterns (0+0+0, 1+1+1, 2+2+2, 0+1+2) by popping the top values from the appropriate heaps. This approach uses a heap (priority queue) to avoid full sorting, though the asymptotic complexity remains similar.
Recommended for interviews: The sorting + grouping strategy is usually the expected answer. Interviewers want to see whether you recognize the remainder pattern that determines divisibility by 3. Starting with the brute force solution demonstrates baseline reasoning, but the grouped greedy approach shows stronger algorithmic insight and clean implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplets | O(n^3) | O(1) | Useful for small arrays or verifying correctness of optimized solutions |
| Sorting + Grouping + Enumeration | O(n log n) | O(n) | Best general solution; simple logic with reliable performance |
| Remainder Groups with Max Heap | O(n log n) | O(n) | When you want quick access to largest elements without sorting the entire array |