Watch 10 video solutions for Neither Minimum nor Maximum, a easy level problem involving Array, Sorting. This walkthrough by CodeJulian has 526 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |