Find the minimum and maximum element in an array using Divide and Conquer
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
Output:
The minimum array element is 2
The maximum array element is 9
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> #include <vector> #include <climits> using namespace std; // Divide and conquer solution to find the minimum and maximum number in an array void findMinAndMax(vector<int> const &nums, int low, int high, int &min, int &max) { // if the array contains only one element if (low == high) // common comparison { if (max < nums[low]) { // comparison 1 max = nums[low]; } if (min > nums[high]) { // comparison 2 min = nums[high]; } return; } // if the array contains only two elements if (high - low == 1) // common comparison { if (nums[low] < nums[high]) // comparison 1 { if (min > nums[low]) { // comparison 2 min = nums[low]; } if (max < nums[high]) { // comparison 3 max = nums[high]; } } else { if (min > nums[high]) { // comparison 2 min = nums[high]; } if (max < nums[low]) { // comparison 3 max = nums[low]; } } return; } // find the middle element int mid = (low + high) / 2; // recur for the left subarray findMinAndMax(nums, low, mid, min, max); // recur for the right subarray findMinAndMax(nums, mid + 1, high, min, max); } int main() { vector<int> nums = { 7, 2, 9, 3, 1, 6, 7, 8, 4 }; // initialize the minimum element by INFINITY and the // maximum element by -INFINITY int max = INT_MIN, min = INT_MAX; int n = nums.size(); findMinAndMax(nums, 0, n - 1, min, max); cout << "The minimum array element is " << min << endl; cout << "The maximum array element is " << max << endl; return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// nums Pair class to wrap immutable primitive ints class Pair { public int max, min; public Pair(int max, int min) { this.max = max; this.min = min; } } class Main { // Divide and conquer solution to find the minimum and maximum number in an array public static void findMinAndMax(int[] nums, int left, int right, Pair p) { // if the array contains only one element if (left == right) // common comparison { if (p.max < nums[left]) { // comparison 1 p.max = nums[left]; } if (p.min > nums[right]) { // comparison 2 p.min = nums[right]; } return; } // if the array contains only two elements if (right - left == 1) // common comparison { if (nums[left] < nums[right]) // comparison 1 { if (p.min > nums[left]) { // comparison 2 p.min = nums[left]; } if (p.max < nums[right]) { // comparison 3 p.max = nums[right]; } } else { if (p.min > nums[right]) { // comparison 2 p.min = nums[right]; } if (p.max < nums[left]) { // comparison 3 p.max = nums[left]; } } return; } // find the middle element int mid = (left + right) / 2; // recur for the left subarray findMinAndMax(nums, left, mid, p); // recur for the right subarray findMinAndMax(nums, mid + 1, right, p); } public static void main(String[] args) { int[] nums = { 7, 2, 9, 3, 1, 6, 7, 8, 4 }; // initialize the minimum element by INFINITY and the // maximum element by -INFINITY Pair p = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE); findMinAndMax(nums, 0, nums.length - 1, p); System.out.println("The minimum array element is " + p.min); System.out.println("The maximum array element is " + p.max); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import sys # Divide and conquer solution to find the minimum and maximum number in a list def findMinAndMax(nums, left, right, min=sys.maxsize, max=-sys.maxsize): # if the list contains only one element if left == right: # common comparison if min > nums[right]: # comparison 1 min = nums[right] if max < nums[left]: # comparison 2 max = nums[left] return min, max # if the list contains only two elements if right - left == 1: # common comparison if nums[left] < nums[right]: # comparison 1 if min > nums[left]: # comparison 2 min = nums[left] if max < nums[right]: # comparison 3 max = nums[right] else: if min > nums[right]: # comparison 2 min = nums[right] if max < nums[left]: # comparison 3 max = nums[left] return min, max # find the middle element mid = (left + right) // 2 # recur for the left sublist min, max = findMinAndMax(nums, left, mid, min, max) # recur for the right sublist min, max = findMinAndMax(nums, mid + 1, right, min, max) return min, max if __name__ == '__main__': nums = [7, 2, 9, 3, 1, 6, 7, 8, 4] # initialize the minimum element by INFINITY and the # maximum element by -INFINITY (min, max) = findMinAndMax(nums, 0, len(nums) - 1) print("The minimum element in the list is", min) print("The maximum element in the list is", max) |
Output:
The minimum array element is 1
The maximum array element is 9
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).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)