Find maximum and minimum in an array

find max and min in an array

Difficulty: Medium, Asked-in: Facebook, Microsoft, Key takeaway after reading this blog: You will learn problem solving using single loop and divide and conquer approach. In the single loop approach, we are incrementing loop by 2 to solve the problem using minimum number of comparisons.

Problem understanding

Given an array X[] of size n, write a program to find the maximum and minimum element in the array. Our goal would be to solve this problem using minimum number of comparisons.

Examples

Input: X[] = [4, 2, 0, 8, 20, 9, 2], Output: max = 20, min = 0

Input: X[] = [-8, -3, -10, -32, -1], Output: max = -1, min = -32

Brute force approach: Incrementing loop by 1

• We initialize two variables, max and min, with the first element.
• Now we traverse array and compare each element with min and max. If X[i] < min, we update min with X[i]. Otherwise, if X[i] > max, we update max with X[i].
• By the end of loop, minimum and maximum elements of the array will be stored in min and max. To return these two values, we take extra array output[] of size 2 (we store maximum at output[0] and minimum at output[1]).

Algorithm pseudocode

Algorithm analysis

The worst case will occur when array is sorted in descending order. In this situation, we will be making two comparisons at each iteration i.e. first if statement will be false and second if statement will be true. So total number of comparison = 2*(n — 1) = 2n — 2.

Overall time complexity in the worst case = (2n — 2) *O(1) = O(n). What will be the count of comparison in the best case? Think! We are using constant extra space, so space complexity = O(1).

Using divide and conquer approach

Can we think recursively to solve this problem? Here is a divide and conquer idea similar to merge sort algorithm.

• Divide: Divide array into two halves.
• Conquer: Recursively find maximum and minimum of both halves.
• Combine: Compare maximum of both halves to get overall maximum and compare minimum of both halves to get overall minimum.

Algorithm steps

Suppose the function call minMax(X[], l, r) returns the maximum and minimum of the array, where l and r are the left and right endpoints.

• Divide array by calculating mid index i.e. mid = l + (r — l)/2
• Recursively find the maximum and minimum of left part by calling the same function i.e. leftMinMax[2] = minMax(X, l, mid)
• Recursively find the maximum and minimum of right part by calling the same function i.e. rightMinMax[2] = minMax(X, mid + 1, r)
• Finally, get the overall maximum and minimum by comparing the min and max of both halves.

if (leftMinMax[0] > rightMinMax[0])
    max = lminMax[0]
else
    max = rightMinMax[0]
if (leftMinMax[1] < rightMinMax[1])
    min = leftMinMax[1]
else
    min = rightMinMax[1]

• Store max and min in output[2] and return it.

Base case 1: If the array size gets reduced to 1 during recursion, return that single element as both max and min.

Base case 2: If the array size gets reduced to 2 during recursion, compare both elements and return maximum and minimum.

Algorithm pseudocode

Algorithm analysis

Suppose the time complexity of input size n is T(n). So we need to define the recurrence relation for the time complexity function T(n).

We are recursively solving two subproblems of size n/2 and making two comparisons to get the overall max and min. So the recurrence relation of time complexity is: T(n) = 2 T(n/2) + 2, where T(2) = 1 and T(1) = 0.

We can solve this recurrence relation using the recursion tree method and master theorem. For a better analysis, let’s assume n is a power of 2.

Recursion tree diagram of divide and conquer solution of finding minimum and maximum.

Here subproblems will get divided equally and terminate at the base case of input size 2. In other words, recursion will stop when n/(2^i) = 2 => n = 2^(i+1) ……. (1).

So total count of comparison operations in the above recursion tree = Sum of comparison count at each level = (2 + 4 + 8 + 2^i ) + 2^i = 2 (2^i — 1) + 2^i = 2^(i + 1) + 2^i — 2 = n + n/2–2 = 3n/2–2. Note: If n is not a power of 2, it makes more than 3n/2 -2 comparisons.

So time complexity = (3n/2–2) * O(1) = O(n). Space complexity is equal to the size of the recursion call stack, which is equal to the height of the recursion tree i.e. O(logn). Note: As we observe, time complexity is O(n), but we are solving the problem using less number of comparisons (In the worst case).

Efficient approach: Incrementing loop by 2

Algorithm idea

In the brute force approach, we will be making two comparisons for each element in the worst case. Can we optimize this further to solve the problem using less comparison count? Let’s think!!

The idea is to run a single loop, pick values in pairs and keep tracking minimum and maximum. Suppose we have updated the maximum and minimum till (i — 1)th index and stored them in max and min variables. In the next iteration, we consider a pair of values at ith and (i + 1)th indices and try to update max and min till (i + 1)th index.

If X[i] < X[i + 1], then X[i] will be the candidate for minimum, and X[i + 1] will be the candidate for maximum. So we compare X[i] with min and X[i + 1] with max and update both variables.

if (X[i] < min), we update min = X[i]
if (X[i + 1] > max), we update max = X[i + 1]

If X[i] > X[i + 1], then X[i + 1] will be the candidate for minimum, and X[i] will be the candidate for maximum. So we compare X[i + 1] with min and X[i] with max and update both variables.

if (X[i] > max), we update max = X[i]
if (X[i + 1] < min), we update min = X[i + 1]

Here we will make 3 comparisons in both scenarios to update the max and min of a pair of elements. So this idea will save one comparison count with respect to the brute force approach, where we are making 4 comparisons for two elements in the worst case.

Algorithm steps

• Declare max and min variables to store maximum and minimum.
• We are picking elements in pairs. So if array size is odd, initialise min and max with X[0] and loop variable i with 1. Otherwise, compare X[0] and X[1], initialize min with the smaller value, max with larger value and loop variable i with 2.

Now run a loop till the end and process array elements in pairs. Based on comparison of X[i] and X[i + 1]:

• Compare larger of X[i] and X[i + 1] with max and update max.
• Compare smaller of X[i] and X[i + 1] with min and update min.

By the end of loop, max and min will store the maximum and minimum of the array. So we take an array output[2], store max at output[0], min at output[1] and return it.

Algorithm pseudocode

Algorithm analysis

We make three comparisons for each pair of elements in both best and worst cases. So total count of comparison operations =

• 3 * (n — 1) / 2 if n is odd.
• 1 + 3*(n — 2)/2 = 3n/2–2, if n is even.

As we observe, time complexity is O(n), but the total count of comparison is less than the comparison count in the brute force approach.

Possible follow-up questions by the interviewer

• Can you identify another scenario where we solve problems by incrementing the loop by 2 or more than 2?
• What are the best and worst cases in the second approach? In which situation is the number of comparison counts by approach 2 equal to the number of comparison counts by approach 3?
• How can we analyze the time complexity of the second approach using the master theorem or substitution method of recursion analysis?
• Why is the space complexity O(logn) in the second approach?
• What will be the time complexity if we only consider the base case of array size 1? Can we solve this problem using some other approach?

Similar coding problems to explore

• Sort an array in the waveform
• Find N Repeated Element in 2N Size Array
• Divide and conquer idea of max subarray sum
• Divide and conquer idea to find majority element
• Divide and conquer idea to find max difference in an array
• Remove duplicates from the sorted array
• Valid mountain in an array
• Move zeroes to the end
• Number of buildings facing the sun
• Sort an array of 0s, 1s and 2s

For more content, explore our free DSA course and coding interview blogs. If you want to learn live, explore these two courses:

• EnjoyAlgorithms 16-Week Live DSA Course
• EnjoyAlgorithms 10-Week Live DSA Course

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!

Originally published at https://www.enjoyalgorithms.com/blog/find-the-minimum-and-maximum-value-in-an-array/