Posts Max Min (InterviewBit)
Post
Cancel

Max Min (InterviewBit)

PROBLEM DESCRIPTION

Given an array A of size N. You need to find the sum of Maximum and Minimum element in the given array.

interviewbit

SOLUTION

We can break the array into two sections and search for the smallest and largest numbers within each part. By performing this process for both halves of the array, we can identify the smallest number in the entire array by comparing the smallest numbers from each half. Similarly, we determine the largest number by comparing the largest numbers from both halves. After finding these smallest and largest values, we add them together and return their sum.

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
public class Solution {

    public int solve(int[] A) {

        // Find the minimum and maximum elements using minMaxPair function
        int[] minMax = minMaxPair(0, A.length-1, A);

        // Return the sum of the minimum and maximum elements
        return minMax[0] + minMax[1];

    }

    // recursive method to get the [min, max] pair for a given array
    public int[] minMaxPair(int s, int e, int[] A){

        // Calculate the size of the subarray
        int n = e - s + 1;

        // If only one element in the subarray, return it as both minimum and maximum
        if(n == 1) return new int[]{A[s], A[s]};

        // Calculate the midpoint of the subarray (to divide it into two parts)
        int mid = s + (e - s) / 2;

        // Recursively find min and max for left and right halves of the subarray
        int[] left = minMaxPair(s, mid, A);
        int[] right = minMaxPair(mid + 1, e, A);

        // Determine minimum and maximum among the minimums and maximums of left and right halves
        int minArray = left[0] < right[0] ? left[0] : right[0];
        int maxArray = left[1] > right[1] ? left[1] : right[1];

        // Return the minimum and maximum elements of the entire subarray
        return new int[]{minArray, maxArray};
    }
}
This post is licensed under CC BY 4.0 by the author.