Skip to content

3371. Identify the Largest Outlier in an Array 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int getLargestOutlier(vector<int>& nums) {
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    int ans = INT_MIN;
    unordered_map<int, int> count;

    for (const int num : nums)
      ++count[num];

    for (const int num : nums) {
      const int withoutNum = sum - num;
      if (withoutNum % 2 == 0) {
        const int specialSum = withoutNum / 2;  // the sum of special numbers
        if (count[specialSum] > (num == specialSum ? 1 : 0))
          ans = max(ans, num);
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int getLargestOutlier(int[] nums) {
    final int sum = Arrays.stream(nums).sum();
    int ans = Integer.MIN_VALUE;
    Map<Integer, Integer> count = new HashMap<>();

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    for (final int num : nums) {
      final int withoutNum = sum - num;
      if (withoutNum % 2 == 0) {
        final int specialSum = withoutNum / 2; // the sum of special numbers
        if (count.getOrDefault(specialSum, 0) > (num == specialSum ? 1 : 0))
          ans = Math.max(ans, num);
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def getLargestOutlier(self, nums: list[int]) -> int:
    ans = -math.inf
    summ = sum(nums)
    count = collections.Counter(nums)

    for num in nums:
      withoutNum = summ - num
      if withoutNum % 2 == 0:
        specialSum = withoutNum // 2  # the sum of special numbers
        if count[specialSum] > (1 if num == specialSum else 0):
          ans = max(ans, num)

    return ans