Given an integer array nums containing distinct positive integers, find and return any number from the array that is neither the minimum nor the maximum value in the array, or -1 if there is no such number.
Return the selected integer.
Example 1:
Input: nums = [3,2,1,4] Output: 2 Explanation: In this example, the minimum value is 1 and the maximum value is 4. Therefore, either 2 or 3 can be valid answers.
Example 2:
Input: nums = [1,2] Output: -1 Explanation: Since there is no number in nums that is neither the maximum nor the minimum, we cannot select a number that satisfies the given condition. Therefore, there is no answer.
Example 3:
Input: nums = [2,1,3] Output: 2 Explanation: Since 2 is neither the maximum nor the minimum value in nums, it is the only valid answer.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100nums are distinctProblem Overview: You receive an integer array nums. Return any value that is neither the smallest nor the largest element in the array. If no such value exists (for example when the array has fewer than three elements), return -1. The task mainly checks basic reasoning about ordering inside an array.
Approach 1: Simple Traversal (O(n) time, O(1) space)
Scan the array once to compute the global min and max. After that, iterate through the array again and return the first value that is not equal to either of those extremes. The key observation: any element strictly between the minimum and maximum satisfies the requirement. This approach only uses constant variables and two linear passes, so the complexity stays O(n) time with O(1) extra space.
An even tighter variation looks only at the first three elements. Among three numbers, one must be the minimum, one the maximum, and the remaining value is guaranteed to be neither. Compare the three values and return the middle element. Both variants rely purely on comparisons and simple iteration, which makes them ideal when you want the fastest possible solution without modifying the array.
Approach 2: Sort and Select (O(n log n) time, O(1) or O(n) space depending on sort)
Another straightforward strategy is to sort the array using a standard sorting algorithm. After sorting, the smallest element sits at index 0 and the largest at index n-1. Any element between them (for example nums[1]) is guaranteed to be neither minimum nor maximum when n ≥ 3. The implementation becomes trivial: sort the array and return the element at index 1.
The tradeoff is complexity. Sorting costs O(n log n) time, which is slower than a linear scan. Some languages also allocate additional memory during sorting, increasing space usage. However, this approach is still practical when the array is already sorted or when sorting is required for later steps in the algorithm.
Recommended for interviews: The simple traversal approach is what interviewers expect. It demonstrates that you recognize the problem only needs comparisons and not full ordering. The sorting solution works but performs unnecessary work. Showing the linear O(n) idea proves stronger algorithmic judgment and familiarity with common array manipulation patterns.
This approach involves finding the minimum and maximum values of the array and then traversing the array to find any number that isn't either the minimum or the maximum. If such a number is found, return it; otherwise, return -1.
The code starts by initializing 'min' and 'max' as the first element. Then it traverses the array to find the actual minimum and maximum values. After that, it traverses the array again to find any element that is neither the minimum nor the maximum. If found, it is returned; otherwise, -1 is returned.
Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1) as no extra space is used apart from variables.
Sorting the array and selecting the second element after sorting can also help find a number that is neither the minimum nor the maximum.
This C solution sorts the array and returns the second element since the sorted array guarantees that position one isn't the min or max if array size is at least 3.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) (ignores sort's possible stack space).
First, we find the minimum and maximum values in the array, denoted as mi and mx respectively. Then, we traverse the array and find the first number that is not equal to mi and not equal to mx, and return it.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
| Approach | Complexity |
|---|---|
| Simple Traversal | Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1) as no extra space is used apart from variables. |
| Sort and Select | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) (ignores sort's possible stack space). |
| Simulation | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Traversal (Find Min and Max) | O(n) | O(1) | Best general solution when you only need any non-min/non-max element |
| Three-Element Comparison | O(1) | O(1) | Fastest trick when the array has at least three elements and you only inspect the first three values |
| Sort and Select | O(n log n) | O(1) to O(n) | Useful if the array is already being sorted for another step |
LeetCode#2733 Neither Minimum nor Maximum - Python • CodeJulian • 526 views views
Watch 9 more video solutions →Practice Neither Minimum nor Maximum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor