Neither Minimum nor Maximum — Solution in Python, Java & C++
Neither Minimum nor Maximum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Neither Minimum nor Maximum is an easy coding problem on arrays and sorting, asked in Amazon, Google and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting
- Asked at: Amazon, Google, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums holds distinct positive integers. Return the smallest number in it that is neither the minimum nor the maximum of the array.
If no such number exists, return -1.
Example 1
Input: nums = [3,2,1,4]
Output: 2
Explanation: The minimum is 1 and the maximum 4; the smallest of what is left is 2.
Example 2
Input: nums = [1,2]
Output: -1
Explanation: Every element is either the minimum or the maximum.
Example 3
Input: nums = [2,1,3]
Output: 2
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 100All values of nums are distinct.Among the qualifying numbers, the smallest is returned.
Hints for Neither Minimum nor Maximum
Hint 1
With fewer than three distinct values there is nothing left over.
Hint 2
Find the minimum and the maximum in one pass.
Hint 3
Then take the smallest value that is neither.
How to solve Neither Minimum nor Maximum
Find the extremes, then scan again for the smallest value that is neither.
Approach
- Return
-1immediately when the array is shorter than three. - Find the minimum and maximum.
- Scan for the smallest value different from both.
Why it works
Distinctness is what makes the two-pass approach exact: with repeats, a value equal to the minimum might still be a different element, and the != test would wrongly exclude it. Sorting and reading index 1 is the classic one-liner, but the two passes are linear.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Arrays of length 1 or 2 always answer
-1. - Returning the second element of the unsorted array is not the same as the second smallest.
- The problem asks for a value, not an index.
Reference solution
Python
from typing import List
def findNonMinOrMax(nums: List[int]) -> int:
if len(nums) < 3:
return -1
mn, mx = min(nums), max(nums)
rest = [v for v in nums if v != mn and v != mx]
return min(rest) if rest else -1Java
public static int findNonMinOrMax(int[] nums) {
if (nums.length < 3) return -1;
int mn = nums[0], mx = nums[0];
for (int v : nums) {
mn = Math.min(mn, v);
mx = Math.max(mx, v);
}
int best = -1;
for (int v : nums) {
if (v == mn || v == mx) continue;
if (best < 0 || v < best) best = v;
}
return best;
}C++
int findNonMinOrMax(vector<int>& nums) {
if (nums.size() < 3) return -1;
int mn = *min_element(nums.begin(), nums.end());
int mx = *max_element(nums.begin(), nums.end());
int best = -1;
for (int v : nums) {
if (v == mn || v == mx) continue;
if (best < 0 || v < best) best = v;
}
return best;
}JavaScript
var findNonMinOrMax = function(nums) {
if (nums.length < 3) return -1;
var mn = nums[0], mx = nums[0], i;
for (i = 1; i < nums.length; i++) {
if (nums[i] < mn) mn = nums[i];
if (nums[i] > mx) mx = nums[i];
}
var best = -1;
for (i = 0; i < nums.length; i++) {
if (nums[i] === mn || nums[i] === mx) continue;
if (best < 0 || nums[i] < best) best = nums[i];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms