Identify the Largest Outlier in an Array - Practice Coding Problems

Identify the Largest Outlier in an Array - 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 potential outlier in nums.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,5,10]

› Output: 10

💡 Note: Array has n=4 elements, so n-2=2 special numbers. If outlier=10, remaining=[2,3,5]. Sum of specials should equal sum element: 2+3=5, and 5 exists. So 10 is valid outlier.

Example 2 — Multiple Valid Outliers

$ Input: nums = [-2,-1,-3,-6,4]

› Output: 4

💡 Note: If outlier=4, remaining=[-2,-1,-3,-6]. Sum of [-2,-1,-3]=-6, and -6 exists. If outlier=-1, remaining=[-2,-3,-6,4]. Sum of [-2,-3]=-5, but -5 doesn't exist. So 4 is the largest valid outlier.

Example 3 — Edge Case with Duplicates

$ Input: nums = [1,1,1]

› Output: 1

💡 Note: With n=3, need n-2=1 special number. If outlier=1 (index 0), remaining=[1,1]. Sum of 1 special = 1, sum element = 1. Valid configuration exists.

Constraints

3 ≤ nums.length ≤ 10⁵
-1000 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with n-2 specials, 1 sum, 1 outlier

Test Each Element

Check if element can be outlier by validating remaining

Find Maximum

Return largest valid outlier

Key Takeaway

🎯 Key Insight: For each potential outlier, remaining elements must perfectly split into specials and their sum

Asked in

a Amazon 25 M Microsoft 20

The key insight is that for each potential outlier, the remaining elements must split into exactly n-2 special numbers and 1 sum element where the sum element equals the sum of all special numbers. Best approach uses frequency counting for efficient validation. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(n³)	O(1)	Try each element as outlier and check if remaining elements can form valid special+sum groups
Frequency Count Optimization	O(n²)	O(n)	Use frequency map to efficiently validate potential outliers

Brute Force Enumeration — Algorithm Steps

Step 1: Try each element as potential outlier
Step 2: Calculate total sum of remaining n-1 elements
Step 3: Check if any remaining element equals sum of the other n-2 elements
Step 4: Track the largest valid outlier

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Outlier

Select element to test as outlier

Test Remaining

Check if remaining elements can form valid special+sum pair

Find Maximum

Track largest valid outlier found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int n) {
    int maxOutlier = INT_MIN;
    
    // Try each element as potential outlier
    for (int i = 0; i < n; i++) {
        int outlier = nums[i];
        int totalRemaining = 0;
        
        // Calculate sum of remaining elements
        for (int k = 0; k < n; k++) {
            if (k != i) {
                totalRemaining += nums[k];
            }
        }
        
        // Try each remaining element as potential sum
        for (int j = 0; j < n; j++) {
            if (j != i) {
                int potentialSum = nums[j];
                int specialsSum = totalRemaining - potentialSum;
                
                // Check if this configuration is valid
                if (potentialSum == specialsSum && n - 2 == n - 2) {
                    if (outlier > maxOutlier) {
                        maxOutlier = outlier;
                    }
                    break;
                }
            }
        }
    }
    
    return maxOutlier;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int nums[1000];
    int n = 0;
    char* ptr = line + 1; // Skip '['
    
    while (*ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        nums[n++] = atoi(ptr);
        while (*ptr != ',' && *ptr != ']') ptr++;
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n elements as outlier, we check n-1 elements as potential sum, each requiring O(n) validation

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for tracking, no extra data structures

✓ Linear Space

35.6K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler