Beats 100%...Freq Array!!
IntuitionAt first glance, the problem seems to be about identifying an outlier in the array where one of the numbers is the sum of the special numbers in the ar
# Intuition
At first glance, the problem seems to be about identifying an outlier in the array where one of the numbers is the sum of the special numbers in the array, and the other is the actual outlier. Our primary challenge is efficiently identifying the largest outlier from the given array, leveraging the constraints that one element is the sum of the special numbers, and the other is an outlier.

# Approach
1. Frequency Array: We will use a frequency array to count how often each number appears in the array. Since the values in the array can be negative, we'll use an offset (1000 in this case) to make sure we can map negative values to non-negative indices.
1. Sum of All Elements: We calculate the total sum of the array. This sum will help in calculating potential candidates for the outlier by subtracting the current number.
1. Iterating Through Each Number:
    - For each element in the array, we subtract that element from the total sum. This gives us the sum of the remaining elements, which is potentially the sum of the special numbers.
    - If the remaining sum is even, we check if half of the remaining sum exists in the frequency array (since two special numbers must sum up to this remaining value).
1. Validating the Outlier: If the remaining sum is valid, and the corresponding element is found in the array, we conclude that the current element is the outlier.
1. Returning the Largest Outlier: During the iteration, we will track the largest outlier and return it as the result.

# Complexity
- Time complexity:
    - The first loop to calculate the sum and populate the frequency array takes O(n), where n is the length of the array.
    - The second loop to check for each potential outlier also takes O(n).
    - So, the overall time complexity is O(n).

- Space complexity:
    - We are using a frequency array of fixed size (2001 elements) to handle the range of values from -1000 to 1000. This array takes up O(1) space, as its size does not depend on the input size.
    - The space complexity is therefore O(n) due to the space required for storing the input array.

# Code
```java []
class Solution {
    public int getLargestOutlier(int[] nums) {
        int n = nums.length;
        int[] freq = new int[2001];
        int sum = 0;
        for (int num : nums) {
            freq[num + 1000]++;
            sum += num;
        }
        int max = -1000;
        for (int num : nums) {
            int rem = sum - num - num;
            if (rem + 1000 >= 0 && rem + 1000 <= 2000 && freq[rem + 1000] > (rem == num ? 1 : 0)) {
                max = Math.max(rem, max);
            }
        }
        return max;
    }
}
```
['Java']