Neither Minimum nor Maximum
EasyPrompt
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] <= 100- All values in
numsare distinct
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves sorting the entire array first. Once sorted, the minimum element will be at the beginning and the maximum element will be at the end. Any element between these two extremes is a valid answer.
Algorithm
-
- Check if the length of the input array
numsis less than 3. If it is, no such number can exist, so return -1.
- Check if the length of the input array
-
- Sort the array
numsin ascending order.
- Sort the array
-
- After sorting, the minimum element is at
nums[0]and the maximum is atnums[nums.length - 1].
- After sorting, the minimum element is at
-
- Any element between these two is a valid answer. We can simply return
nums[1].
- Any element between these two is a valid answer. We can simply return
Walkthrough
The most straightforward way to solve this problem is to first establish an order among the elements. By sorting the array, we can easily identify the minimum and maximum values.
- First, we handle the edge case: if the array has fewer than three elements, no number can be neither the minimum nor the maximum, so we return -1.
- Then, we use a standard sorting algorithm to sort the input array
numsin non-decreasing order. - After sorting,
nums[0]holds the minimum value andnums[nums.length - 1]holds the maximum value. - Any element at an index
iwhere0 < i < nums.length - 1is guaranteed to be neither the minimum nor the maximum of the array. - We can simply pick the element at index 1,
nums[1], and return it as our answer.
import java.util.Arrays; class Solution { public int findNonMinOrMax(int[] nums) { if (nums.length < 3) { return -1; } Arrays.sort(nums); return nums[1]; }}Complexity
Time
O(N log N) Where N is the number of elements in `nums`. The time complexity is dominated by the sorting step.
Space
O(log N) or O(N) This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires O(log N) space on average for the recursion stack.
Trade-offs
Pros
Very simple to conceptualize and write.
Leverages built-in sorting functions, leading to concise code.
Cons
Inefficient for this specific problem, as sorting the entire array is overkill.
The time complexity of O(N log N) is significantly worse than possible alternatives.
This method avoids the O(N log N) cost of sorting. It works by first finding the minimum and maximum elements in the array in one pass, and then iterating through the array a second time to find a number that is neither of these two.
Algorithm
-
- Handle the edge case: if
nums.lengthis less than 3, return -1.
- Handle the edge case: if
-
- Initialize two variables,
minValandmaxVal, to track the minimum and maximum values.
- Initialize two variables,
-
- Iterate through the array once to find the true
minValandmaxVal.
- Iterate through the array once to find the true
-
- Iterate through the array a second time.
-
- For each element
num, check if it is not equal tominValand not equal tomaxVal.
- For each element
-
- The first element that satisfies this condition is a valid answer, so return it.
Walkthrough
Instead of sorting the whole array, we can find the minimum and maximum values with a single linear scan. Then, we can perform another scan to find an element that matches neither.
- As with the previous approach, we first check if the array size is less than 3 and return -1 if it is.
- We initialize
minValandmaxValwith the first element of the array. - We perform a single pass (the first pass) through the array to find the absolute minimum and maximum values by comparing each element.
- After finding
minValandmaxVal, we perform a second pass through the array. - In this second pass, for each element
num, we check if it is different from bothminValandmaxVal. - The first element that satisfies
num != minVal && num != maxValis a valid answer, and we can return it immediately. - Since the problem guarantees that an answer exists for arrays of length 3 or more, this second loop will always find such a number.
class Solution { public int findNonMinOrMax(int[] nums) { if (nums.length < 3) { return -1; } int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; for (int num : nums) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } for (int num : nums) { if (num != minVal && num != maxVal) { return num; } } return -1; // This line is unreachable for arrays of length >= 3 }}Complexity
Time
O(N) Where N is the number of elements. We iterate through the array twice in the worst case (once to find min/max, once to find the answer), which results in a time complexity of O(N) + O(N) = O(N).
Space
O(1) We only use a constant amount of extra space for variables like `minVal` and `maxVal`.
Trade-offs
Pros
A significant improvement over the sorting approach with O(N) time complexity.
Still relatively easy to understand and implement.
Uses constant extra space.
Cons
Requires two passes over the data, which is less optimal than a single-pass or constant-time solution.
A highly efficient approach that leverages the problem's constraints and the fact that we only need to return any valid number. By considering just the first three elements of the array, we can find a valid answer in constant time.
Algorithm
-
- Check if the array length is less than 3. If so, return -1.
-
- Consider only the first three elements of the array:
nums[0],nums[1], andnums[2].
- Consider only the first three elements of the array:
-
- Among these three distinct numbers, one must be the smallest, one the largest, and one in the middle.
-
- This middle value is guaranteed to be a valid answer because it cannot be the global minimum or maximum of the entire array.
-
- Find this middle value by sorting the three elements and picking the second one, or by using comparisons.
-
- Return the identified middle value.
Walkthrough
The key insight for the optimal solution is that we don't need to inspect the entire array. If an array has three or more distinct elements, a number that is neither the minimum nor the maximum must exist.
-
We can prove that the middle value of any three distinct elements from the array is a valid answer. Let the three elements be
a,b, andc. When sorted, let them bex < y < z. The valueycannot be the global minimum of the entirenumsarray (becausexis smaller), and it cannot be the global maximum (becausezis larger). Therefore,yis a valid answer. -
The algorithm is as follows:
- First, check if the array length is less than 3. If so, return -1.
- Take the first three elements:
nums[0],nums[1], andnums[2]. - Find the middle value among these three. A simple way is to put them in a temporary array of size 3, sort it, and pick the element at index 1.
import java.util.Arrays; class Solution { public int findNonMinOrMax(int[] nums) { if (nums.length < 3) { return -1; } // Create a temporary array with the first three elements int[] firstThree = {nums[0], nums[1], nums[2]}; // Sort the temporary array Arrays.sort(firstThree); // The middle element is a valid answer return firstThree[1]; }}Complexity
Time
O(1) We perform a fixed number of operations (reading 3 elements, sorting an array of size 3) regardless of the size of the input array `N`.
Space
O(1) We use a constant amount of extra space, for instance, to hold the three elements in a temporary array of fixed size 3.
Trade-offs
Pros
Optimal solution with O(1) time complexity.
Extremely fast, as it only examines a fixed number of elements regardless of the input size.
Cons
The logic relies on a specific insight that might not be immediately obvious.
It only works because the problem asks for any valid number, not a specific one.
Solutions
Solution
class Solution {public int findNonMinOrMax(int[] nums) { int mi = 100, mx = 0; for (int x : nums) { mi = Math.min(mi, x); mx = Math.max(mx, x); } for (int x : nums) { if (x != mi && x != mx) { return x; } } return -1; }}class Solution {public: int findNonMinOrMax(vector<int> &nums) { int mi = *min_element(nums.begin(), nums.end()); int mx = *max_element(nums.begin(), nums.end()); for (int x : nums) { if (x != mi && x != mx) { return x; } } return -1; }};class Solution: def findNonMinOrMax( self, nums: List[int]) -> int: return - 1 if len(nums) < 3 else sorted(nums)[1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.