Teaching Kids Programming – Algorithms to Find Neither Minimum nor Maximum

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Please note that, the given numbers are all unique/distinct, and they are all positive. Thus, we can have a few methods to do this. All algorithms need to check the case when such numbers don’t exist, for example, when there is only 1 number or 2 numbers in the array.

Algorithms to Find Neither Minimum nor Maximum via Sorting

We can sort the array, and return the second number. This costs O(NLogN) time.

1
2
3
4
5
6

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        nums.sort()
        return nums[1]

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        nums.sort()
        return nums[1]

Algorithms to Find Neither Minimum nor Maximum via Linear Search

We can perform linear search to find the minimum and maximum number, and then iterate the array again to return the first number that is neither of max or min.

Finding minimum via min function costs O(N), and finding maximum via max function costs O(N). The overall time complexity is O(N), although we need to perform the linear search twice.

1
2
3
4
5
6
7
8
9

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        minv, maxv = min(nums), max(nums)
        for i in nums:
            if i != minv and i != maxv:
                return i
        return -1

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        minv, maxv = min(nums), max(nums)
        for i in nums:
            if i != minv and i != maxv:
                return i
        return -1

A better way is to iterate the array once and then find the maximum and minimum at the same time, so this only requires a single pass. And we can also use the next function to return the first number that meets the requirement. Although, it takes at most three iterations to find such number.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        minv = maxv = nums[0]
        for i in nums:
            if i < minv:
                minv = i
            elif i > maxv:
                maxv = i
        return next((i for i in nums if i != minv and i != maxv), -1)

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        minv = maxv = nums[0]
        for i in nums:
            if i < minv:
                minv = i
            elif i > maxv:
                maxv = i
        return next((i for i in nums if i != minv and i != maxv), -1)

Algorithms to Find Neither Minimum nor Maximum via O(1) Constant Time

Since all numbers are unique, we just need to look at the first 3 numbers, we can sort them (sort the 3 numbers and return the second one), however, this only takes O(1) time.

1
2
3
4
5
6

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

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

Here is another slight different approach, by finding the min and max of first two numbers, and then check where the third number falls:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        a, b = min(nums[:2]), max(nums[:2])
        if a < nums[2] < b:
            return nums[2]
        if nums[2] < a:
            return a
        return b

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        a, b = min(nums[:2]), max(nums[:2])
        if a < nums[2] < b:
            return nums[2]
        if nums[2] < a:
            return a
        return b

The time/space complexity is O(1), which is the optimal.

–EOF (The Ultimate Computing & Technology Blog) —