Python Easy Solution. O(N) Time Complexity.
Intuition
total_sum = sum of (n-2) elements + outlier + special number.
It is given that, sum(n-2) elements = special number.
So, total_sum - outlier =  sum(n-2
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- **total_sum = sum of (n-2) elements + outlier + special number.**
- It is given that, **sum(n-2) elements = special number.**
- So, **total_sum - outlier =  sum(n-2) elements + special number.**
- This implies that,  **total_sum - outlier = 2 * special number.**
- Which means that **special number = (total_sum - outlier)/ 2**

# Approach
<!-- Describe your approach to solving the problem. -->
1. We calculate the sum of array and declare max_outlier = -inf.
2. Create a frequency map of all elements.
3. The idea is that, for every ith element of the array, we treat the number as an outlier and check if the above theorem of finding special number is true. 
4. If the theorem is proven, then we check if the special number is existing in freq dict or not and then update max_outlier. 
5. Whenever considering an element  as outlier, make sure to reduce its count before checking for special number in freq dict because, we must not take the currrent outlier into account when checking for special number.
6. Once max_outlier is updated, make sure to put back the current outlier into freq dict, so that it can be used by other elements.

# Complexity
- Time complexity: $$O(n)$$

# Code
```python3 []
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = sum(nums)
        max_outlier = -inf
        freq_dict = {}
        for i in range(n):
            key = nums[i]
            if nums[i] in freq_dict:
                freq_dict[key] += 1
            else:
                freq_dict[key] = 1

        for i in range(n):
            current_outlier = nums[i]
            required_sum = total_sum - current_outlier
            if required_sum % 2 != 0:
                continue
            freq_dict[current_outlier] -= 1
            spl_number = required_sum // 2
            if (spl_number) in freq_dict and freq_dict[spl_number] != 0:
                max_outlier = max(max_outlier, current_outlier)
            freq_dict[current_outlier] += 1

        return max_outlier

```
['Array', 'Hash Table', 'Counting', 'Enumeration', 'Python', 'Python3']