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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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:

  1. Finding the Minimum and Maximum: We first find the smallest (mi) and largest (mx) numbers in the array using the min(nums) and max(nums) functions. These functions traverse the array, and each one completes in O(n) time where n is the number of elements in the array.
1mi, mx = min(nums), max(nums)
  1. Iterating Through the Array: Next, we iterate through each element x in the array nums. This is done using a for loop.
1for x in nums:
  1. Checking the Condition: In each iteration, we check if the current element x is not equal to the minimum value mi and not equal to the maximum value mx.
1if x != mi and x != mx:
  1. 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.
1return x
  1. 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.
1return -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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's illustrate the solution approach with an example:

Assume our input array nums is [3, 1, 4, 2].

  1. Finding the Minimum and Maximum: We find the smallest number (mi) is 1 and the largest number (mx) is 4.

    1mi, mx = min(nums), max(nums) # mi = 1, mx = 4
  2. Iterating Through the Array: We iterate through each element x in the array [3, 1, 4, 2], using a for loop.

  3. Checking the Condition:

    • First iteration: x = 3, x != mi is True, and x != mx is also True. Since both conditions are satisfied, we have found a "middle" number.
    1for x in nums:
    2    if x != mi and x != mx:
    3        return x
  4. 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
Not Sure What to Study? Take the 2-min Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