Well Explained, Beginner Friendly Solution !!! O(n) Solution !!! Beats 100% Solutions !!!
Intuition\n\nTo solve this problem, we need to find the largest potential outlier in an array where:\n- \( n - 2 \) elements are special numbers.\n- One element
### Intuition\n\nTo solve this problem, we need to find the largest potential outlier in an array where:\n- \\( n - 2 \\) elements are special numbers.\n- One element is the sum of the special numbers.\n- One element is the outlier, which is distinct from both the sum element and the special numbers.\n\nThe problem hints that we can leverage the relationship between the sum of all elements and the sum of special numbers. Specifically, the sum of all elements in the array is related to the sum of the special numbers, their sum, and the outlier. This relationship can be described by the equation:\n\n$$\n\\text{total\\_sum} = 2 \\times (\\text{sum of special numbers}) + (\\text{outlier})\n$$\n\nThe task is to find the largest outlier, given that there is one candidate that is the sum of the special numbers and the rest are special numbers.\n\n---\n\n### Approach\n\nTo solve this efficiently, I\u2019ll break down the approach as follows:\n\n1. **Calculate the Total Sum of All Elements**:  \n   First, compute the sum of all elements in the array (`total_sum`). This will help us later in identifying potential outliers.\n\n2. **Count Frequencies of Elements**:  \n   Use a dictionary (`num_counts`) to track the frequency of each number in the array. This helps in quickly checking whether a number exists in the array when needed.\n\n3. **Identify Possible Outliers**:  \n   For each unique number `num` in the array, treat it as a candidate for the sum of the special numbers. The potential outlier is calculated using the formula:\n   $$\n   \\text{potential\\_outlier} = \\text{total\\_sum} - 2 \\times \\text{num}\n   $$\n   This formula comes from the equation:\n   $$\n   \\text{outlier} = \\text{total\\_sum} - 2 \\times \\text{sum of special numbers}\n   $$\n\n4. **Check Validity of Potential Outlier**:  \n   For each candidate number, check if the calculated potential outlier exists in the array. Ensure that the outlier is distinct from the candidate number, unless the candidate appears multiple times in the array.\n\n5. **Track the Largest Outlier**:  \n   Throughout the iteration, keep track of the largest valid outlier and return that as the result.\n\n---\n\n### Complexity\n\n- **Time complexity**:  \n  - Calculating the total sum: \\(O(n)\\), where \\(n\\) is the number of elements in the array.\n  - Constructing the frequency map: \\(O(n)\\).\n  - Iterating over the unique keys in the frequency map: \\(O(m)\\), where \\(m\\) is the number of unique elements, and \\(m \\leq n\\).  \n  - Therefore, the overall time complexity is \\(O(n)\\).\n\n- **Space complexity**:  \n  The space complexity is dominated by the space used for the frequency map, which stores the count of each unique number. Hence, the space complexity is \\(O(m)\\), where \\(m\\) is the number of unique elements in the array.\n\n---\n\n### Code\n\n```python\n\nclass Solution:\n    def getLargestOutlier(self, nums: List[int]) -> int:\n    \n        total_sum = sum(nums)  \n      \n        num_counts = defaultdict(int)\n        for num in nums:\n            num_counts[num] += 1\n        \n\n        largest_outlier = float(\'-inf\')\n        \n \n        for num in num_counts.keys():\n          \n            potential_outlier = total_sum - 2 * num  \n            \n \n            if potential_outlier in num_counts:\n                if potential_outlier != num or num_counts[num] > 1: \n                    largest_outlier = max(largest_outlier, potential_outlier)\n        \n    \n        return largest_outlier\n
['Python3']