Neither Minimum nor Maximum

Difficulty: Easy | Acceptance: 76.40% | Paid: No Topics: Array, Sorting

Given an integer array nums containing distinct positive integers, find a number that is neither the minimum nor the maximum value in the array.

Return the number if it exists, otherwise return -1.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Linear Scan

Examples

Example 1

Input: nums = [3,2,1,4]
Output: 2
Explanation: 2 is neither the minimum (1) nor the maximum (4) in the array.

Example 2

Input: nums = [1,2]
Output: -1
Explanation: Since the array length is less than 3, there is no number that is neither minimum nor maximum.

Example 3

Input: nums = [2,1,3]
Output: 2
Explanation: 2 is neither the minimum (1) nor the maximum (3) in the array.

Constraints

3 <= nums.length <= 100
1 <= nums[i] <= 100
All the integers of nums are distinct.

Sorting

Intuition Since the array contains distinct integers, sorting the array places the minimum at the beginning and the maximum at the end. Any element in between (specifically the second element) is guaranteed to be neither the minimum nor the maximum.

Steps

• Sort the array in non-decreasing order.
• If the length of the array is less than 3, return -1.
• Return the element at index 1 (the second element).

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

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on sorting implementation.
• Notes: Sorting is simple but not the most time-efficient.

Linear Scan

Intuition We can find the minimum and maximum values in a single pass. Then, we iterate through the array again to find the first element that is not equal to the minimum or maximum. Since the array has distinct elements and length >= 3, such an element must exist.

Steps

• Initialize min and max variables.
• Iterate through the array to find the global minimum and maximum.
• Iterate through the array again. If an element is not equal to min and not equal to max, return it.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the optimal time complexity solution.