💡 Find the Largest Outlier in an Array 🧐
\uD83E\uDDE0 Intuition\n1. Key Insight \uD83E\uDDD0:\n   The array consists of numbers such that one element represents the sum of special numbers, and another 
# \uD83E\uDDE0 Intuition\n1. **Key Insight \uD83E\uDDD0**:\n   The array consists of numbers such that one element represents the sum of special numbers, and another is the outlier. By removing the sum element and one other element, the remaining numbers should form a valid pair-wise sum.  \n2. **Efficient Strategy**:  \n   - Sort the array for easy traversal.  \n   - Check for each candidate outlier and validate if the remaining numbers sum correctly to identify it.  \n\n---\n\n# \uD83D\uDEE0\uFE0F Approach\n1. **Sort the Array**:  \n   This simplifies operations like binary search and helps ensure correctness when verifying the sum condition.  \n2. **Iterate Backwards**:  \n   Check potential outliers starting from the largest element, as the goal is to find the largest outlier.  \n3. **Binary Search for Validation**:  \n   Use a binary search to verify the presence of the sum of special numbers.  \n\n---\n\n# \u23F3 Complexity  \n- **Time Complexity**:  \n  $$ O(n \\log n) $$ due to sorting and binary search.  \n- **Space Complexity**:  \n  $$ O(1) $$ additional space apart from the input array.  \n\n---\n![c1ee5054-dd07-4caa-a7df-e21647cfae9e_1709942227.5165014.png](https://assets.leetcode.com/users/images/2142d5e3-a62b-41c7-8f0a-2511d6ed85e7_1733114638.595336.png)\n\n# Code \uD83D\uDCBB  \n\n```cpp []\nclass Solution {\npublic:\n    int getLargestOutlier(vector<int>& nums) {\n        sort(nums.begin(), nums.end());  // Sort the array\n        int sum = 0;\n        unordered_map<int, int> mp;     // Frequency map for validation\n\n        for (int i : nums) {\n            sum += i;                   // Calculate the total sum\n            mp[i]++;\n        }\n\n        for (int i = nums.size() - 1; i >= 0; i--) {\n            double potentialSum = (sum - nums[i]) / 2.0;\n\n            if (binary_search(nums.begin(), nums.end(), potentialSum)) {\n                // Validate the sum condition\n                if ((potentialSum == nums[i] && mp[nums[i]] >= 2) || potentialSum != nums[i]) {\n                    return nums[i];     // Return the largest valid outlier\n                }\n            }\n        }\n\n        return 0;  // Default return value (should not occur)\n    }\n};\n```\n\n```java []\nclass Solution {\n    public boolean binarySearch(int[] nums, double target) {\n        int left = 0, right = nums.length - 1;\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            if (nums[mid] == target) {\n                return true;\n            } else if (nums[mid] < target) {\n                left = mid + 1;\n            } else {\n                right = mid - 1;\n            }\n        }\n        return false;\n    }\n\n    public int getLargestOutlier(int[] nums) {\n        Arrays.sort(nums); // Sort the array\n        int totalSum = Arrays.stream(nums).sum();\n        Map<Integer, Integer> freq = new HashMap<>();\n\n        for (int num : nums) {\n            freq.put(num, freq.getOrDefault(num, 0) + 1);\n        }\n\n        for (int i = nums.length - 1; i >= 0; i--) {\n            double potentialSum = (totalSum - nums[i]) / 2.0;\n\n            // Use the manual binary search function\n            if (binarySearch(nums, potentialSum)) {\n                if ((potentialSum == nums[i] && freq.get(nums[i]) >= 2) || potentialSum != nums[i]) {\n                    return nums[i];\n                }\n            }\n        }\n\n        return 0;\n    }\n}\n\n```\n\n```python []\nclass Solution:\n    def binary_search(self, nums: List[int], target: float) -> bool:\n        left, right = 0, len(nums) - 1\n        while left <= right:\n            mid = (left + right) // 2\n            if nums[mid] == target:\n                return True\n            elif nums[mid] < target:\n                left = mid + 1\n            else:\n                right = mid - 1\n        return False\n\n    def getLargestOutlier(self, nums: List[int]) -> int:\n        nums.sort()  # Sort the array\n        total_sum = sum(nums)\n        freq = Counter(nums)\n\n        for i in range(len(nums) - 1, -1, -1):\n            potential_sum = (total_sum - nums[i]) / 2.0\n\n            # Use the manual binary search function\n            if self.binary_search(nums, potential_sum):\n                if (potential_sum == nums[i] and freq[nums[i]] >= 2) or potential_sum != nums[i]:\n                    return nums[i]\n\n        return 0\n\n```\n---\n\n# Conclusion \uD83D\uDE80  \n\nThis solution efficiently identifies the largest outlier by leveraging sorting and binary search. The logic ensures correctness and optimal performance even for large input sizes.  \n\nIf you found this explanation helpful, don\u2019t forget to **upvote** and share your feedback! \uD83D\uDE0A Happy coding!\n\n![1HBC0324_COV.jpg](https://assets.leetcode.com/users/images/a6777a40-5a0e-45e2-a26a-6703814ddf74_1733114696.3979058.jpeg)\n
['Hash Table', 'Binary Search', 'C++', 'Java', 'Python3']