🔥Beats 100 % 🔥 |  O(n) and O(1) | 2 Solutions | ✔️ Explained & Optimized Solution ✔️ |
Intuition\nWe first calculate the total sum of the array, then iterate through each number k. For each number, we temporarily remove it and check if the sum of 
# Intuition\nWe first calculate the total **sum** of the array, then iterate through each number `k`. For each number, we temporarily remove it and check if the sum of the remaining numbers `sum - k` is divisible by `2`. If yes, compute the target value `p = (sum - k) / 2`. Check if `p` exists in the remaining numbers using a **frequency map** or **multiset**. If it does, update the maximum outlier `k`. After the check, restore `k` back to the data structure. Finally, return the largest valid `k`, or a **default** value if no such number exists.\n\n# Approach\n\n`Step 1` **Calculate the Total Sum :**\n- Compute the **sum** of all elements in the array. This will help us evaluate the condition of `divisibility by 2`.\n\n`Step 2` **Use a Multiset for Frequency Tracking :**\n\n- A `multiset` keeps track of the occurrences of each element, allowing **efficient addition, removal, and lookup**.\n\n`Step 3` **Iterate Through the Array :**\n\n- For each element:\n    - Temporarily remove it from the `multiset`.\n    - Check if sum of the remaining elements `(sum - k)` is **even**.\n    - If yes, check if half of **sum** exists in the remaining array.\n\n`Step 4` **Update the Answer :**\n- If all conditions are satisfied, update the maximum **outlier** found so far.\n\n`Step 5` **Restore the Multiset :**\n- After evaluating the current number, restore it to the `multiset`.\n\n`Step 6` **Return the Largest Outlier :**\n- If no valid `outlier` is found, return a **default value**.\n\n# Complexity\n- Time complexity : $$O(n)$$\n- Space complexity : $$O(1)$$\n\n# Code\n```java []\nclass Solution \n{\n    public int getLargestOutlier(int[] nums) \n    {\n        // Step 1: Calculate the total sum of the array\n        int sum = 0;\n        for (int num : nums)\n        {\n            sum += num;\n        }\n        \n        // Step 2: Use a TreeMap to mimic multiset functionality\n        TreeMap<Integer, Integer> frequencyMap = new TreeMap<>();\n        for (int num : nums) \n        {\n            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);\n        }\n        \n        // Step 3: Initialize the answer as the smallest possible value\n        int ans = Integer.MIN_VALUE;\n\n        // Step 4: Iterate through each number in the array\n        for (int num : nums) \n        {\n            // Check if the sum excluding the current number is even\n            if ((sum - num) % 2 == 0) \n            {\n                int target = (sum - num) / 2;\n\n                // Temporarily reduce the count of the current number\n                frequencyMap.put(num, frequencyMap.get(num) - 1);\n                if (frequencyMap.get(num) == 0) \n                {\n                    frequencyMap.remove(num);\n                }\n\n                // Check if the target exists in the map\n                if (frequencyMap.containsKey(target)) \n                {\n                    // Update the maximum outlier found so far\n                    ans = Math.max(ans, num);\n                }\n\n                // Restore the current number to the map\n                frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);\n            }\n        }\n        \n        // Step 5: Return the largest outlier, or a default value if none found\n        return ans == Integer.MIN_VALUE ? -1 : ans;\n    }\n}\n```\n\n```C++ []\nclass Solution\n{\npublic:\n    int getLargestOutlier(vector<int>& nums)\n    {\n        // Step 1: Calculate the total sum of the array\n        int sum = 0;\n        for (int k : nums)\n        {\n            sum += k;\n        }\n\n        // Step 2: Use a multiset to track occurrences of elements\n        multiset<int> st(nums.begin(), nums.end());\n\n        // Step 3: Initialize the answer as the smallest possible value\n        int ans = INT_MIN;\n\n        // Step 4: Iterate through each number in the array\n        for (int k : nums)\n        {\n            // Check if the sum excluding the current number is even\n            if ((sum - k) % 2 == 0)\n            {\n                // Temporarily remove the current number from the multiset\n                st.erase(st.find(k));\n\n                // Calculate the target number\n                int p = (sum - k) / 2;\n\n                // Check if the target exists in the multiset\n                if (st.find(p) != st.end())\n                {\n                    // Update the maximum outlier found so far\n                    ans = max(ans, k);\n                }\n\n                // Step 5 : Restore the current number back into the multiset\n                st.insert(k);\n            }\n        }\n\n        // Step 6: Return the largest outlier, or a default value if none found\n        return ans;\n    }\n};\n\n```
['Array', 'Ordered Map', 'C++', 'Java']