Maximum Sum of Three Numbers Divisible by Three - Solution & Explanation

Problem 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.