Minimum Average of Smallest and Largest Elements

Minimum Average of Smallest and Largest Elements - Problem

You have an array of floating point numbers averages which is initially empty. You are given an array nums of n integers where n is even.

You repeat the following procedure n / 2 times:

Remove the smallest element, minElement, and the largest element maxElement, from nums.
Add (minElement + maxElement) / 2 to averages.

Return the minimum element in averages.

Input & Output

Example 1 — Basic Case

$ Input: nums = [7,8,3,4,15,13,4,1]

› Output: 5.5

💡 Note: After sorting: [1,3,4,4,7,8,13,15]. Pairs: (1,15)→8.0, (3,13)→8.0, (4,8)→6.0, (4,7)→5.5. Minimum average is 5.5.

Example 2 — Even Distribution

$ Input: nums = [1,9,8,2,3,7]

› Output: 5.0

💡 Note: After sorting: [1,2,3,7,8,9]. Pairs: (1,9)→5.0, (2,8)→5.0, (3,7)→5.0. All averages are 5.0, so minimum is 5.0.

Example 3 — Minimum Size

$ Input: nums = [1,2]

› Output: 1.5

💡 Note: Only one pair possible: (1,2) with average (1+2)/2 = 1.5.

Constraints

2 ≤ nums.length ≤ 10⁵
nums.length is even
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of even length integers

Pair Extremes

Repeatedly pair smallest with largest

Find Minimum

Return minimum average computed

Key Takeaway

🎯 Key Insight: Sorting allows us to efficiently pair minimum and maximum elements using two pointers, avoiding repeated searches.

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to sort the array first, then use two pointers to efficiently pair minimum and maximum elements. The optimal approach sorts once O(n log n) then tracks the minimum average directly without extra storage. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Direct Minimum Tracking	O(n log n)	O(1)	Sort once and track minimum average without storing all averages
Brute Force - Repeated Min/Max Finding	O(n³)	O(n)	Find min and max by scanning array repeatedly for each pairing
Sort First - Two Pointers	O(n log n)	O(n)	Sort array once, then use two pointers from ends to pair min/max efficiently

Optimized - Direct Minimum Tracking — Algorithm Steps

Step 1: Sort the array in ascending order
Step 2: Initialize minimum average to infinity
Step 3: Use two pointers to pair min/max elements
Step 4: Update minimum average for each pair
Step 5: Return the tracked minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Initialize

Sort array and set minAvg = ∞

Compute & Compare

Calculate each average and update minimum

Result

Return tracked minimum value

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

double solution(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    double minAvg = DBL_MAX;
    
    int left = 0, right = numsSize - 1;
    while (left < right) {
        double avg = (nums[left] + nums[right]) / 2.0;
        if (avg < minAvg) {
            minAvg = avg;
        }
        left++;
        right--;
    }
    
    return minAvg;
}

int main() {
    // Simple parsing for array input
    int nums[1000];
    int size = 0;
    
    scanf("%*c"); // Skip '['
    while (1) {
        int num;
        scanf("%d", &num);
        nums[size++] = num;
        
        char c;
        scanf("%c", &c);
        if (c == ']') break;
    }
    
    double result = solution(nums, size);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Dominated by sorting step, then O(n) for two-pointer pairing

⚡ Linearithmic

Space Complexity

O(1)

Only storing minimum value, no extra arrays needed (excluding sorting space)

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 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

Optimized - Direct Minimum Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler