Maximum sum of three numbers divisible by three

Array Greedy Sorting Heap (Priority Queue)

47.7% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_sum(nums: Vec<i32>) -> i32 {
    // Group by residue mod 3, keep top 3
    let mut groups = [Vec::new(), Vec::new(), Vec::new()];
    for &x in &nums {
      groups[(x % 3) as usize].push(x);
    }
    for g in &mut groups { g.sort_unstable_by(|a, b| b.cmp(a)); g.truncate(3); }
    let top = |g: &Vec<i32>, n: usize| -> i32 { g[..g.len().min(n)].iter().sum() };
    let mut best = 0i32;
    // (0,0,0)
    if groups[0].len() >= 3 { best = best.max(top(&groups[0], 3)); }
    // (1,1,1)
    if groups[1].len() >= 3 { best = best.max(top(&groups[1], 3)); }
    // (2,2,2)
    if groups[2].len() >= 3 { best = best.max(top(&groups[2], 3)); }
    // (0,1,2)
    if !groups[0].is_empty() && !groups[1].is_empty() && !groups[2].is_empty() {
      best = best.max(groups[0][0] + groups[1][0] + groups[2][0]);
    }
    best
  }
}