Given an array of size N. The task is to find the maximum and the minimum element of the array using the minimum number of comparisons.
Examples:
Input : A[]={4,2,-1,5,0,-5,7,3,6} Output : Min Element -5 Max Element 7 Input : A[]={3,8,4,2,6,9} Output : Min Element 2 Max Element 9
Approach:
The idea is to use the Two Pointer Approach, so that we can minimize the number of comparisons.
Below is the Step by Step Approach to Solve the Problem:
- Create two variables say mn ,mx for storing the minimum and maximum element respectively.
- Initialize mn and mx with first element of Array.
- Create two variables l and r initialize them with 0 and n-1 respectively
- Traverse the Array till l is less than or equal to r.
- while Traversing the Array Check
- If element at lth position is less than or equal to element at rth position in the Array
- Make mn equal to minimum of mn and element present at lth position in the Array.
- Make mx equal to maximum of mx and element present at rth position in the Array.
- Otherwise
- Make mn equal to minimum of mn and element present at rth position in the Array
- Make mx equal to maximum of mx and element present at lth position in the Array
- Increase l by one and Decrease r by one
- If element at lth position is less than or equal to element at rth position in the Array
- Print the Maximum and Minimum Elements obtained after the loop gets terminated.
Below is implementation of above Approach:
#include <bits/stdc++.h> using namespace std; void Min_And_Max(int a[], int n) { // Create mn,mx for storing // mimimum and maximum // element respectively int mn, mx; // Intitialize mn and mx // with a[0] mn = a[0]; mx = a[0]; // create two variables l and r // initilize them // with 0 and n-1 // respectively int l = 0, r = n - 1; // Traverse Array // untill l<=r while (l <= r) { // if element at lth position // is less than or equal to // element at rth position // in the Array if (a[l] <= a[r]) { mn = min(mn, a[l]); mx = max(mx, a[r]); } // otherwise else { mn = min(mn, a[r]); mx = max(mx, a[l]); } // increase l and r by one l++; r--; } // Print Minimum and maximum element cout << "Min Element " << mn << endl; cout << "Max Element " << mx; } // Driver Code int main() { int a[] = { 4, 2, -1, 5, 0, -5, 7, 3 }; int n = sizeof(a) / sizeof(a[0]); Min_And_Max(a, n); return 0; }
Output:
Min Element -5 Max Element 7
Time Complexity : O(N)
Space Complexity : O(1)