Identify the Largest Outlier in an Array

Medium
1822.

Identify the Largest Outlier in an Array

Identify the Largest Outlier in an Array is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

You are given an array nums of n integers. Exactly n - 2 of its elements are special numbers. Of the two remaining elements, one is the sum of all the special numbers, and the other is an outlier — a number that is neither special nor that sum.

The special numbers, the sum element and the outlier sit at distinct indices, but they may share values.

Return the largest value that could be the outlier. The input is guaranteed to admit at least one valid split.

Example 1

Input
nums = [4,1,5,12]
Output
12
Explanation
`4` and `1` are special, `5` is their sum, and `12` is the outlier.

Example 2

Input
nums = [-1,-2,-3,-6,5]
Output
5
Explanation
`-1`, `-2`, `-3` are special and sum to `-6`; `5` is the outlier.

Example 3

Input
nums = [2,2,2,2,8,8]
Output
8
Explanation
The four `2`s are special with sum `8`; the other `8` is the outlier.

Constraints

  • 3 <= nums.length <= 10^5
  • -1000 <= nums[i] <= 1000
  • At least one potential outlier exists in nums
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var getLargestOutlier = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Identify the Largest Outlier in an Array — Solution

Identify the Largest Outlier in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Identify the Largest Outlier in an Array is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of n integers. Exactly n - 2 of its elements are special numbers. Of the two remaining elements, one is the sum of all the special numbers, and the other is an outlier — a number that is neither special nor that sum.

The special numbers, the sum element and the outlier sit at distinct indices, but they may share values.

Return the largest value that could be the outlier. The input is guaranteed to admit at least one valid split.

Example 1

Input: nums = [4,1,5,12]
Output: 12
Explanation: `4` and `1` are special, `5` is their sum, and `12` is the outlier.

Example 2

Input: nums = [-1,-2,-3,-6,5]
Output: 5
Explanation: `-1`, `-2`, `-3` are special and sum to `-6`; `5` is the outlier.

Example 3

Input: nums = [2,2,2,2,8,8]
Output: 8
Explanation: The four `2`s are special with sum `8`; the other `8` is the outlier.

Constraints

  • 3 <= nums.length <= 10^5
  • -1000 <= nums[i] <= 1000
  • At least one potential outlier exists in nums

Hints for Identify the Largest Outlier in an Array

  1. Hint 1

    Let S be the total of the array. If x is the outlier and y the sum element, the specials add up to S - x - y, and they must also add up to y.

  2. Hint 2

    So x is a valid outlier exactly when S - x = 2y for some other element y.

  3. Hint 3

    Try every element as x: y = (S - x) / 2 must be an integer present in the array — and if y == x, it must appear at least twice. A count table answers that in O(1).

How to solve Identify the Largest Outlier in an Array

Removing the outlier x leaves the specials plus their sum y, which total 2y. So x works exactly when S - x is even and (S - x) / 2 occurs at some index other than x's own.

Approach

  1. Compute the total S and count how many times each value occurs.
  2. For each element x: if S - x is odd, skip it. Otherwise let y = (S - x) / 2.
  3. x is a valid outlier if y occurs at least once when y != x, or at least twice when y == x.
  4. Return the largest valid x.

Why it works

If x is the outlier and y the sum, the array total is specials + y + x = y + y + x, so S - x = 2y. Conversely, if some other index holds y = (S - x) / 2, then the remaining n - 2 elements add up to S - x - y = y, so they are a valid set of specials with y as their sum and x as the outlier.

Complexity

  • Time — O(n)
  • Space — O(V) for the counts, V = 2001 possible values

Pitfalls

  • y must be a different index from x: with y == x, one copy is not enough.
  • Values are negative too — test parity with % 2 != 0, not % 2 == 1, which misses negative odd numbers in most languages.
  • y can fall outside [-1000, 1000]; guard the count lookup.

Reference solution

Python

from typing import List
from collections import Counter

def getLargestOutlier(nums: List[int]) -> int:
    total = sum(nums)
    count = Counter(nums)
    best = None
    for x in nums:
        rest = total - x
        if rest % 2 != 0:
            continue
        y = rest // 2
        need = 2 if y == x else 1
        if count.get(y, 0) >= need and (best is None or x > best):
            best = x
    return best

Java

public static int getLargestOutlier(int[] nums) {
    int total = 0;
    int[] count = new int[2001];
    for (int v : nums) {
        total += v;
        count[v + 1000]++;
    }
    int best = Integer.MIN_VALUE;
    for (int x : nums) {
        int rest = total - x;
        if (rest % 2 != 0) continue;
        int y = rest / 2;
        if (y < -1000 || y > 1000) continue;
        int need = y == x ? 2 : 1;
        if (count[y + 1000] >= need) best = Math.max(best, x);
    }
    return best;
}

C++

int getLargestOutlier(vector<int>& nums) {
    int total = 0;
    vector<int> count(2001, 0);
    for (int v : nums) {
        total += v;
        count[v + 1000]++;
    }
    int best = INT_MIN;
    for (int x : nums) {
        int rest = total - x;
        if (rest % 2 != 0) continue;
        int y = rest / 2;
        if (y < -1000 || y > 1000) continue;
        int need = y == x ? 2 : 1;
        if (count[y + 1000] >= need) best = max(best, x);
    }
    return best;
}

JavaScript

var getLargestOutlier = function(nums) {
    var total = 0;
    var count = new Array(2001).fill(0);
    for (var i = 0; i < nums.length; i++) {
        total += nums[i];
        count[nums[i] + 1000]++;
    }
    var best = -Infinity;
    for (var j = 0; j < nums.length; j++) {
        var x = nums[j], rest = total - x;
        if (rest % 2 !== 0) continue;
        var y = rest / 2;
        if (y < -1000 || y > 1000) continue;
        var need = y === x ? 2 : 1;
        if (count[y + 1000] >= need && x > best) best = x;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets