LeetCode Problem 3194

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Sorting

Solution

LeetCode 3194 - Minimum Average of Smallest and Largest Elements

Problem Understanding

The problem gives us an even-length integer array nums. We repeatedly perform the following operation until the array becomes empty:

1. Remove the smallest element.
2. Remove the largest element.
3. Compute their average.
4. Store that average in another array called averages.

After all pairs have been processed, we return the minimum value that appeared in averages.

In simpler terms, after sorting the array, we always pair the smallest remaining number with the largest remaining number. For every pair, we compute:

$$\frac{\text{smallest} + \text{largest}}{2}$$

Among all these averages, we must return the smallest one.

The constraints are very small:

• 2 <= nums.length <= 50
• The array length is always even.
• Each value is between 1 and 50.

These constraints tell us that performance is not a major concern. Even less efficient solutions would pass comfortably. However, the problem is designed to test understanding of sorting and two pointer techniques.

An important observation is that the problem guarantees an even number of elements, so every element can always be paired. We never need to handle leftover elements.

Several edge cases are worth considering:

• Arrays with only two elements.
• Arrays where all numbers are equal.
• Arrays with repeated minimum or maximum values.
• Arrays where the minimum average occurs late in the process instead of early.

A naive implementation could repeatedly search for minimum and maximum elements and physically remove them from the array, but there is a cleaner and more efficient way.

Approaches

Brute Force Approach

The brute force solution directly simulates the process exactly as described.

At every step:

1. Find the smallest element.
2. Find the largest element.
3. Remove both from the array.
4. Compute their average.
5. Track the minimum average seen so far.

Since removing elements from a list or array is expensive, each operation may require shifting elements. Additionally, repeatedly searching for minimum and maximum values costs linear time.

Although this works correctly because it follows the problem statement exactly, it is inefficient compared to a sorting-based solution.

Optimal Approach

The key insight is that after sorting the array, the smallest remaining element is always at the left side, and the largest remaining element is always at the right side.

Instead of repeatedly searching and deleting elements, we can:

1. Sort the array once.
2. Use two pointers:

• left starts at the beginning.
• right starts at the end.

3. Pair nums[left] with nums[right].
4. Compute the average.
5. Move both pointers inward.

This avoids repeated searches and deletions entirely.

Because the array is sorted, every iteration naturally gives us the current minimum and maximum remaining elements.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly searches and removes min/max elements
Optimal	O(n log n)	O(1) or O(log n) depending on sorting implementation	Sort once, then use two pointers

Algorithm Walkthrough

Optimal Algorithm

1. Sort the array in non-decreasing order.

Sorting ensures the smallest values are on the left and the largest values are on the right. 2. Initialize two pointers.

Set:

• left = 0
• right = len(nums) - 1

These pointers represent the smallest and largest remaining elements. 3. Initialize the answer.

Start with a very large value such as positive infinity. This variable will store the minimum average encountered. 4. Process pairs while left < right.

At every iteration:

• Compute the average:

$$\frac{nums[left] + nums[right]}{2}$$

• Update the minimum answer if this average is smaller.
• Move left one step right.
• Move right one step left.

5. Return the minimum average.

After processing all pairs, the stored minimum value is the answer.

Why it works

After sorting, the smallest remaining element is always at the left pointer and the largest remaining element is always at the right pointer. Moving inward after each pairing exactly simulates the process described in the problem statement. Since every valid pair is processed once and every average is considered, the minimum recorded average must be correct.

Python Solution

from typing import List

class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        nums.sort()

        left = 0
        right = len(nums) - 1

        minimum_average = float("inf")

        while left < right:
            current_average = (nums[left] + nums[right]) / 2

            minimum_average = min(minimum_average, current_average)

            left += 1
            right -= 1

        return minimum_average

The implementation begins by sorting the array so that the smallest and largest remaining elements can always be accessed directly.

Two pointers are then initialized. The left pointer starts at the beginning of the sorted array, while the right pointer starts at the end.

Inside the loop, the code computes the average of the current smallest and largest elements. The result is compared against the current minimum average.

After processing the pair, both pointers move inward to represent removing those elements from consideration.

The loop continues until all pairs have been processed, and the smallest average found is returned.

Go Solution

package main

import (
	"math"
	"sort"
)

