LeetCode 3371 - Identify the Largest Outlier in an Array

LeetCode Problem 3371

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting, Enumeration

Solution

Problem Understanding

The problem gives us an integer array nums containing exactly three types of elements:

1. n - 2 special numbers
2. One element equal to the sum of all special numbers
3. One outlier

The task is to return the largest possible value that could serve as the outlier.

The important detail is that these roles are determined by indices, not values. Multiple elements may share the same value, but they must occupy different positions in the array. This distinction becomes very important in cases with duplicates.

Suppose the array has:

• special numbers with total sum S
• one element equal to S
• one outlier x

Then the total array sum becomes:

total = S + S + x

which simplifies to:

total = 2S + x

From this equation, if we assume some value x is the outlier, then:

S = (total - x) / 2

This observation is the key to solving the problem efficiently.

The constraints are important:

• nums.length can be as large as 10^5
• values range from -1000 to 1000

An O(n^2) solution may be too slow in the worst case, so we should aim for a linear or near-linear approach.

There are several edge cases that can easily cause mistakes:

• Duplicate values, especially when the sum element and outlier share the same value
• Negative numbers
• Arrays where the outlier itself could also equal the computed sum numerically
• Multiple valid interpretations of the array
• Ensuring the sum element and outlier use distinct indices

The problem guarantees that at least one valid outlier exists.

Approaches

Brute Force Approach

A brute-force solution would try every element as the outlier.

For each candidate outlier:

1. Remove it conceptually from the array.
2. Among the remaining elements, try every element as the sum element.
3. Check whether the rest of the numbers add up correctly.

More concretely:

• Let x be the outlier.
• Let s be the sum element.
• Remove both from the total sum.
• Verify whether the remaining numbers sum to s.

This works because it explicitly checks every valid configuration.

However, this requires nested iteration. With n elements:

• n choices for outlier
• n choices for sum element

This leads to O(n^2) time complexity, which is too expensive for n = 10^5.

Optimal Approach

The key mathematical observation is:

total = 2 * special_sum + outlier

If we assume some number x is the outlier, then:

special_sum = (total - x) / 2

This means:

• total - x must be even
• The value (total - x) / 2 must exist in the array as the sum element
• The sum element and outlier must use distinct indices

We can use a frequency map to check existence efficiently.

For each candidate outlier x:

1. Compute remaining = total - x
2. If remaining is odd, skip
3. Compute sum_element = remaining // 2
4. Verify that sum_element exists in the array
5. Handle duplicates carefully:

• If sum_element == x, then we need at least two occurrences

This reduces the problem to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Try every outlier and sum-element pair
Optimal	O(n)	O(n)	Uses algebra and a frequency map

Algorithm Walkthrough

1. Compute the total sum of the array.

Let:

total = sum(nums)

This allows us to derive the special-number sum for any candidate outlier. 2. Build a frequency map.

We use a hash map to count how many times each value appears.

This is necessary because:

• We need fast existence checks
• Duplicate handling is critical

3. Iterate through every number as a possible outlier.

Suppose the current candidate is x. 4. Remove the candidate outlier conceptually.

The remaining sum becomes:

remaining = total - x

5. Check whether the remaining sum is even.

Since:

remaining = 2 * special_sum

it must be divisible by 2.

If it is odd, this candidate cannot be valid. 6. Compute the required sum element.

sum_element = remaining // 2

7. Verify the sum element exists.

We use the frequency map for O(1) lookup. 8. Handle the duplicate-value case carefully.

If:

sum_element == x

then we need at least two copies of that value:

• one index for the outlier
• one index for the sum element

9. Track the maximum valid outlier.

Since the problem asks for the largest valid outlier, we update the answer whenever we find a larger valid candidate.

Why it works

The algorithm is based on the invariant:

total = 2 * special_sum + outlier

For every candidate outlier, we uniquely determine the required sum element. If that sum element exists with valid indexing constraints, then the array can indeed be partitioned into:

• special numbers
• their sum
• the outlier

Because we test every possible outlier and validate it correctly, the algorithm always finds the largest valid one.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        frequency = Counter(nums)

        largest_outlier = float("-inf")

        for outlier in nums:
            remaining = total_sum - outlier

            # remaining must equal 2 * special_sum
            if remaining % 2 != 0:
                continue

            sum_element = remaining // 2

            if sum_element not in frequency:
                continue

            # Need distinct indices if values are equal
            if sum_element == outlier and frequency[outlier] < 2:
                continue

            largest_outlier = max(largest_outlier, outlier)

        return largest_outlier

The implementation begins by computing the total array sum. This value is reused throughout the algorithm and avoids repeated summation work.

Next, a Counter stores the frequency of each number. This allows constant-time existence checks and correctly handles duplicate-value situations.

The main loop treats each number as a possible outlier. For every candidate:

• We remove it conceptually from the total sum.
• We verify that the remaining sum is even.
• We compute the required sum element.
• We check whether that sum element exists.

The duplicate-value condition is especially important. If the outlier and sum element share the same value, there must be at least two copies available so they can occupy different indices.

Finally, we keep the maximum valid outlier and return it.

Go Solution

package main

