Identify the largest outlier in an array

Array Hash Table Counting Enumeration

36.2% acceptance

Feb 24, 2026

225

You are given an integer array nums. This array contains n elements, where exactly n - 2 elements are special numbers. One of the remaining two elements is the sum of these special numbers, and the other is an outlier. An outlier is defined as a number that is neither one of the original special numbers nor the element representing the sum of those numbers. Note that special numbers, the sum element, and the outlier must have distinct indices, but may share the same value. Return the largest potential outlier in nums.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn get_largest_outlier(nums: Vec<i32>) -> i32 {
    // total = sum of all nums
    // If outlier = nums[i], then remaining sum = total - nums[i]
    // = sum_special + sum_special = 2 * sum_special (wait no)
    // Actually: total = sum_special + sum_val + outlier
    // where sum_val = sum_special (they're equal)
    // => total = 2 * sum_special + outlier
    // => sum_special = (total - outlier) / 2
    // For nums[i] to be outlier: (total - nums[i]) must be even
    // and (total - nums[i]) / 2 must exist as a value in nums at some index j != i
    
    let total: i32 = nums.iter().sum();
    let mut cnt: HashMap<i32, i32> = HashMap::new();
    for &x in &nums { *cnt.entry(x).or_insert(0) += 1; }
    
    let mut ans = i32::MIN;
    for (i, &v) in nums.iter().enumerate() {
      let _ = i;
      let rem = total - v;
      if rem % 2 != 0 { continue; }
      let need = rem / 2;
      // Check if 'need' exists in nums at some index != i (current outlier candidate)
      let cnt_need = *cnt.get(&need).unwrap_or(&0);
      let available = if need == v { cnt_need - 1 } else { cnt_need };
      if available > 0 {
        ans = ans.max(v);
      }
    }
    ans
  }
}