Optimized Brute-Force + Counting that beats 95%. Mathematical Intuitive Explanation
IntuitionIn this problem, we have array nums sized n with:
an element is outlier
an element is sum of another n-2 elements, excluding itself and outlier.
n-2 "o
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

In this problem, we have array `nums` sized `n` with:
- an element is outlier
- an element is sum of another `n-2` elements, excluding itself and outlier.
- `n-2` "ordinary" elements.
- Every elements/index can have exactly a role from the 3 roles above.

The highest `n` possible here is $$10^5$$, so if we do brute-force on `nums` directly, it will lead to Time-Limit Exceeded.

On the other hand, the `nums[i]` is bounded at `[-1000, 1000]`. Thus, we can use **hash map / hash table** to store counts and brute-force is safe since the search space is at most `2001`.

# Approach 1 : Brute-Force + Hash Map
<!-- Describe your approach to solving the problem. -->

We use brute-force on unique keys (`nums[i]`) to search for the outlier.

Let's say we have `nums[i] = [a, b, c, d ,e]`, where `e` is outlier and `d` is sum of other 3 elements: `a + b + c`.

Let `sumAll` be the sum of all elements in the `nums`. 
```
sumAll = a + b + c + d + e
```

We know that `d = a + b + c`, thus:
```
sumAll = d + d + e
```

In another form:
```
2d = (sumAll - e)
```

Therefore, we can brute-force on `e` that is having possible `d` in the nums.

However, there can be a case when `d` equals `e`. In this case, we need to ensure that they are on different indexes, or its **occurences count** is more than 1.

## Algorithm

1. Create a hashmap to store counts of `nums[i]`.
2. Count occurences for every unique `nums[i]`.
3. Count the sum of all elements in `nums`. Let's call it `sumAll`
4. Let `ans` be our variable to store the answer, set it to any number lower than `-1000` (the lowest `nums[i]` can have)
5. For each `key` in the hashmap (Let `key` be our current outlier guess):
    - If current `key` is less than or equal to the current answer, skip it (**continue**).
    - If there's exist `d = (sumAll - key) / 2`\* in the hashmap :
        -  If `d` isn't equal to `key` **or** the occurence count of `d` is more than 1, then update the `ans` to `key`.
6. Return `ans`


> \*) If we create a hashmap of integer, additional check of `2d = sumAll - key` is required to prevent false `d` that leads to wrong answer.

## Complexity

Let $$N$$ be size of `nums` and $$M$$ be number of varying unique elements in `nums`

- Time complexity: $$O(M + N)$$
    We loop entire `nums` at least once, and may need to loop entire $$M$$ elements in the hashmap.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(M)$$
    This is for the hashmap storing occurence counts of elements in nums.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->


## Code
```cpp []
class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        unordered_map<int, int> m;
        int sumAll = 0;
        for(int x : nums){
            m[x]++; // Count Occurence
            sumAll += x; // Count sumAll
        }
        int ans = -10000;

        // Brute-force on key.
        // key is it->first here.
        for(auto it=m.begin(); it!=m.end(); it++) {
            if(it->first <= ans) continue; // skip

            // Find the d
            auto it1 = m.find((sumAll - it->first) / 2);
            // Additional check on d
            if(it1 != m.end() && it1->first * 2 == sumAll - it->first) {
                // Final check to qualify as outlier
                if(it1->first != it->first || it1->second > 1)
                    ans = it->first;
            }
        }
        return ans;
    }
};
```
['Greedy', 'Counting', 'C++']