Maximize ysum by picking a triplet of distinct xvalues

Array Hash Table Greedy Sorting Heap (Priority Queue)

63.2% acceptance

Feb 25, 2026

You are given two integer arrays x and y of length n. Choose three distinct indices i, j, k such that x[i], x[j], x[k] are all distinct. Maximize y[i]+y[j]+y[k]. Return maximum sum, or -1 if no such triplet exists.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_distinct_triplet(x: Vec<i32>, y: Vec<i32>) -> i32 {
    use std::collections::HashMap;

    // For each distinct x-value, keep the maximum y
    let mut best: HashMap<i32, i32> = HashMap::new();
    for (xi, yi) in x.iter().zip(y.iter()) {
      let e = best.entry(*xi).or_insert(0);
      *e = (*e).max(*yi);
    }

    if best.len() < 3 {
      return -1;
    }

    // Get top 3 y-values from distinct x-values
    let mut vals: Vec<i32> = best.values().cloned().collect();
    vals.sort_unstable_by(|a, b| b.cmp(a));
    vals[0] + vals[1] + vals[2]
  }
}