func getLargestOutlier(nums []int) int {
	totalSum := 0
	frequency := make(map[int]int)

	for _, num := range nums {
		totalSum += num
		frequency[num]++
	}

	largestOutlier := -1 << 60

	for _, outlier := range nums {
		remaining := totalSum - outlier

		// remaining must equal 2 * specialSum
		if remaining%2 != 0 {
			continue
		}

		sumElement := remaining / 2

		count, exists := frequency[sumElement]
		if !exists {
			continue
		}

		// Need distinct indices if values are equal
		if sumElement == outlier && count < 2 {
			continue
		}

		if outlier > largestOutlier {
			largestOutlier = outlier
		}
	}

	return largestOutlier
}

The Go implementation follows the same logic as the Python solution.

Instead of Counter, Go uses a map[int]int to store frequencies.

Go integers are sufficient for this problem because the maximum possible total sum is well within 32-bit integer range:

10^5 * 1000 = 10^8

The initialization:

largestOutlier := -1 << 60

acts as a very small sentinel value for comparison purposes.

Worked Examples

Example 1

nums = [2, 3, 5, 10]

Total sum:

20

Frequency map:

Value	Count
2	1
3	1
5	1
10	1

Now iterate.

Candidate Outlier	Remaining	Even?	Required Sum Element	Exists?	Valid?
2	18	Yes	9	No	No
3	17	No	-	-	No
5	15	No	-	-	No
10	10	Yes	5	Yes	Yes

Largest valid outlier:

10

Example 2

nums = [-2, -1, -3, -6, 4]

Total sum:

-8

Frequency map:

Value	Count
-2	1
-1	1
-3	1
-6	1
4	1

Iteration:

Candidate Outlier	Remaining	Even?	Required Sum Element	Exists?	Valid?
-2	-6	Yes	-3	Yes	Yes
-1	-7	No	-	-	No
-3	-5	No	-	-	No
-6	-2	Yes	-1	Yes	Yes
4	-12	Yes	-6	Yes	Yes

Largest valid outlier:

4

Example 3

nums = [1,1,1,1,1,5,5]

Total sum:

15

Frequency map:

Value	Count
1	5
5	2

Iteration:

Candidate Outlier	Remaining	Even?	Required Sum Element	Exists?	Valid?
1	14	Yes	7	No	No
5	10	Yes	5	Yes	Yes

The duplicate check succeeds because there are two copies of 5.

Largest valid outlier:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass for frequency counting and one pass for validation
Space	O(n)	Hash map stores frequencies

The algorithm performs only constant-time work per element. Hash map lookups are O(1) on average, so the total runtime scales linearly with the array size.

The space complexity comes from storing frequencies for distinct values in the array.

Test Cases

from typing import List

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        from collections import Counter

        total_sum = sum(nums)
        frequency = Counter(nums)

        largest_outlier = float("-inf")

        for outlier in nums:
            remaining = total_sum - outlier

            if remaining % 2 != 0:
                continue

            sum_element = remaining // 2

            if sum_element not in frequency:
                continue

            if sum_element == outlier and frequency[outlier] < 2:
                continue

            largest_outlier = max(largest_outlier, outlier)

        return largest_outlier

solution = Solution()

assert solution.getLargestOutlier([2, 3, 5, 10]) == 10
# Basic positive-number example

assert solution.getLargestOutlier([-2, -1, -3, -6, 4]) == 4
# Negative numbers

assert solution.getLargestOutlier([1, 1, 1, 1, 1, 5, 5]) == 5
# Duplicate sum/outlier values

assert solution.getLargestOutlier([0, 0, 0]) == 0
# Smallest valid array with duplicates

assert solution.getLargestOutlier([3, 6, 9, 18, 100]) == 100
# Large positive outlier

assert solution.getLargestOutlier([-5, -5, -10, 7]) == 7
# Negative special numbers

assert solution.getLargestOutlier([4, 4, 8, 8]) == 8
# Duplicate sum element and outlier

assert solution.getLargestOutlier([1, 2, 3, 6, 20]) == 20
# Outlier larger than all others

assert solution.getLargestOutlier([-1, -1, -2, -4]) == -4
# All negative values

assert solution.getLargestOutlier([10, -10, 0, 0]) == 0
# Zero as valid outlier

Test	Why
[2,3,5,10]	Basic valid configuration
[-2,-1,-3,-6,4]	Negative-number handling
[1,1,1,1,1,5,5]	Duplicate-value correctness
[0,0,0]	Smallest-size edge case
[3,6,9,18,100]	Very large outlier
[-5,-5,-10,7]	Negative special-number sum
[4,4,8,8]	Same value used for sum and outlier
[1,2,3,6,20]	Large positive outlier
[-1,-1,-2,-4]	Entirely negative array
[10,-10,0,0]	Zero-value handling

Edge Cases

One important edge case occurs when the sum element and outlier have the same value. For example:

[1,1,1,1,1,5,5]

A naive implementation might incorrectly reject this case because it sees only one value 5. However, the problem requires distinct indices, not distinct values. The frequency map solves this by verifying there are at least two copies whenever sum_element == outlier.

Another tricky case involves negative numbers. Since sums can become negative, implementations that assume positivity may fail. For example:

[-2,-1,-3,-6,4]

The algorithm works correctly because it relies purely on algebraic relationships rather than ordering or positivity assumptions.

Arrays containing zeros are also important. Consider:

[0,0,0]

Here, one zero can represent the special-number sum while another acts as the outlier. Duplicate handling again becomes essential. The implementation correctly validates this because the frequency count for 0 is at least two.

A final subtle case occurs when total - outlier is odd. Since this quantity must equal 2 * special_sum, odd values are impossible. The implementation immediately skips such candidates, preventing invalid fractional sums.