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 Map and Set Enumeration

Intuition

Since exactly n-2 elements are special numbers, and the other two are the sum and the outlier, we can try every possible pair of numbers as (sum, outlier), check if the rest can sum up to the sum, and return the largest valid outlier.

Approach

  1. For each pair of indices (i, j) in nums (i != j):
    • Assume nums[i] is the sum, nums[j] is the outlier.
    • Build a multiset of the remaining numbers.
    • Check if the sum of the multiset equals nums[i].
    • If so, nums[j] is a valid outlier.
  2. Track the largest valid outlier found.
  3. Return the largest outlier.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int findLargestOutlier(vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MIN;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) if (i != j) {
                int sum = 0;
                for (int k = 0; k < n; ++k) if (k != i && k != j) sum += nums[k];
                if (sum == nums[i]) ans = max(ans, nums[j]);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func findLargestOutlier(nums []int) int {
    ans := -1 << 31
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i == j { continue }
            sum := 0
            for k := 0; k < n; k++ {
                if k != i && k != j {
                    sum += nums[k]
                }
            }
            if sum == nums[i] && nums[j] > ans {
                ans = nums[j]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findLargestOutlier(int[] nums) {
        int n = nums.length, ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) if (i != j) {
                int sum = 0;
                for (int k = 0; k < n; ++k) if (k != i && k != j) sum += nums[k];
                if (sum == nums[i]) ans = Math.max(ans, nums[j]);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findLargestOutlier(nums: IntArray): Int {
        var ans = Int.MIN_VALUE
        val n = nums.size
        for (i in 0 until n) {
            for (j in 0 until n) if (i != j) {
                var sum = 0
                for (k in 0 until n) if (k != i && k != j) sum += nums[k]
                if (sum == nums[i]) ans = maxOf(ans, nums[j])
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findLargestOutlier(self, nums: list[int]) -> int:
        n = len(nums)
        ans = float('-inf')
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                s = sum(nums[k] for k in range(n) if k != i and k != j)
                if s == nums[i]:
                    ans = max(ans, nums[j])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn find_largest_outlier(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = i32::MIN;
        for i in 0..n {
            for j in 0..n {
                if i == j { continue; }
                let mut sum = 0;
                for k in 0..n {
                    if k != i && k != j {
                        sum += nums[k];
                    }
                }
                if sum == nums[i] && nums[j] > ans {
                    ans = nums[j];
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    findLargestOutlier(nums: number[]): number {
        let ans = -Infinity;
        const n = nums.length;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) if (i !== j) {
                let s = 0;
                for (let k = 0; k < n; ++k) if (k !== i && k !== j) s += nums[k];
                if (s === nums[i]) ans = Math.max(ans, nums[j]);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of nums, due to three nested loops.
  • 🧺 Space complexity: O(1), only a few variables are used for computation.

Method 2 – 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)