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] <= 1000nums.Problem Overview: You receive an integer array where all elements except one form a special structure: among the remaining numbers, one value equals the sum of several others. The task is to identify the largest number that could be the outlier while the rest of the array still satisfies this condition.
The key observation comes from simple algebra. If o is the outlier and y is the element equal to the sum of the special numbers, then:
totalSum - o - y = y
Rearranging gives y = (totalSum - o) / 2. For any candidate outlier o, the array must contain a valid y. Efficient solutions focus on testing this relationship quickly.
Approach 1: Sorting and Iterative Check (O(n log n) time, O(1) extra space)
Sort the array first, then iterate from the largest value toward the smallest while treating each element as a possible outlier. For each candidate o, compute (totalSum - o) / 2 and check whether that value exists elsewhere in the array. Sorting helps you evaluate larger outliers first and use binary search or pointer checks for existence. The approach is straightforward and works well when the array size is moderate.
This solution relies mainly on Array manipulation and enumeration of candidates. The downside is the O(n log n) cost from sorting.
Approach 2: Hashing for Frequency and Sum (O(n) time, O(n) space)
Use a frequency map to store counts of every value in the array. Compute the total sum once. Then iterate through the array and treat each number as the potential outlier o. Calculate remaining = totalSum - o. If remaining is even, the required element must be y = remaining / 2.
Check the hash map to see if y exists among the remaining elements. Frequency handling matters: if y equals the candidate outlier, ensure its count is greater than one before accepting it. Track the largest valid outlier while scanning the array. Hash lookups keep the validation constant time.
This method uses a Hash Table for frequency counting and efficient lookups. The algorithm performs a single pass after building the map, giving an optimal O(n) time solution with O(n) space.
Recommended for interviews: Start by explaining the equation derived from the sum relationship. A brute reasoning step shows you understand the structure of the problem. Then move to the hash map solution, which interviewers typically expect because it reduces the search to constant-time lookups using Counting and frequency tracking. The O(n) hashing approach is both clean and optimal.
By sorting the array, we can easily identify potential sums and iterate through the list to find the largest value that cannot be a part of the sum. Leveraging the sorted property, we can assess elements from the smallest to the largest, mindful of how they can sum to intermediate values that appear in the array.
The array is sorted, and the potential sum is determined using all elements except the largest. If this sum matches the last element (the largest), it implies there's another candidate, so we check its neighbor. Sorting helps quickly determine which number might be an outlier.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), since no additional space proportionate to input size is used.
To find the largest outlier efficiently without sorting, use a hashmap to count element frequencies and determine potential outliers by verifying if an element could be a sum by considering n-2 special numbers. The goal is to ensure only one potential sum matches an element, allowing easy identification of the outlier.
This C solution uses an integer frequency array to count elements quickly. A frequency table and ongoing sum calculation allow assessing if removing a value provides a valid sum equated to another element in the array. The largest outlier is returned when the expected condition is met.
Time Complexity: O(n).
Space Complexity: O(1) due to fixed hash table size relative to input.
We use a hash table cnt to record the frequency of each element in the array nums.
Next, we enumerate each element x in the array nums as a possible outlier. For each x, we calculate the sum t of all elements in the array nums except x. If t is not even, or half of t is not in 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 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 nums.
| Approach | Complexity |
|---|---|
| Sorting and Iterative Check | Time Complexity: O(n log n) due to sorting. |
| Hashing for Frequency and Sum | Time Complexity: O(n). |
| Hash Table + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Iterative Check | O(n log n) | O(1) | Useful when avoiding extra memory or when the array is already sorted. |
| Hashing for Frequency and Sum | O(n) | O(n) | Best general solution. Fast lookups make candidate validation constant time. |
3371. Identify the Largest Outlier in an Array | Hash Table | Math • Aryan Mittal • 4,272 views views
Watch 9 more video solutions →Practice Identify the Largest Outlier in an Array with our built-in code editor and test cases.
Practice on FleetCode