LeetCode 3371 – Identify The Largest Outlier In An Array (Python)

The problem seems to be pretty popular with Amazon and Meta (formerly known as Facebook) in the past 3 months.

At its core it’s a math problem and not a programming problem, so if you can figure out the mathematical trick, then this problem is pretty simple.

We’ve been given an array where n-2 are special numbers and one of the two remaining numbers is the sum of the these special numbers and the other is the outlier. So how do you figure out the outlier?

The trick is that if you remove the outlier then the array is simply 2S, where . So if we take the total sum of the array minus the outlier then it has to be an even number and thus has to be divisible by 2.
Another thing is that, since the sum of array minus the outlier is 2S, then there must exist a number S in the array. We can check this using a dictionary.

Our algorithm will be to initialise an outlier variable and then check each number one by one, compute the total minus the number. Check if the total is divisible by 2 and if the half of this number exists in the array, aka, is there a count > 0 in our array. To check this in O(1) time, we maintain a counter of all the numbers in our array. If these conditions are satisfied, then this number could be a possible outlier and we update our outlier variable. If not, we reset the count of the number and our total.

In the end we will return this outlier.

from collections import Counter
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        counts = Counter(nums)
        outlier = float("-inf")

        for num in nums:
            counts[num]-=1
            total_sum-=num
            if total_sum%2==0 and counts[total_sum//2]>0:
                outlier = max(outlier,num)

            counts[num]+=1
            total_sum+=num
        return outlier