Hash Table, Math, Prefix Sum O(n)
IntuitionThe problem hints that the array consists of:
n - 2 special numbers
1 sum element, which is the sum of the special numbers
1 outlier
Let’s call the tot
# Intuition
The problem hints that the array consists of:
- `n - 2` special numbers
- 1 sum element, which is the sum of the special numbers
- 1 outlier

Let’s call the total sum of the array `total_sum`. Let `s` be the sum of the special numbers, and let `x` be the outlier.

Then by the structure of the array:  
`total_sum = s + x + s = 2s + x`  
Thus, rearranged:  
`x = total_sum - 2s`

The key idea is that we iterate through all numbers as potential outliers `x`, subtract `x` from the total sum to get `2s`, and check if `2s` is even. If it is, `s = (total_sum - x) // 2`, and we check if `s` exists in the array.

# Approach
1. Compute the total sum of the array.
2. Use a `Counter` to store the frequency of each number in the array for fast lookups.
3. Iterate through each number as a potential outlier `x`.
    - Subtract `x` from `total_sum`, and check if the result is even.
    - If it is, check if `s = (total_sum - x) // 2` exists in the frequency map.
    - Be careful about the case where `x == s`: we need at least two occurrences in the array.
4. Track the maximum valid outlier.

# Complexity
- Time complexity:  
  $$O(n)$$ — One pass to compute sum, one pass through unique elements, and constant time dictionary lookups.

- Space complexity:  
  $$O(n)$$ — For the frequency map.

# Code
```python []
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        count = Counter(nums)
        max_outlier = float('-inf')

        for x in count:
            remaining = total_sum - x
            if remaining % 2 != 0:
                continue
            s = remaining // 2
            if s in count:
                # Ensure s and x are from different indices
                if s != x or count[x] > 1:
                    max_outlier = max(max_outlier, x)

        return max_outlier

['Array', 'Hash Table', 'Counting', 'Python3']