LeetCode 2733 - Neither Minimum nor Maximum

LeetCode Problem 2733

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem asks us to select a number from an array of distinct positive integers such that the chosen number is neither the minimum nor the maximum in the array. In other words, we must return a number that lies strictly between the smallest and largest elements. If all numbers are either the minimum or maximum (for example, in an array of size 2), we must return -1.

The input nums is a list of integers with size ranging from 1 to 100, and each integer is between 1 and 100. Since all numbers are distinct, there are no duplicates to consider. The constraints guarantee that we never have repeated elements, which simplifies determining the minimum and maximum values.

Important edge cases include arrays of size 1 or 2, where it is impossible to find a number that is neither minimum nor maximum. Arrays with size 3 or more will always have at least one valid number that satisfies the condition.

Approaches

The brute-force approach involves first finding the minimum and maximum values in the array and then iterating through all elements to select any number that is neither. This approach works correctly but iterates through the array twice: once to find min/max and once to select the number.

The key observation for the optimal approach is that since we only need any number that is neither min nor max, we can leverage sorting. After sorting, the first element is the minimum, the last element is the maximum, and any element in between is a valid answer. Sorting allows us to access a valid element immediately without scanning the array multiple times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Find min and max with two passes, then select a number
Optimal (Sorting)	O(n log n)	O(1) or O(n) depending on sort implementation	Sort array and select middle element

For arrays of size ≤ 100, the difference between O(n) and O(n log n) is negligible. However, the brute-force method is slightly more efficient and simpler in practice for this problem size.

Algorithm Walkthrough

1. Check if the length of nums is less than 3. If so, return -1 immediately since no number can be strictly between min and max.
2. Initialize two variables, min_val and max_val, to store the minimum and maximum values of the array. Iterate through nums to find these values.
3. Iterate through nums again. For each number, check if it is strictly greater than min_val and strictly less than max_val.
4. Return the first number that satisfies the above condition.
5. If no such number is found after iterating through the array, return -1.

Why it works: This works because the problem guarantees distinct elements. Any number that is not the global minimum or maximum is guaranteed to be strictly between the two. By scanning the array, we ensure correctness, and by returning the first such number, we satisfy the requirement of returning any valid number.

Python Solution

from typing import List

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1

        min_val = min(nums)
        max_val = max(nums)

        for num in nums:
            if num != min_val and num != max_val:
                return num

        return -1

This Python implementation first handles the edge case of arrays with fewer than three elements. It then uses the built-in min and max functions to find the extreme values and iterates through the array to return the first valid element. If none exists, it returns -1.

Go Solution

func findNonMinOrMax(nums []int) int {
    if len(nums) < 3 {
        return -1
    }

    minVal := nums[0]
    maxVal := nums[0]
    for _, num := range nums {
        if num < minVal {
            minVal = num
        }
        if num > maxVal {
            maxVal = num
        }
    }

    for _, num := range nums {
        if num != minVal && num != maxVal {
            return num
        }
    }

    return -1
}

In Go, we explicitly iterate to find the minimum and maximum since there are no built-in min or max functions for slices. The rest of the logic mirrors the Python version, iterating to find a valid element.

Worked Examples

Example 1: nums = [3,2,1,4]

Step	min_val	max_val	num checked	Result
1	1	4	3	3 is neither min nor max → return 3

Example 2: nums = [1,2]

Step	min_val	max_val	num checked	Result
1	1	2	-	Length < 3 → return -1

Example 3: nums = [2,1,3]

Step	min_val	max_val	num checked	Result
1	1	3	2	2 is neither min nor max → return 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to find min/max, another pass to find a valid element
Space	O(1)	Only a few variables are used, no additional data structures

The complexity is efficient given the constraints (array length ≤ 100). Sorting would increase time to O(n log n) unnecessarily.

Test Cases

# Provided examples
assert Solution().findNonMinOrMax([3,2,1,4]) in [2,3]  # typical case
assert Solution().findNonMinOrMax([1,2]) == -1        # array too small
assert Solution().findNonMinOrMax([2,1,3]) == 2       # middle element is valid

# Boundary cases
assert Solution().findNonMinOrMax([1]) == -1           # single element
assert Solution().findNonMinOrMax([100,1,50]) == 50   # numbers at extremes

# Larger case
assert Solution().findNonMinOrMax(list(range(1,101))) == 2  # any middle number valid

Test	Why
[3,2,1,4]	Normal case with multiple candidates
[1,2]	Array too small to have a valid number
[2,1,3]	Exact three-element array, middle is valid
[1]	Single element edge case
[100,1,50]	Checks handling of extremes
range(1,101)	Stress test with largest allowed array

Edge Cases

Edge Case 1: Array of size 1

An array with only one element cannot have a number strictly between min and max. The implementation returns -1 immediately to handle this.

Edge Case 2: Array of size 2

Two-element arrays also have no numbers strictly between min and max. The algorithm checks for array length < 3 at the start and returns -1.

Edge Case 3: Numbers at the extreme ends of the allowed range

Arrays containing values like 1 and 100 test whether the algorithm correctly identifies min and max. Since the code uses explicit comparisons or built-in functions, it correctly isolates numbers between these extremes.