DEV Community

Cover image for 🚩Find Max and Min of the array🚩
Kaiwalya Koparkar
Kaiwalya Koparkar

Posted on

🚩Find Max and Min of the array🚩

Question: Write a program to return minimum and maximum in an array. Your program should make the minimum number of comparisons.

  • Answer:

    Logic:

    • Iterative: ( O ^ n )
      • Declare min and max ( min = 10000000 , max = 0 )
      • iterate through every element in the array and check if it is greater than max OR lesser than min. and update accordingly
    • Tournament method:( O ^ log2n )
      • Declare min and max ( min = 10000000 , max = 0 )
      • Run two loops. 1) From arr [ 0 ] to arr [ arr.length/2 ] . 2)From arr [ arr.length/2 ] to arr[ arr.length -1 ];
      • and find max1 and min1 from the first loop and max2 and min2 from the second loop.
      • Compare max1 and max2 AND min1 and min2
      • Print the greater max and lower min
    • Sorting method:( O ^ logn ):
      • Sort the array ( here I have used inbuilt function but you can actually implement the sorting technique to solve)
      • Print arr [ 0 ] as min and arr[ arr.length - 1 ] as max
    
    import java.util.*;
    
    public class Solution{
        public static void main(String args[]){
    
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int arr[] = new int[n];
            for(int i=0; i<arr.length; i++){
                arr[i] = sc.nextInt();
            }
    
            int maxIterative = 0;
            int minIterative = 100000000;
    
            //This is Iterative method
            for(int i=0; i<arr.length; i++){
                if(arr[i]>maxIterative){
                    maxIterative = arr[i];
                }
                if(arr[i]<minIterative){
                    minIterative = arr[i];
                }
            }
    
            System.out.println("Max by iterative is: "+maxIterative);
            System.out.println("Min by iterative is: "+minIterative);
    
            //This is Tournament method
            int maxTour1 = 0;
            int maxTour2 = 0;
            int minTour1 = 100000000;
            int minTour2 = 100000000;
    
            for(int i=0; i<arr.length/2; i++){
                if(arr[i]>maxTour1){
                    maxTour1 = arr[i];
                }
                if(arr[i]<minTour1){
                    minTour1 = arr[i];
                }
            }
            for(int i=arr.length/2; i<arr.length; i++){
                if(arr[i]>maxTour2){
                    maxTour2 = arr[i];
                }
                if(arr[i]<minTour2){
                    minTour2 = arr[i];
                }
            }
            if(maxTour1<maxTour3){
                System.out.println("Max by Tournament method is: "+maxTour2);
            }else{
                System.out.println("Max by Tournament method is: "+maxTour1);
            }
            if(minTour1<minTour2){
                System.out.println("Min by Tournament method is: "+minTour1);
            }else{
                System.out.println("Min by Tournament method is: "+minTour2);
            }
    
            //This is Sorting method
            Arrays.sort(arr);
            System.out.println("Max by sorting method is: "+arr[arr.length-1]);
            System.out.println("Min by sorting method is: "+arr[0]);
    
        }
    }
    

Discussion (0)