Problem

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**** potentialoutlier in nums.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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 <= 10^5
  • -1000 <= nums[i] <= 1000
  • The input is generated such that at least one potential outlier exists in nums.

Solution

Method 1 – Hash Set and Total Sum

Intuition

The sum of all special numbers is present in the array, and the outlier is the remaining number. For each number, try removing it and see if the rest can be split into (n-2) numbers and their sum.

Approach

  1. Compute the total sum of the array.
  2. For each number x in nums, let s = total - x. If s - y (for some y ≠ x) is also in nums, then x or y could be the outlier. Try all possibilities and track the largest valid outlier.
  3. Use a Counter to handle duplicates.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import java.util.*;
class Solution {
    public int findLargestOutlier(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        long total = 0;
        for (int x : nums) {
            count.put(x, count.getOrDefault(x, 0) + 1);
            total += x;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            int x = nums[i];
            long s = total - x;
            for (int j = 0; j < nums.length; ++j) {
                if (i == j) continue;
                int y = nums[j];
                if (s - y == y) {
                    int cnt = count.get(y);
                    if ((x == y && cnt >= 2) || (x != y && cnt >= 1)) {
                        res = Math.max(res, x);
                    }
                }
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import Counter
def findLargestOutlier(nums):
    total = sum(nums)
    count = Counter(nums)
    res = float('-inf')
    n = len(nums)
    for i, x in enumerate(nums):
        s = total - x
        for j, y in enumerate(nums):
            if i == j:
                continue
            if s - y == y:
                cnt = count[y]
                if (x == y and cnt >= 2) or (x != y and cnt >= 1):
                    res = max(res, x)
    return int(res)

Complexity

  • ⏰ Time complexity: O(n^2) (can be optimized to O(n) with sorting and set, but this is the direct approach).
  • 🧺 Space complexity: O(n)