# Neither Minimum nor Maximum
**Difficulty:** EASY
[External](https://leetcode.com/problems/neither-minimum-nor-maximum)
Canonical: https://scaleengineer.com/dsa/problems/neither-minimum-nor-maximum
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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 <= 100`
* `1 <= nums[i] <= 100`
* All values in `nums` are distinct

# Approaches
## Brute Force with Sorting
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.
**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.
**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.
### Explanation
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 `nums` in non-decreasing order.
- After sorting, `nums[0]` holds the minimum value and `nums[nums.length - 1]` holds the maximum value.
- Any element at an index `i` where `0 < i < nums.length - 1` is 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.

```java
import java.util.Arrays;

class Solution {
    public int findNonMinOrMax(int[] nums) {
        if (nums.length < 3) {
            return -1;
        }
        Arrays.sort(nums);
        return nums[1];
    }
}
```
### Algorithm
- 1. Check if the length of the input array `nums` is less than 3. If it is, no such number can exist, so return -1.
- 2. Sort the array `nums` in ascending order.
- 3. After sorting, the minimum element is at `nums[0]` and the maximum is at `nums[nums.length - 1]`.
- 4. Any element between these two is a valid answer. We can simply return `nums[1]`.

## Two-Pass Linear Scan
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.
**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`.
**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.
### Explanation
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 `minVal` and `maxVal` with 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 `minVal` and `maxVal`, we perform a second pass through the array.
- In this second pass, for each element `num`, we check if it is different from both `minVal` and `maxVal`.
- The first element that satisfies `num != minVal && num != maxVal` is 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.

```java
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
    }
}
```
### Algorithm
- 1. Handle the edge case: if `nums.length` is less than 3, return -1.
- 2. Initialize two variables, `minVal` and `maxVal`, to track the minimum and maximum values.
- 3. Iterate through the array once to find the true `minVal` and `maxVal`.
- 4. Iterate through the array a second time.
- 5. For each element `num`, check if it is not equal to `minVal` and not equal to `maxVal`.
- 6. The first element that satisfies this condition is a valid answer, so return it.

## Constant Time Solution by Examining a Subset
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.
**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.
**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.
### Explanation
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`, and `c`. When sorted, let them be `x < y < z`. The value `y` cannot be the global minimum of the entire `nums` array (because `x` is smaller), and it cannot be the global maximum (because `z` is larger). Therefore, `y` is 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]`, and `nums[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.

```java
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];
    }
}
```
### Algorithm
- 1. Check if the array length is less than 3. If so, return -1.
- 2. Consider only the first three elements of the array: `nums[0]`, `nums[1]`, and `nums[2]`.
- 3. Among these three distinct numbers, one must be the smallest, one the largest, and one in the middle.
- 4. This middle value is guaranteed to be a valid answer because it cannot be the global minimum or maximum of the entire array.
- 5. Find this middle value by sorting the three elements and picking the second one, or by using comparisons.
- 6. Return the identified middle value.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def findNonMinOrMax(
        self, nums: List[int]) -> int: return - 1 if len(nums) < 3 else sorted(nums)[1]

```