2733. Neither Minimum nor Maximum
Problem Description
The problem presents us with an integer array called nums
, which contains distinct positive integers. This means that all the elements in the array are unique and greater than zero. The task is to identify a number in this array that is neither the smallest (minimum) nor the largest (maximum) value present. If such a number exists, it should be returned as the output. If no such number can be found, which would likely be the case if the array has too few elements to have a middle value, then the function should return -1
.
The problem specifies that the function should return any such "middle" value. This means that if there are multiple numbers satisfying the condition of being neither the minimum nor the maximum, any one of them can be chosen as the correct answer.
Intuition
To solve this problem, we can follow a straightforward approach. Since we are given that all the numbers in the array are distinct, we know that there will be one unique minimum value and one unique maximum value.
The first step is to find these two values, the smallest and the largest number in the array, which we can do efficiently by using the min
and max
functions respectively.
Once we have the smallest and largest values, we can then iterate through the array to find an element that is neither of these. As soon as we find such an element, we can return it, since the problem does not require us to do anything other than find one such 'middle' number.
- We use a loop to check each number.
- For each number, if it is not equal to the minimum and not equal to the maximum, we have found a valid "middle" number and we return it immediately.
- If the loop completes without finding such an element, this means that all elements are either the minimum or the maximum, and we return
-1
as per the problem's instructions.
This approach ensures that we look at each element of the array at most once, making the solution efficient and straightforward.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution uses a very basic algorithmic approach with simple control structures. No advanced data structures or design patterns are required, just the built-in Python list and the straightforward use of the min
and max
functions.
The core parts of the solution can be broken down as follows:
- Finding the Minimum and Maximum: We first find the smallest (
mi
) and largest (mx
) numbers in the array using themin(nums)
andmax(nums)
functions. These functions traverse the array, and each one completes inO(n)
time wheren
is the number of elements in the array.
mi, mx = min(nums), max(nums)
- Iterating Through the Array: Next, we iterate through each element
x
in the arraynums
. This is done using a for loop.
for x in nums:
- Checking the Condition: In each iteration, we check if the current element
x
is not equal to the minimum valuemi
and not equal to the maximum valuemx
.
if x != mi and x != mx:
- Returning the Middle Value: If
x
is neither the minimum nor maximum, we have found a valid number that fits the problem's criteria, and we can return it immediately.
return x
- Returning -1 If No Number Found: If we go through the entire array without finding a number that satisfies the condition, it implies that no such number exists (for example, the array might only contain the minimum and maximum values). In that case, after the loop concludes, we return
-1
.
return -1
This algorithm is linear in nature since it involves a single pass through the array to find min
and max
and another pass to find a non-minimum and non-maximum element. Hence, the overall time complexity is O(n)
because the array is traversed at most twice.
Note: The assumption is that the input array nums
provided to the solution function is valid as per the problem description and contains distinct positive integers only.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example:
Assume our input array nums
is [3, 1, 4, 2]
.
-
Finding the Minimum and Maximum: We find the smallest number (
mi
) is1
and the largest number (mx
) is4
.mi, mx = min(nums), max(nums) # mi = 1, mx = 4
-
Iterating Through the Array: We iterate through each element
x
in the array[3, 1, 4, 2]
, using a for loop. -
Checking the Condition:
- First iteration:
x = 3
,x != mi
isTrue
, andx != mx
is alsoTrue
. Since both conditions are satisfied, we have found a "middle" number.
for x in nums: if x != mi and x != mx: return x
- First iteration:
-
Returning the Middle Value: We return
3
immediately because it satisfies the condition of being neither the minimum nor the maximum value in the array.
In this case, the function would have returned 3
on the first iteration, illustrating that the algorithm efficiently finds a number that is neither the smallest nor the largest in the array without needing to check the rest of the elements. If the array had been [2, 1]
, the loop would have completed without finding a suitable middle number, so the function would return -1
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findNonMinOrMax(self, nums: List[int]) -> int:
5 """
6 This method returns the first element from the input list 'nums'
7 that is not the minimum or maximum value in the list.
8 If all elements are the minimum or maximum, -1 is returned.
9
10 :param nums: List[int] - List of integers to search through
11 :return: int - The first non-minimum and non-maximum value, or -1 if not found
12 """
13
14 # Find the minimum and maximum values in the list
15 min_value, max_value = min(nums), max(nums)
16
17 # Iterate over the list to find an element that is not minimum or maximum
18 for num in nums:
19 if num != min_value and num != max_value:
20 return num # Return the first non-min/max number
21
22 # If all elements are the same (i.e., min equals max), return -1
23 return -1
24
1class Solution {
2 // Method to find an element which is neither the minimum nor the maximum in the array.
3 public int findNonMinOrMax(int[] nums) {
4 // Initialize minimum and maximum with extreme values which are beyond
5 // the expected range of elements in the array.
6 int minimum = Integer.MAX_VALUE;
7 int maximum = Integer.MIN_VALUE;
8
9 // Loop through all elements in the array to find the minimum and maximum values.
10 for (int num : nums) {
11 minimum = Math.min(minimum, num);
12 maximum = Math.max(maximum, num);
13 }
14
15 // Loop through the array again to find an element that is not equal to
16 // the minimum or maximum value.
17 for (int num : nums) {
18 if (num != minimum && num != maximum) {
19 return num; // Return the first non min/max element found.
20 }
21 }
22
23 // If all elements are either min or max or there's only one element, return -1.
24 return -1;
25 }
26}
27
1class Solution {
2public:
3 // Function to find an element in the vector that is not the minimum or maximum
4 int findNonMinOrMax(vector<int>& nums) {
5 // Find the minimum element in nums using min_element algorithm
6 int minElement = *min_element(nums.begin(), nums.end());
7 // Find the maximum element in nums using max_element algorithm
8 int maxElement = *max_element(nums.begin(), nums.end());
9 // Iterate through all elements in the vector
10 for (int element : nums) {
11 // Check if current element is neither the minimum nor the maximum
12 if (element != minElement && element != maxElement) {
13 // Return the first element found that is not a min or max
14 return element;
15 }
16 }
17 // If there is no such element, return -1
18 return -1;
19 }
20};
21
1// Import statements for necessary functionalities
2import { min, max } from 'lodash';
3
4// Function to find an element in the array that is not the minimum or maximum
5function findNonMinOrMax(nums: number[]): number {
6 // Find the minimum element in nums
7 const minElement = min(nums);
8 // Find the maximum element in nums
9 const maxElement = max(nums);
10
11 // Iterate through all elements in the array
12 for (const element of nums) {
13 // Check if current element is neither the minimum nor the maximum
14 if (element !== minElement && element !== maxElement) {
15 // Return the first element found that is not a min or max
16 return element;
17 }
18 }
19
20 // If there is no such element, return -1
21 return -1;
22}
23
Time and Space Complexity
// The time complexity of the findNonMinOrMax
method is O(n)
, where n
is the number of elements in the input list nums
. This is because min(nums)
and max(nums)
both iterate over the entire list individually, each taking O(n)
time. The subsequent for-loop also iterates over the list once, leading to a linear time complexity overall.
// The space complexity of the method is O(1)
since it only uses a fixed amount of additional space for the variables mi
, mx
, and x
regardless of the size of the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!