3371. Identify the Largest Outlier in an Array

MediumArrayHash TableCountingEnumeration

Problem 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.

Intuition

The task is to find the largest outlier in the given array, where most of the elements are classified as special numbers, and only two elements are not: the sum of the special numbers and the outlier itself. Here’s how we can approach this:

Identify the Sum Element:
- Sum all elements in the array to get s.
- The outlier does not contribute to the sum of special numbers, so when we pick a candidate as an outlier, the sum of remaining numbers should be twice the sum element if the rest were the correct special numbers plus the sum element.
Use Enumeration Strategy:
- Go through each element x in nums and consider it as a potential outlier.
- Calculate the sum t i.e., the sum of all elements minus x (t = s - x). This t should be twice the sum of special numbers if x is truly an outlier.
Check Conditions for Outlier:
- If t is not even, x cannot be the outlier since (t / 2) should correspond to the sum element.
- Check if half of t is present in the original elements (cnt[t // 2] should be > 0).
- Ensure x does not interfere with index validity or frequency related conditions: x should be different from the candidate sum if it is participating in the sum process or should appear more than once if equal.
Determine Largest Outlier:
- Track the largest potential outlier that satisfies the conditions using a variable ans.

This conceptual understanding guides us to implement the solution leveraging a hash table for frequency checking, enabling efficient checks and updates.

Solution Approach

The solution efficiently determines the largest potential outlier by using a combination of hash table and enumeration strategies. Here's a walk-through of how the solution is implemented:

Hash Table for Frequency Count:
- Initialize a hash table cnt to store the frequency of each element in the array nums. This helps in quickly checking the presence of a potential sum element when evaluating candidates for the outlier.
Calculate Total Sum:
- Compute the sum s of all elements in the array using Python's built-in sum() function. This will be used to validate each potential outlier.
Iterate Over Each Element:
- Use a loop to iterate over the array using each element x as a candidate for the outlier.
Calculate and Evaluate Sum of Special Numbers:
- For each candidate x, compute t = s - x, which represents the theoretical sum of special numbers plus the candidate sum element.
- Check if t is even, as only an even t can be divided into twice the sum element. If t isn't even, skip this candidate.
Verify the Candidate:
- Check if the half of t (t // 2) exists in the array using the hash table cnt. If this condition isn't satisfied, the candidate x cannot be considered as an outlier.
- Make sure x itself is not half of t unless it appears more than once. This ensures index validity and avoids confusing x with the sum element.
Track Largest Potential Outlier:
- If x meets all conditions, update the maximum outlier value found so far using ans = max(ans, x).
Final Result:
- Once the loop completes, the value in ans is returned as the largest potential outlier.

This approach efficiently combines hash-table lookups and logic checks to determine which element stands out as a non-contributing outlier within the array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to better understand the process of identifying the largest potential outlier:

Example

Given the array nums = [2, 3, 5, 10, 7, 15], where n = 6, we seek the largest potential outlier.

Step 1: Calculate Total Sum

Total sum of the array s = 2 + 3 + 5 + 10 + 7 + 15 = 42

Step 2: Use a Hash Table for Frequency Count

Construct a frequency hash table: cnt = {2: 1, 3: 1, 5: 1, 10: 1, 7: 1, 15: 1}

Step 3: Iterate Over Each Element Evaluate each element as a potential outlier:

For x = 2
- Calculate t = s - x = 42 - 2 = 40
- t is even. Check if t // 2 = 20 exists in nums. It does not; skip x = 2.
For x = 3
- Calculate t = s - x = 42 - 3 = 39
- t is not even; skip x = 3.
For x = 5
- Calculate t = s - x = 42 - 5 = 37
- t is not even; skip x = 5.
For x = 10
- Calculate t = s - x = 42 - 10 = 32
- t is even. Check if t // 2 = 16 exists in nums. It does not; skip x = 10.
For x = 7
- Calculate t = s - x = 42 - 7 = 35
- t is not even; skip x = 7.
For x = 15
- Calculate t = s - x = 42 - 15 = 27
- t is not even; skip x = 15.

Step 4: Determine Largest Potential Outlier

None of the elements satisfied the conditions for being an outlier based on our loop checks.

Final Result

Since no valid outlier was found, theoretically, we could return a relevant value for this case, such as indicating no outlier was present.

In this particular example run, no valid outlier was more prominent, suggesting a deeper look at input reasoning or constraints if such outputs are typical.

Solution Implementation

1from typing import List
2from collections import Counter
3from math import inf
4
5class Solution:
6    def getLargestOutlier(self, nums: List[int]) -> int:
7        # Calculate the sum of all numbers in the list
8        s = sum(nums)
9      
10        # Create a frequency counter for the numbers in the list
11        count = Counter(nums)
12      
13        # Initialize the answer to negative infinity
14        largest_outlier = -inf
15      
16        # Iterate over each unique number and its count in the list
17        for num, freq in count.items():
18            # Calculate the tentative sum removing the current number
19            tentative_sum = s - num
20          
21            # Check if tentative_sum is odd or there is no pair that sums up to half of tentative_sum
22            if tentative_sum % 2 or count[tentative_sum // 2] == 0:
23                continue
24          
25            # Check for the condition of a valid outlier
26            if num != tentative_sum // 2 or freq > 1:
27                # Update the largest outlier if the current number is greater
28                largest_outlier = max(largest_outlier, num)
29      
30        # Return the largest outlier found, default is -inf if none found
31        return largest_outlier
32

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int getLargestOutlier(int[] nums) {
6        int sum = 0;
7        Map<Integer, Integer> countMap = new HashMap<>();
8
9        // Calculate the sum of all elements and count the occurrences of each element
10        for (int number : nums) {
11            sum += number;
12            countMap.merge(number, 1, Integer::sum);
13        }
14
15        // Initialize the answer to the smallest possible value
16        int largestOutlier = Integer.MIN_VALUE;
17
18        // Iterate through each unique element and its count
19        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
20            int key = entry.getKey();
21            int value = entry.getValue();
22
23            // Calculate the target value by subtracting the current key from the sum
24            int target = sum - key;
25
26            // If the target is not divisible by 2 or there is no corresponding element, continue
27            if (target % 2 != 0 || !countMap.containsKey(target / 2)) {
28                continue;
29            }
30
31            // Check the conditions to update the largest outlier
32            if (key != target / 2 || value > 1) {
33                largestOutlier = Math.max(largestOutlier, key);
34            }
35        }
36
37        return largestOutlier;
38    }
39}
40

1class Solution {
2public:
3    int getLargestOutlier(vector<int>& nums) {
4        int totalSum = 0; // Initialize the total sum of all elements
5        unordered_map<int, int> count; // Map to store the frequency of each element
6
7        // Calculate the total sum and populate the frequency map
8        for (int num : nums) {
9            totalSum += num; // Add each number to the total sum
10            count[num]++; // Increment the frequency count for the number
11        }
12
13        int largestOutlier = INT_MIN; // Variable to track the largest outlier found
14
15        // Iterate over each unique number (and its frequency) in the map
16        for (auto [num, frequency] : count) {
17            int remainingSum = totalSum - num; // Calculate the sum excluding the current number
18
19            // Check if remaining sum is divisible by 2 and second condition
20            if (remainingSum % 2 != 0 || !count.contains(remainingSum / 2)) {
21                continue; // Skip if the conditions are not satisfied
22            }
23
24            // Ensure that this number is valid to consider as an outlier
25            if (num != remainingSum / 2 || frequency > 1) {
26                largestOutlier = max(largestOutlier, num); // Update the largest outlier
27            }
28        }
29      
30        return largestOutlier; // Return the largest outlier or INT_MIN if none found
31    }
32};
33

1function getLargestOutlier(nums: number[]): number {
2    // Initialize sum of all numbers
3    let totalSum = 0;
4
5    // Create a frequency map to count occurrences of each number
6    const frequencyMap: Record<number, number> = {};
7
8    // Calculate totalSum and populate frequencyMap
9    for (const num of nums) {
10        totalSum += num;
11        frequencyMap[num] = (frequencyMap[num] || 0) + 1;
12    }
13
14    // Initialize answer with the smallest possible number
15    let largestOutlier = -Infinity;
16
17    // Iterate over each distinct number and its frequency
18    for (const [key, value] of Object.entries(frequencyMap)) {
19        const number = +key; // Convert key back to number
20        const remainingSum = totalSum - number;
21
22        // Check if remainingSum is even and half of it exists in the array
23        if (remainingSum % 2 === 0 && frequencyMap.hasOwnProperty(remainingSum / 2)) {
24          
25            // Check if the current number is not the same as half the remainingSum
26            // or there are at least two occurrences of the number
27            if (number !== remainingSum / 2 || value > 1) {
28                // Update largestOutlier to the maximum found outlier
29                largestOutlier = Math.max(largestOutlier, number);
30            }
31        }
32    }
33
34    return largestOutlier; // Return the largest outlier found
35}
36

Time and Space Complexity

The time complexity of the code is O(n). This results from iterating through the array to compute the sum and another iteration through the Counter dictionary, which also depends on n, the number of elements in the array nums.

The space complexity is O(n), as the Counter stores the frequency of each element in the array, which in the worst case could be all unique elements, thus proportional to n.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know