Maximum and Minimum Element in an Array - DSA Question 1

Problem Statement:

Given an array A of size N your task is to find the minimum and maximum elements in the array containing integers.

Example 1:

Input:
N = 6
A[] = {3, 2, 1, 56, 10000, 167}
Output: 1 10000
Explanation: minimum and maximum elements of array are 1 and 10000.

As a student, diving into the world of programming can be overwhelming, especially when faced with complex problems. However, fear not! We're here to unravel one such problem in a way that even beginners can grasp. Imagine you have a list of numbers, and you're tasked with finding the smallest and largest numbers from this list. Let’s break down this problem and its solutions step by step.

Understanding the Problem:

Picture this: you have an array of numbers, just like a shopping list. Each number represents an item. The challenge is to figure out the cheapest and most expensive items on your list.

Brute Force Solution:

A brute-force approach to solve this problem involves iterating through the array and keeping track of the minimum and maximum elements found so far.

Explanation of Brute Force Solution:

1. Initialize two variables min and max with the first element of the array.

2. Iterate through the array starting from the second element.

3. For each element, compare it with the current min and max values.

4. If the current element is smaller than min, update min.

5. If the current element is larger than max, update max.

6. After iterating through the array, min and max will hold the minimum and maximum elements respectively.

public class MinMaxElement {

    public static void main(String[] args) {
        int[] arr = {3, 5, 4, 1, 9};

        int min = arr[0]; // Initialize min with the first element of the array
        int max = arr[0]; // Initialize max with the first element of the array

        for (int i = 1; i < arr.length; i++) {
            // Check if the current element is smaller than min, update min
            if (arr[i] < min) {
                min = arr[i];
            }

            // Check if the current element is larger than max, update max
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        System.out.println("Minimum element is: " + min);
        System.out.println("Maximum element is: " + max);
    }
}

Optimal Solution:

The brute force solution has a time complexity of O(n) where n is the number of elements in the array. The optimal solution also has a time complexity of O(n), but it involves reducing the number of comparisons by considering pairs of elements.

Explanation of Optimal Solution:

1. Initialize an Pair object to store both minimum and maximum values.

2. Based on the number of elements in the array, initialize minmax with the first element or the first two elements.

3. Iterate through the array with a step of 2 (considering pairs of elements).

4. For each pair of elements, compare them and update minmax.min and minmax.max accordingly.

5. The number of comparisons is reduced by processing elements in pairs, making the algorithm more efficient.

public class MinMaxElement {

    static class Pair {
        int min;
        int max;
    }

    static Pair getMinMax(int[] arr, int n) {
        Pair minmax = new Pair();
        int i;

        // If the array has an even number of elements, initialize min and max with the first two elements.
        if (n % 2 == 0) {
            if (arr[0] > arr[1]) {
                minmax.max = arr[0];
                minmax.min = arr[1];
            } else {
                minmax.min = arr[0];
                minmax.max = arr[1];
            }
            i = 2; // Start the loop from the third element
        } else {
            // If the array has an odd number of elements, initialize min and max with the first element.
            minmax.min = arr[0];
            minmax.max = arr[0];
            i = 1; // Start the loop from the second element
        }

        // Compare elements in pairs and update min and max accordingly.
        while (i < n - 1) {
            if (arr[i] > arr[i + 1]) {
                if (arr[i] > minmax.max) {
                    minmax.max = arr[i];
                }
                if (arr[i + 1] < minmax.min) {
                    minmax.min = arr[i + 1];
                }
            } else {
                if (arr[i + 1] > minmax.max) {
                    minmax.max = arr[i + 1];
                }
                if (arr[i] < minmax.min) {
                    minmax.min = arr[i];
                }
            }
            i += 2; // Move to the next pair
        }

        return minmax;
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 4, 1, 9};
        int n = arr.length;
        Pair minmax = getMinMax(arr, n);

        System.out.println("Minimum element is: " + minmax.min);
        System.out.println("Maximum element is: " + minmax.max);
    }
}

Conclusion:

To sum it up, finding the minimum and maximum numbers in an array is akin to finding the cheapest and most expensive items in your shopping list. With a simple mindset and a bit of cleverness, you can efficiently solve this problem. Whether you prefer the straightforward brute force method or the optimized pair comparison approach, the goal remains the same: to find the minimum and maximum elements in a list. So, fear not, aspiring programmers! With these techniques in your toolkit, you’re one step closer to mastering the world of coding. Happy coding!