Two pass solution, O(N) time and space
IntuitionApproachComplexity
Time complexity: O(N)

Space complexity: O(N)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
# exactly n - 2 elements are special numbers. One of the remaining two elements is the sum of these special numbers
# therefore in nums there exist sum(sublist) = s
# for a valid outlier "o" to exist
# sum(nums)-o = 2s
# where s is a number in nums

# calculate the sum of nums
# count the frequency of each digit in nums
# iterate over nums
# consider x as the outlier
# decrease the count of x in the freq_map (we want to exclude the outlier from calculating is s in valid)
# subtract x from the total
# check if total is an even number and that total//2 exists in the frequency map
# if true then update soln to max(soln, x)
# increase the count of x again
# return soln

# T: O(N)
# S: O(N)
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        total = sum(nums)
        counts = Counter(nums)
        outlier = float('-inf')
        for candidate in counts:
            curr_sum = total - candidate # curr_sum = 2s if candidate is an outlier
            counts[candidate] -= 1
            if curr_sum % 2 == 0 and counts[curr_sum//2] > 0:
                outlier = max(outlier, candidate)
            counts[candidate] += 1
        return outlier
```
['Python3']