We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Identify the Largest Outlier in an Array

Number: 3594

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Goldman Sachs

Problem Description

Given an integer array nums, exactly n - 2 of its elements are considered as "special numbers". One of the other two elements represents the sum of all these special numbers, and the remaining element is called the "outlier". An outlier is a number that is neither one of the original special numbers nor the sum element. The task is to identify and return the largest potential outlier from the array.

Key Insights

  • The total sum of the array, S, can be represented as S = 2 * (sum of special numbers) + outlier.
  • For any candidate special sum element x (which is one of the numbers in nums), the outlier can be computed as outlierCandidate = S - 2*x.
  • To be valid, outlierCandidate must appear elsewhere in the array with a distinct index. If x equals outlierCandidate, it must occur at least twice.
  • By evaluating every possible candidate x from the array, we can determine all valid outlier candidates and select the largest one.

Space and Time Complexity

Time Complexity: O(n) — We traverse the array once to compute the total sum and build a frequency map, and then iterate over at most O(n) distinct elements. Space Complexity: O(n) — We use a hash table (frequency map) that in the worst-case stores all n elements.

Solution

We start by computing the total sum S of the array and build a frequency map to know the occurrences of each number. For every distinct number x in the map (acting as a potential candidate for the special sum), we compute outlierCandidate = S - 2*x. To validate this candidate:

  • If outlierCandidate is different from x, we simply check if it exists in the frequency map.
  • If outlierCandidate is the same as x, we ensure that it appears at least twice (at different indices) in the array. We collect all valid outlier candidates and then return the largest among them. This approach leverages the frequency map for efficient lookups and requires only linear passes through the data.

Code Solutions

# Calculate the total sum and frequency of each element in the array
def findLargestOutlier(nums):
    total_sum = sum(nums)  # Total sum of the array
    freq = {}             # Dictionary to hold frequency of each element
    for num in nums:
        freq[num] = freq.get(num, 0) + 1

    largest_outlier = None

    # Iterate over each distinct number as a candidate for special sum
    for candidate in freq:
        outlier_candidate = total_sum - 2 * candidate  # Compute potential outlier

        # Check validity: if candidate is outlier_candidate, ensure at least 2 occurrences
        if outlier_candidate == candidate:
            if freq[candidate] < 2:
                continue
        # Else outlier_candidate must exist in the frequency map
        elif outlier_candidate not in freq:
            continue

        # Track the largest valid outlier candidate
        if largest_outlier is None or outlier_candidate > largest_outlier:
            largest_outlier = outlier_candidate

    return largest_outlier

# Example usage:
print(findLargestOutlier([2,3,5,10]))  # Expected: 10
print(findLargestOutlier([-2,-1,-3,-6,4]))  # Expected: 4
print(findLargestOutlier([1,1,1,1,1,5,5]))  # Expected: 5
← Back to All Questions