# Identify the Largest Outlier in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/identify-the-largest-outlier-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/identify-the-largest-outlier-in-an-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
---
## Problem
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] <= 1000`
* The input is generated such that at least **one** potential outlier exists in `nums`.

# Approaches
## Brute-Force Approach
This approach directly translates the problem definition into a search. We consider every possible pair of elements `(nums[i], nums[j])` from the array. For each pair, we hypothesize that `nums[i]` is the sum of special numbers and `nums[j]` is the outlier. The remaining `n-2` numbers are then the special numbers. We verify if this hypothesis is valid by checking if the sum of these `n-2` numbers indeed equals `nums[i]`. This is the most straightforward but also the least efficient method.
**Time:** O(n^2) - Two nested loops iterate through the array of size `n`, leading to a quadratic time complexity. This is too slow for the given constraints where `n` can be up to 10^5. · **Space:** O(1) - Constant extra space is used, only for variables to store the total sum and the maximum outlier found.
**Pros:** Simple to understand and implement directly from the problem statement.; Requires no extra space, making it very memory efficient.
**Cons:** Highly inefficient for large arrays due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms with typical time constraints for the given input size.
### Explanation
The core of this method lies in exploring all possibilities. Given `n` numbers, we need to identify two special roles: the 'sum' and the 'outlier'. We can iterate through every element `nums[i]` and propose it as the 'sum'. Then, for each such proposal, we iterate through every other element `nums[j]` and propose it as the 'outlier'. With these two roles assigned, the remaining `n-2` elements are assumed to be the 'special numbers'.

The validation step is based on the relationship `sum(all_elements) = sum(special_numbers) + sum_element + outlier_element`. Since we assume `sum(special_numbers) = sum_element`, this simplifies to `sum(all_elements) = 2 * sum_element + outlier_element`. We first pre-calculate the total sum of the array. Then, for each pair `(nums[i], nums[j])`, we check if `totalSum == 2 * nums[i] + nums[j]`. If this equation holds, we've found a valid scenario where `nums[j]` is an outlier. We keep track of the largest such `nums[j]` found.

```java
class Solution {
    public int findLargestOutlier(int[] nums) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int maxOutlier = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                // Assume nums[i] is the sum and nums[j] is the outlier
                // The sum of special numbers would be totalSum - nums[i] - nums[j]
                // Check if this equals nums[i]
                if (totalSum - nums[i] - nums[j] == (long)nums[i]) {
                    maxOutlier = Math.max(maxOutlier, nums[j]);
                }
            }
        }
        return maxOutlier;
    }
}
```
### Algorithm
1. Calculate the total sum of all elements in the array, `totalSum`.
2. Initialize a variable `maxOutlier` to the smallest possible integer value.
3. Use two nested loops to iterate through all distinct pairs of indices `(i, j)`.
4. For each pair, assume `nums[i]` is the sum element and `nums[j]` is the outlier.
5. The sum of the `n-2` special numbers is `totalSum - nums[i] - nums[j]`.
6. Check if this calculated sum of special numbers equals the assumed sum element `nums[i]`. The condition is `totalSum - nums[i] - nums[j] == nums[i]`, which simplifies to `totalSum == 2 * nums[i] + nums[j]`.
7. If the condition holds true, `nums[j]` is a valid potential outlier. Update `maxOutlier` by taking the maximum of its current value and `nums[j]`.
8. After iterating through all pairs, `maxOutlier` will contain the largest possible outlier value.

## Sorting and Binary Search
This approach improves upon the brute-force method by optimizing the search for the outlier candidate. The key insight is that if we fix a potential 'sum' element, the value of the corresponding 'outlier' is determined. By first sorting the array, we can use the much faster binary search algorithm (`O(log n)`) to check for the existence of this required outlier, instead of a linear scan (`O(n)`).
**Time:** O(n log n) - The dominant operation is sorting the array. The subsequent loop runs `n` times, with each iteration performing a binary search (`O(log n)`), resulting in a total time of `O(n log n)` for the search phase as well. · **Space:** O(log n) or O(n) - This depends on the sorting algorithm's implementation. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which has an average space complexity of `O(log n)` for the recursion stack.
**Pros:** Significantly more efficient than the brute-force approach for large `n`.; Generally uses less memory than the hash map approach.
**Cons:** Slower than the optimal linear time solution.; The logic to handle cases where the sum and outlier have the same value requires careful implementation.
### Explanation
The foundation of this approach is the same algebraic relationship: `outlier = totalSum - 2 * sum`. The improvement comes from optimizing the search. After an initial `O(n log n)` sort, we can find elements much more quickly.

We iterate through each element `nums[i]` of the now-sorted array, treating it as the candidate for the sum. We calculate the `outlierCandidate` value. Then, we perform a binary search on the entire sorted array to see if this value exists. 

A crucial detail is handling the requirement that the sum and outlier must be at distinct indices. 
- If `sumCandidate` and `outlierCandidate` are different values, their existence in the array guarantees they come from different positions.
- If they are the same value, we need to ensure the array contains at least two copies of that value. Since the array is sorted, we can easily check this by looking at the immediate neighbors (`nums[i-1]` or `nums[i+1]`) of the current element `nums[i]`.

If a valid configuration is found, we update our `maxOutlier`.

```java
import java.util.Arrays;

