Skip to content

3371. Identify the Largest Outlier in an Array

Description

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.

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.

Solutions

Solution 1: Hash Table + Enumeration

We use a hash table $\textit{cnt}$ to record the frequency of each element in the array $\textit{nums}$.

Next, we enumerate each element $x$ in the array $\textit{nums}$ as a possible outlier. For each $x$, we calculate the sum $t$ of all elements in the array $\textit{nums}$ except $x$. If $t$ is not even, or half of $t$ is not in $\textit{cnt}$, then $x$ does not meet the condition, and we skip this $x$. Otherwise, if $x$ is not equal to half of $t$, or $x$ appears more than once in $\textit{cnt}$, then $x$ is a possible outlier, and we update the answer.

After enumerating all elements, we return the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        s = sum(nums)
        cnt = Counter(nums)
        ans = -inf
        for x, v in cnt.items():
            t = s - x
            if t % 2 or cnt[t // 2] == 0:
                continue
            if x != t // 2 or v > 1:
                ans = max(ans, x)
        return ans
 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(int[] nums) {
        int s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            s += x;
            cnt.merge(x, 1, Integer::sum);
        }
        int ans = Integer.MIN_VALUE;
        for (var e : cnt.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            int t = s - x;
            if (t % 2 != 0 || !cnt.containsKey(t / 2)) {
                continue;
            }
            if (x != t / 2 || v > 1) {
                ans = Math.max(ans, x);
            }
        }
        return ans;
    }
}
 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) {
        int s = 0;
        unordered_map<int, int> cnt;
        for (int x : nums) {
            s += x;
            cnt[x]++;
        }
        int ans = INT_MIN;
        for (auto [x, v] : cnt) {
            int t = s - x;
            if (t % 2 || !cnt.contains(t / 2)) {
                continue;
            }
            if (x != t / 2 || v > 1) {
                ans = max(ans, x);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func getLargestOutlier(nums []int) int {
    s := 0
    cnt := map[int]int{}
    for _, x := range nums {
        s += x
        cnt[x]++
    }
    ans := math.MinInt32
    for x, v := range cnt {
        t := s - x
        if t%2 != 0 || cnt[t/2] == 0 {
            continue
        }
        if x != t/2 || v > 1 {
            ans = max(ans, x)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function getLargestOutlier(nums: number[]): number {
    let s = 0;
    const cnt: Record<number, number> = {};
    for (const x of nums) {
        s += x;
        cnt[x] = (cnt[x] || 0) + 1;
    }
    let ans = -Infinity;
    for (const [x, v] of Object.entries(cnt)) {
        const t = s - +x;
        if (t % 2 || !cnt.hasOwnProperty((t / 2) | 0)) {
            continue;
        }
        if (+x != ((t / 2) | 0) || v > 1) {
            ans = Math.max(ans, +x);
        }
    }
    return ans;
}

Comments