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.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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] <= 1000At least one potential outlier exists in nums
Hints for Identify the Largest Outlier in an Array
Hint 1
Let
Sbe the total of the array. Ifxis the outlier andythe sum element, the specials add up toS - x - y, and they must also add up toy.Hint 2
So
xis a valid outlier exactly whenS - x = 2yfor some other elementy.Hint 3
Try every element as
x:y = (S - x) / 2must be an integer present in the array — and ify == 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
- Compute the total
Sand count how many times each value occurs. - For each element
x: ifS - xis odd, skip it. Otherwise lety = (S - x) / 2. xis a valid outlier ifyoccurs at least once wheny != x, or at least twice wheny == x.- 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
ymust be a different index fromx: withy == 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. ycan 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 bestJava
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