class Solution {
    public int findLargestOutlier(int[] nums) {
        Arrays.sort(nums);
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int maxOutlier = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            long sumCandidate = nums[i];
            long outlierCandidateValue = totalSum - 2 * sumCandidate;

            // We need to cast to int for binary search as nums is an int array
            if (outlierCandidateValue < Integer.MIN_VALUE || outlierCandidateValue > Integer.MAX_VALUE) {
                continue;
            }
            int outlierCandidate = (int)outlierCandidateValue;

            int searchIndex = Arrays.binarySearch(nums, outlierCandidate);

            if (searchIndex >= 0) {
                // A potential outlier is found. Check if it's a valid scenario.
                if (outlierCandidate != sumCandidate) {
                    // Different values, so they must be at different indices. Valid.
                    maxOutlier = Math.max(maxOutlier, outlierCandidate);
                } else { // outlierCandidate == sumCandidate
                    // Same value, need at least two instances.
                    // Check neighbors of nums[i] since the array is sorted.
                    if ((i > 0 && nums[i - 1] == nums[i]) || (i < nums.length - 1 && nums[i + 1] == nums[i])) {
                        maxOutlier = Math.max(maxOutlier, outlierCandidate);
                    }
                }
            }
        }
        return maxOutlier;
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. Calculate the `totalSum` of all elements in `nums`.
3. Initialize `maxOutlier` to a very small number.
4. Iterate through the sorted array with an index `i`. For each `nums[i]`, consider it as the potential sum element (`sumCandidate`).
5. Calculate the required value for the outlier: `outlierCandidate = totalSum - 2 * sumCandidate`.
6. Use binary search to find if `outlierCandidate` exists in the sorted array `nums`.
7. If `outlierCandidate` is found, we must ensure it corresponds to a distinct element. 
   - If `outlierCandidate` has a different value than `sumCandidate`, any found instance is valid.
   - If `outlierCandidate` has the same value as `sumCandidate`, we must verify that there are at least two instances of this value in the array. Since the array is sorted, this can be checked by looking at the neighbors of `nums[i]`.
8. If a valid scenario is confirmed, update `maxOutlier = max(maxOutlier, outlierCandidate)`.
9. Return `maxOutlier` after the loop.

## Optimal Approach with Hash Map
This is the most efficient approach, achieving a linear time complexity. It uses a hash map to store the frequency of each number in the array. This allows for constant-time (`O(1)`) lookups to check for the existence of the required outlier candidate, avoiding the `O(n)` or `O(log n)` search time of the previous approaches.
**Time:** O(n) - There are two main passes over the data. The first pass to build the sum and frequency map takes `O(n)`. The second pass iterates over the unique keys of the map (at most `n` keys), with `O(1)` operations inside. The total time is linear. · **Space:** O(k) or O(n) - Where `k` is the number of unique elements in `nums`. In the worst case, all `n` elements are unique, leading to `O(n)` space complexity for the hash map.
**Pros:** Optimal time complexity of O(n).; The logic is clean and directly implements the core idea once the frequency map is built.
**Cons:** Uses extra space to store the frequency map, which can be up to O(n) in the worst case.
### Explanation
This optimal solution relies on the same algebraic formula, `outlier = totalSum - 2 * sum`, but streamlines the search process dramatically. 

First, we invest `O(n)` time to make one pass through the array. During this pass, we compute the `totalSum` and build a frequency map (a hash map that maps each number to its number of occurrences). This map is the key to the efficiency of this approach.

Next, we iterate through the unique numbers of the array (which are the keys of our map). For each unique number, we consider it the `sumCandidate`. We calculate the `outlierCandidate`'s value. Instead of searching the array, we perform a quick `O(1)` lookup in our frequency map.

- If `sumCandidate` and `outlierCandidate` are different values, we just need to check if `outlierCandidate` is a key in our map. 
- If they are the same value, we need to ensure we have at least two of them, which we can verify by checking if `map.get(sumCandidate) >= 2`.

If the map confirms a valid scenario, we update our `maxOutlier`. This process avoids any nested loops or expensive sorting operations, leading to a linear time solution.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findLargestOutlier(int[] nums) {
        long totalSum = 0;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            totalSum += num;
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int maxOutlier = Integer.MIN_VALUE;

        for (int sumCandidate : counts.keySet()) {
            long outlierCandidateValue = totalSum - 2 * (long)sumCandidate;
            
            if (outlierCandidateValue < Integer.MIN_VALUE || outlierCandidateValue > Integer.MAX_VALUE) {
                continue;
            }
            int outlierCandidate = (int)outlierCandidateValue;

            if (counts.containsKey(outlierCandidate)) {
                boolean isValid = false;
                if (outlierCandidate == sumCandidate) {
                    // If sum and outlier are the same value, we need at least two.
                    if (counts.get(sumCandidate) >= 2) {
                        isValid = true;
                    }
                } else {
                    // If they are different values, we just need them to exist.
                    isValid = true;
                }

                if (isValid) {
                    maxOutlier = Math.max(maxOutlier, outlierCandidate);
                }
            }
        }
        return maxOutlier;
    }
}
```
### Algorithm
1. Iterate through the array `nums` once to calculate the `totalSum` and to populate a frequency map (e.g., a `HashMap`) with the counts of each number.
2. Initialize `maxOutlier` to a very small number.
3. Iterate through each unique number (`sumCandidate`) in the keys of the frequency map.
4. For each `sumCandidate`, calculate the required `outlierCandidate = totalSum - 2 * sumCandidate`.
5. Use the frequency map to check if `outlierCandidate` exists in the original array.
   - If `outlierCandidate` is the same as `sumCandidate`, check if its count in the map is 2 or more.
   - If `outlierCandidate` is different from `sumCandidate`, simply check if it exists as a key in the map.
6. If the existence check passes, it confirms a valid scenario. Update `maxOutlier = max(maxOutlier, outlierCandidate)`.
7. After checking all unique numbers as potential sums, return `maxOutlier`.

# Solutions
### Java

```java
class Solution {
public
  int getLargestOutlier(int[] nums) {
    int s = 0;
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      s += x;
      cnt.merge(x, 1, Integer : : sum);
    }
    int ans = Integer.MIN_VALUE;
    for (var e : cnt.entrySet()) {
      int x = e.getKey(), v = e.getValue();
      int t = s - x;
      if (t % 2 != 0 || !cnt.containsKey(t / 2)) {
        continue;
      }
      if (x != t / 2 || v > 1) {
        ans = Math.max(ans, x);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getLargestOutlier(vector<int> &nums) {
    int s = 0;
    unordered_map<int, int> cnt;
    for (int x : nums) {
      s += x;
      cnt[x]++;
    }
    int ans = INT_MIN;
    for (auto [x, v] : cnt) {
      int t = s - x;
      if (t % 2 || !cnt.contains(t / 2)) {
        continue;
      }
      if (x != t / 2 || v > 1) {
        ans = max(ans, x);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int: s = sum(nums) cnt = Counter(nums) ans = - inf for x, v in cnt . items(): t = s - x if t % 2 or cnt[t // 2] == 0: continue if x != t // 2 or v > 1: ans = max(ans, x) return ans

```