Given an integer array, find the minimum and maximum element present in it by making minimum comparisons by using the divide-and-conquer technique.

For example,

Input:  nums = [5, 7, 2, 4, 9, 6]
 
Output:
 
The minimum array element is 2
The maximum array element is 9

Practice this problem

We can easily solve this problem by using Divide and Conquer. The idea is to recursively divide the array into two equal parts and update the maximum and minimum of the whole array in recursion by passing minimum and maximum variables by reference. The base conditions for the recursion will be when the subarray is of length 1 or 2. The following solution in C++, Java, and Python handles all the comparisons efficiently in base conditions:

C++


Download  Run Code

Java


Download  Run Code

Python


Download  Run Code

Output:
 
The minimum array element is 1
The maximum array element is 9

The time complexity of the above solution is O(n), where n is the size of the input. The auxiliary space required by the program is O(n) for recursion (call stack).