Find the Maximum and Minimum element in an Array

The problem is to find the maximum and minimum element in an array. Given an array of numbers, the task is to identify the largest (maximum) and smallest (minimum) values present in the array.

To solve this problem, we iterate through the array and keep track of the current maximum and minimum values encountered. We start by initializing the maximum and minimum variables to the first element of the array. Then, for each subsequent element, we compare it with the current maximum and minimum values. If a larger value is found, we update the maximum value. Similarly, if a smaller value is found, we update the minimum value.

Process to Find the Maximum and Minimum element in an Array (Simple approach)

In this Java example, we have the findMaxMin method that takes an array of integers as input and returns an array containing the maximum and minimum values. It initializes maxVal and minVal with the first element of the array and then iterates through the remaining elements. If a larger value than the current maximum is found, it updates maxVal. Similarly, if a smaller value than the current minimum is found, it updates minVal. Finally, the method returns an array [maxVal, minVal].

The main method demonstrates how to use the findMaxMin method with an example array and prints the maximum and minimum values.


public class MaxMinArray {
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 7};
        
        // Call the function to find max and min values
        int[] result = findMaxMin(array);
        
        int max = result[0];
        int min = result[1];
        
        System.out.println("Maximum: " + max);
        System.out.println("Minimum: " + min);
    }
    
    public static int[] findMaxMin(int[] arr) {
        if (arr.length == 0) {
            return null;  // Handle empty array case
        }
        
        // Initialize the maximum and minimum variables
        int maxVal = arr[0];
        int minVal = arr[0];
        
        // Iterate through the array
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
            if (arr[i] < minVal) {
                minVal = arr[i];
            }
        }
        
        int[] result = {maxVal, minVal};
        return result;
    }
}

Output:

Maximum: 9
Minimum: 1

Time Complexity : The time complexity of finding the maximum and minimum elements in an array using the approach described above is O(n), where n is the number of elements in the array. This is because we need to iterate through the entire array once to find the maximum and minimum values.

Storage: The space complexity is O(1) because we only need a constant amount of extra space to store the maximum and minimum values. Regardless of the size of the input array, the amount of additional space used remains the same.

Finding the minimum and maximum values from an Array using Binary Search Tree(BST)

To find the minimum and maximum values from an array using a binary search tree (BST), you can construct a BST from the array and then find the minimum and maximum values by traversing the leftmost and rightmost nodes of the BST, respectively. Here’s an example in java.

In this example, the insert function is used to construct the BST from the array. It recursively inserts each element from the array into the BST based on the binary search tree property.

The findMin and findMax functions are the same as in the previous example. They traverse the BST to find the leftmost and rightmost nodes, respectively, which contain the minimum and maximum values.

In the main method, we create a BST by inserting the elements of the array. Then, we find the minimum and maximum values in the BST using the findMin and findMax functions. The output will display the minimum and maximum values from the array.


public class BST {
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    static Node insert(Node root, int key) {
        if (root == null) {
            return new Node(key);
        }

        if (key < root.data) {
            root.left = insert(root.left, key);
        } else if (key > root.data) {
            root.right = insert(root.right, key);
        }

        return root;
    }

    static int findMin(Node root) {
        if (root == null) {
            throw new IllegalArgumentException("The BST is empty");
        }

        Node current = root;
        while (current.left != null) {
            current = current.left;
        }

        return current.data;
    }

    static int findMax(Node root) {
        if (root == null) {
            throw new IllegalArgumentException("The BST is empty");
        }

        Node current = root;
        while (current.right != null) {
            current = current.right;
        }

        return current.data;
    }

    public static void main(String[] args) {
        int[] arr = {1000, 11, 445, 1, 330, 3000};

        Node root = null;
        for (int i = 0; i < arr.length; i++) {
            root = insert(root, arr[i]);
        }

        int minValue = findMin(root);
        int maxValue = findMax(root);

        System.out.println("Minimum value in the array: " + minValue);
        System.out.println("Maximum value in the array: " + maxValue);
    }
}

Note that constructing the BST from the array has a time complexity of O(n log n) on average, assuming the array is randomly ordered. If the array is already sorted, constructing the BST from the sorted array would take O(n^2) time.

Thank you for visiting the FlutterTPoint. You can see more about it from here.