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.
Example 1:
Input: nums = [2,3,5,10]
Output: 10
Explanation:
The special numbers could be 2 and 3, thus making their sum 5 and the outlier 10.
Example 2:
Input: nums = [-2,-1,-3,-6,4]
Output: 4
Explanation:
The special numbers could be -2, -1, and -3, thus making their sum -6 and the outlier 4.
Example 3:
Input: nums = [1,1,1,1,1,5,5]
Output: 5
Explanation:
The special numbers could be 1, 1, 1, 1, and 1, thus making their sum 5 and the other 5 as the outlier.
Constraints:
3 <= nums.length <= 105-1000 <= nums[i] <= 1000nums.In #3371 Identify the Largest Outlier in an Array, the key observation is that most elements follow a specific relationship: the array contains several normal numbers, one number representing the sum of those numbers, and one extra value that acts as the outlier. The task is to determine which value could be the largest possible outlier.
A practical strategy is to compute the total sum of the array and iterate through each element as a potential outlier candidate. If a value is treated as the outlier, the remaining elements must contain a number equal to half of the remaining sum (representing the stored total of the valid numbers). Using a hash map or frequency map helps efficiently verify whether this expected sum element exists while handling duplicates correctly.
This reduces the search to simple arithmetic checks combined with fast lookups. The main idea is validating the structural relationship between elements rather than brute‑forcing combinations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Sum Validation | O(n) | O(n) |
| Sorting + Iteration | O(n log n) | O(1) or O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
What will be the value of array sum if we remove the outlier from it?
Use hashmap to find occurrence of an element quickly.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
The total sum helps derive relationships between the outlier, the element representing the sum of valid numbers, and the remaining values. By subtracting a candidate outlier from the total, you can determine what the expected sum element should be.
Problems like this are common in technical interviews because they test reasoning with sums, hash maps, and edge cases. While the exact question may vary, similar array validation and hashing patterns frequently appear in FAANG-style interviews.
A hash map (or frequency map) is the most useful data structure for this problem. It allows constant-time lookups to verify whether the expected sum element exists while correctly handling duplicate values.
The optimal approach calculates the total sum of the array and treats each element as a potential outlier. Using a hash map, you check whether the remaining elements contain a value equal to half of the remaining sum. This validation allows the correct outlier to be identified efficiently in linear time.