Neither Minimum nor Maximum

EASY

Description

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

Checkout 3 different approaches to solve Neither Minimum nor Maximum. Click on different approaches to view the approach and algorithm in detail.

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.

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.
1. Sort the array nums in ascending order.
1. After sorting, the minimum element is at nums[0] and the maximum is at nums[nums.length - 1].
1. Any element between these two is a valid answer. We can simply return nums[1].

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.

import java.util.Arrays;

class Solution {
    public int findNonMinOrMax(int[] nums) {
        if (nums.length < 3) {
            return -1;
        }
        Arrays.sort(nums);
        return nums[1];
    }
}

Complexity Analysis

Time Complexity: O(N log N) Where N is the number of elements in `nums`. The time complexity is dominated by the sorting step.Space Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Neither Minimum nor Maximum. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Neither Minimum nor Maximum

Algorithms:

Sorting

Data Structures:

Array