func minimumAverage(nums []int) float64 {
	sort.Ints(nums)

	left := 0
	right := len(nums) - 1

	minimumAverage := math.Inf(1)

	for left < right {
		currentAverage := float64(nums[left]+nums[right]) / 2.0

		if currentAverage < minimumAverage {
			minimumAverage = currentAverage
		}

		left++
		right--
	}

	return minimumAverage
}

The Go implementation follows the same logic as the Python version.

The array is sorted using sort.Ints. Since Go distinguishes between integers and floating point values, explicit conversion to float64 is necessary before division. Using 2.0 ensures floating point division instead of integer division.

Go slices are used directly, and no additional arrays are required.

Worked Examples

Example 1

Input:

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

After sorting:

[1,3,4,4,7,8,13,15]

Step	left value	right value	Average	Minimum So Far
1	1	15	8.0	8.0
2	3	13	8.0	8.0
3	4	8	6.0	6.0
4	4	7	5.5	5.5

Final answer:

5.5

Example 2

Input:

nums = [1,9,8,3,10,5]

After sorting:

[1,3,5,8,9,10]

Step	left value	right value	Average	Minimum So Far
1	1	10	5.5	5.5
2	3	9	6.0	5.5
3	5	8	6.5	5.5

Final answer:

5.5

Example 3

Input:

nums = [1,2,3,7,8,9]

After sorting:

[1,2,3,7,8,9]

Step	left value	right value	Average	Minimum So Far
1	1	9	5.0	5.0
2	2	8	5.0	5.0
3	3	7	5.0	5.0

Final answer:

5.0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on the sorting implementation

The main cost comes from sorting the array. After sorting, the two pointer traversal processes each pair exactly once, which takes linear time.

The algorithm itself uses only a few extra variables. However, the underlying sorting implementation may use additional stack space internally.

Test Cases

from typing import List

class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        nums.sort()

        left = 0
        right = len(nums) - 1

        minimum_average = float("inf")

        while left < right:
            current_average = (nums[left] + nums[right]) / 2
            minimum_average = min(minimum_average, current_average)

            left += 1
            right -= 1

        return minimum_average

solution = Solution()

assert solution.minimumAverage([7,8,3,4,15,13,4,1]) == 5.5  # Example 1
assert solution.minimumAverage([1,9,8,3,10,5]) == 5.5       # Example 2
assert solution.minimumAverage([1,2,3,7,8,9]) == 5.0        # Example 3

assert solution.minimumAverage([1,100]) == 50.5             # Smallest valid input
assert solution.minimumAverage([5,5,5,5]) == 5.0            # All elements equal
assert solution.minimumAverage([1,1,1,10,10,10]) == 5.5     # Repeated extremes
assert solution.minimumAverage([2,4,6,8]) == 5.0            # Evenly spaced values
assert solution.minimumAverage([1,2,50,51]) == 26.0         # Two pairs with same average
assert solution.minimumAverage([1,50,2,49,3,48]) == 25.5    # Multiple decreasing averages

Test Summary

Test	Why
[7,8,3,4,15,13,4,1]	Verifies the first official example
[1,9,8,3,10,5]	Verifies the second official example
[1,2,3,7,8,9]	Verifies equal averages across all pairs
[1,100]	Smallest possible valid input
[5,5,5,5]	All values identical
[1,1,1,10,10,10]	Repeated minimum and maximum values
[2,4,6,8]	Standard balanced pairing
[1,2,50,51]	Multiple pairs producing equal averages
[1,50,2,49,3,48]	Ensures minimum may occur later in processing

Edge Cases

Minimum Input Size

The smallest valid array contains exactly two elements. In this case, there is only one pair and therefore only one average. A buggy implementation might incorrectly assume multiple iterations are required. The two pointer solution handles this naturally because the loop executes exactly once.

All Elements Equal

If every element is identical, every computed average will also be identical. Some implementations may unnecessarily track multiple values or accidentally introduce floating point inconsistencies. Since this solution directly computes each average using floating point division, all results remain correct and equal.

Duplicate Minimum or Maximum Values

Arrays may contain repeated smallest or largest elements. A brute force implementation that removes elements incorrectly could accidentally remove too many duplicates. The sorted two pointer approach avoids this issue because each index is processed exactly once.

Minimum Average Appears Late

The smallest average is not guaranteed to appear during the first pairing. For example:

[1,50,2,49,3,48]

produces averages:

24.5, 25.5, 26.0

A flawed implementation that returns early would fail here. This solution processes every pair and tracks the minimum throughout the entire traversal.