3371. Identify the Largest Outlier in an Array LeetCode Solution

In this guide, you will get 3371. Identify the Largest Outlier in an Array LeetCode Solution with the best time and space complexity. The solution to Identify the Largest Outlier in an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Identify the Largest Outlier in an Array solution in C++
  4. Identify the Largest Outlier in an Array solution in Java
  5. Identify the Largest Outlier in an Array solution in Python
  6. Additional Resources
3371. Identify the Largest Outlier in an Array LeetCode Solution image

Problem Statement of Identify the Largest Outlier in an Array

You are given an integer array nums. This array contains n elements, where exactly n – 2 elements are special numbers. One of the remaining two elements is the sum of these special numbers, and the other is an outlier.
An outlier is defined as a number that is neither one of the original special numbers nor the element representing the sum of those numbers.
Note that special numbers, the sum element, and the outlier must have distinct indices, but may share the same value.
Return the largest potential outlier in nums.

Example 1:

Input: nums = [2,3,5,10]
Output: 10
Explanation:
The special numbers could be 2 and 3, thus making their sum 5 and the outlier 10.

Example 2:

Input: nums = [-2,-1,-3,-6,4]
Output: 4
Explanation:
The special numbers could be -2, -1, and -3, thus making their sum -6 and the outlier 4.

See also  3010. Divide an Array Into Subarrays With Minimum Cost I LeetCode Solution

Example 3:

Input: nums = [1,1,1,1,1,5,5]
Output: 5
Explanation:
The special numbers could be 1, 1, 1, 1, and 1, thus making their sum 5 and the other 5 as the outlier.

Constraints:

3 <= nums.length <= 105
-1000 <= nums[i] <= 1000
The input is generated such that at least one potential outlier exists in nums.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

3371. Identify the Largest Outlier in an Array LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

3371. Identify the Largest Outlier in an Array LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

3371. Identify the Largest Outlier in an Array LeetCode Solution in Python

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
# code by PROGIEZ

Additional Resources

See also  3082. Find the Sum of the Power of All Subsequences LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.