Identify the Largest Outlier in an Array

XXX. Largest Outlier Detection

Hash Map

Frequency Analysis

Problem Statement:

Given a list of integers nums, find the largest number in the array that can be considered an "outlier". A number is defined as an outlier if the total sum of the remaining numbers in the array is equal to twice its value, while ensuring at least two such occurrences or a distinct condition to prevent self-pairing.

Algorithm:

1. Calculate Total Sum:

   Compute the total sum of all numbers in the array to facilitate the validation of the outlier condition.

2. Frequency Map:

   Build a frequency map to track occurrences of 2 * n values. This helps in quickly checking if a number can satisfy the outlier condition.

3. Validate Outliers:

   Iterate through the array, calculate the sum of the rest of the elements for each number, and check its validity based on the frequency map.

4. Track Maximum:

   Keep a record of the maximum valid outlier encountered during the iteration.

Complexity:

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n), due to the use of a frequency map.

Java Implementation:

class Solution {
    public int getLargestOutlier(List nums) {
        int ans = Integer.MIN_VALUE, sum = 0;
        Map freq = new HashMap<>();

        // Compute total sum and frequency of double values
        for (int n : nums) {
            sum += n;
            freq.put(n * 2, freq.getOrDefault(n * 2, 0) + 1);
        }

        // Check each number to find the largest outlier
        for (int n : nums) {
            int t = sum - n;
            if (freq.getOrDefault(t, 0) >= 2 || freq.getOrDefault(t, 0) == 1 && t != n * 2)
                ans = Math.max(ans, n);
        }

        return ans;
    }
}