Find Maximum and Minimum using Minimum Number of Comparisons

Difficulty: Medium, Asked-in: Facebook, Microsoft

Key takeaways

  • An excellent coding problem to learn problem-solving using single loop and divide and conquer approach.
  • We are incrementing loop by two (constant) to optimize the code further. We can use similar ideas to optimize code for other coding problems.
  • Base conditions, initializations, and conditional statements are intuitive. We can find similar pattern in other coding problems.
  • The time complexities of all three approaches are O(n), but the total count of comparison operations are different. Such a scenario may arise in solving other coding problems where one can reduce the count of critical operations to optimize the solution further.

Let’s understand the problem

Given an array X[] of size n, we need to find the maximum and minimum elements present in the array. Our algorithm should make the 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

Important note: Before moving to the solutions, we recommend learners to solve this problem. If solved, then well done! We would like to hear your ideas in the message below. Otherwise, no problem! Consider this is an excellent opportunity to learn a new pattern in problem-solving.

Follow-up questions for the interviewer

  • Candidate: Are the input values unique? Interviewer: For the convenience of the solution, we can assume that.
  • Candidate: Do we need to solve this problem in place? Interviewer: Yes, we are looking for an O(n) in-place solution with the minimum number of comparison count.

Now we are moving forward and discussing the solution ideas step-by-step. Practising these steps could help us to arrive at an efficient solution during a coding interview.

Discussed solution approaches

  1. A brute force approach using single loop: Increment by 1
  2. Using divide and conquer approach similar to merge sort
  3. An efficient approach using single loop: Increment by 2

A brute force using single loop: Increment by 1

Solution idea and steps

  • We declare and initialize variables max and min to store maximum and minimum.
  • We traverse the array from i = 1 to n - 1 and compare each element with min and max.
  • If (X[i] < min): We have found a value smaller than minimum till ith index. So update min with X[i] i.e min = X[i].
  • else If(X[i] > max): We have found a value greater than maximum till ith index. So update max with X[i] i.e max = X[i].
  • By the end of loop, minimum and maximum values of the array will be stored in variables min and max.
  • To return this, we take an extra array maxMin[] of size two, where we store maximum at the first index and minimum at the second index. We return maxMin array as an output.

Solution pseudocode

int[] findMinMax(int X[], int n)
{
    int max = X[0]
    int min = X[0]
    for (int i = 1; i < n; i = i + 1)
    {
        if (X[i] > max)
            max = X[i]
        else if (X[i] < min)
            min = X[i]
    }
    int maxMin[2] = {max, min}
    return maxMin
}

Solution analysis

In the worst case, we make two comparisons at each step of iteration. This case will arise if array is sorted in descending order. In this situation, the first if statement will be false every time, and the second if statement will be true every time. So total number of comparisons in the worst case = 2*(n - 1) = 2n - 2

The best case occurs when elements are sorted in ascending order. In this situation, total n - 1 comparison have been made. Think.

Time complexity = O(n), Space complexity = O(1)

Using divide and conquer approach similar to merge sort

Solution idea

Now the critical question is: can we solve this problem using another approach? can we think recursively to design at an efficient solution? Here is an idea!

  • Divide step: We divide the array into two equal parts around mid index i.e we divide the problem into two equal size sub-problems.
  • Conquer step: We recursively find the minimum and maximum of left and right parts.
  • Combine step: We compare the maximum of both halves to get overall maximum and, the minimum of both halves to get overall minimum.

Solution steps

  • We write a recursive function accepting array and its start and end index as input parameters i.e findMinMax (int X[], int l, int r)
  • Base case 1: If array size is 1, we return that single element as maximum and minimum.
  • Base case 2: If array size is 2, we compare both elements and return maximum and minimum.

    if (l == r)
    {
          max = X[l]
          min = X[l]
    }
    
    else if (l + 1 == r)
    {
      if (X[l] < X[r])
      {
          max = X[r]
          min = X[l]
      }
      else
      {
          max = X[l]
          min = X[r]
      }
    }
  • Divide part: We divide array into two equal parts i.e. mid = l + (r - l)/2.
  • Conquer part:
  • We recursively calculate and store the maximum and minimum for the left part i.e. leftMinMax[2] = findMinMax(X, l, mid)
  • We recursively calculate and store the maximum and minimum for the right part i.e. rightMinMax[2] = findMinMax(X, mid + 1, r)
  • Combine part: Now we find the overall maximum and minimum by comparing the min and max of both halves. For this, we need to perform two comparisons only.

    if (leftMinMax[0] > rightMinMax[0])
      max = leftMinMax[0]
    else
      max = rightMinMax[0]
      
    if (leftMinMax[1] < rightMinMax[1])
      min = leftMinMax[1]
    else
      min = rightMinMax[1]
  • We store max and min in extra memory maxMin[2] and return it.

Solution pseudocode

int[] findMinMax(int X[], int l, int r)
{
    int max, min
    if (l == r)
    {
        max = X[l]
        min = X[l]
    }
    else if (l + 1 == r)
    {
        if (X[l] < X[r])
        {
            max = X[r]
            min = X[l]
        }
        else
        {
            max = X[l]
            min = X[r]
        }
    }
    else
    {
        int mid = l + (r - l)/2
        int leftMinMax[2] = findMinMax(X, l, mid)
        int rightMinMax[2] = findMinMax(X, mid + 1, r)
        if (leftMinMax[0] > rightMinMax[0])
            max = leftMinMax[0]
        else
            max = rightMinMax[0]
        if (leftMinMax[1] < rightMinMax[1])
            min = leftMinMax[1]
        else
            min = rightMinMax[1]
    }
    int maxMin[2] = {max, min}
    return maxMin
}

Solution analysis

Let’s define the recurrence relation to analyze time complexity. Suppose T(n) is the time complexity of problem size n.

  • We are dividing problem into two equal size sub-problems of size n/2.
  • We are performing 2 comparison operations in the combine step.
  • Base case situations occur when n = 2 or n = 1. When n = 2, we are performing 1 comparison operation and when n = 0, we are performing 0 comparison operation.

T(n) = T(n/2) + T(n/2) + 2 = 2T(n/2) + 2, where T(2) = 1 and T(1) = 0

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

find the minimum and maximum analysis

Recursion will stop when the input size of problem becomes 2 or 1 => 2 = n/2^i => 2^(i+1) = n

Taking log both sides => i + 1 = logn => i = logn - 1. So the height of recursion tree = logn - 1

Note: Till (i - 1)th level, every subproblem will perform 2 comparisons at the combine step. The last level is the situation of base case, where only one comparison will be made.

  • Total comparison count from 0th to (i - 1)th level = 2 + 4 + 8 + ... + 2^i = 2*(2^i - 1). We get this value from the sum of geometric series.
  • Total comparison count at ith level = 2^i
  • Total count of comparison operations = 2*(2^i - 1) + 2^i = 2^(i + 1) + 2^i - 2 = n + n/2 – 2 = 3n/2 – 2.
  • If n is not a power of 2, it will make more than 3n/2 - 2 comparisons. Overall time complexity = O(n)

Space complexity = The height of recursion tree = O(logn), for recursion call stack.

Note: Here, time complexity is also O(n), but the total count of comparison operation is less than the previous approach.

An efficient approach  using single loop: loop Increment by 2

Solution idea

In the first approach, we are doing two comparison operations for every element in the worst case. Now the critical question is : can we optimize it further and reduce the total count of comparison operations?

One idea is :  Pick elements in pairs and try to update the minimum and maximum. Suppose till (i - 1)th index, maximum and minimum have been updated in max and min variables. Now we are considering a pair of ith and (i + 1)th index in the next iteration. 

  • if (X[i] < X[i + 1]): There can be a chance that X[i] can be less than min and X[i + 1] can be greater than max. In other words, X[i] will be the candidate for minimum, and X[i + 1] will be the candidate for maximum. So we compare X[i] with the min and X[i + 1] with the max to update minimum and maximum till that point i.e. if (X[i] < min), min = X[i] and if(X[i + 1] > max), max = X[i + 1].
  • if (X[i] > X[i + 1]): We can apply the same approach in this scenario. Here X[i + 1] will be the candidate for minimum, and X[i] will be the candidate for maximum i.e. if (X[i] > max), max = X[i] and if (X[i + 1] < min), min = X[i + 1].

In both scenarios, we are making 3 comparisons (in the worst case) to update the maximum and minimum of 2 elements. In other words, we are saving one comparison with respect to the first approach where we need 4 comparisons for 2 elements (in the worst case).

Initialization : If the array size is odd, we initialize the first element as both min and max, and if the array size is even, we compare the first two elements and initialize min and max accordingly.

Solution steps

  • Declare the max and min variables and check for the array size:
  • If odd, initialize min and max to the first element.
  • If even, compare the elements and set min to the smaller value and max to the larger value.

    if (n % 2 != 0)
    {
       max = X[0]
       min = X[0]
       i = 1
    }
    else
    {
       if (X[0] < X[1])
       {
           max = X[1]
           min = X[0]
       }
       else
       {
           max = X[0]
           min = X[1]
       }
       i = 2
    }
  • Now traverse the array and pick elements in pairs. For each pair (i, i + 1), compare both elements. On the basis of comparison:
  • Compare the larger element with max and update max.
  • Compare the smaller element with min and update min.

    while (i < n)
    {
       if (X[i] < X[i + 1])
       {
           if (X[i] < min)
               min = X[i]
           if (X[i + 1] > max)
               max = X[i + 1]
       }
       else
       {
           if (X[i] > max)
               max = X[i]
           if (X[i + 1] < min)
               min = X[i + 1] 
       }
       i = i + 2
    }
  • Store max and min in an extra memory maxMin[2] and return it.

Solution pseudocode

int[] findMinMax(int X[], int n)
{
    int max, min, i
    if (n % 2 != 0)
    {
        max = X[0]
        min = X[0]
        i = 1
    }
    else
    {
        if (X[0] < X[1])
        {
            max = X[1]
            min = X[0]
        }
        else
        {
            max = X[0]
            min = X[1]
        }
        i = 2
    }
    while (i < n)
    {
        if (X[i] < X[i + 1])
        {
            if (X[i] < min)
                min = X[i]
            if (X[i + 1] > max)
                max = X[i + 1]
        }
        else
        {
            if (X[i] > max)
                max = X[i]
            if (X[i + 1] < min)
                min = X[i + 1] 
        }
        i = i + 2
    }
    int maxMin[2] = {max, min}
    return maxMin
}

Solution analysis

For each pair, there are three comparisons: first among the elements of the pair and the other two with min and max. Total number of comparisons = 3 * (n-1) / 2 (If n is odd) or 3n/2 – 2 (If n is even).

Time complexity = O(n). Here we observe that the total number of comparisons is less than the first approach. In other words, comparison in pairs helps us to optimize the first approach further. (Think)

Important Note: We recommend learners transform the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Please let us know if you find any errors or bugs; we would be highly grateful. Enjoy programming!

Critical ideas to think!

  • Why does incrementing the loop by two help in reducing the comparison count?
  • How do we modify the above solutions when input values are repeated?
  • Is there any other way to solve this problem?
  • In which scenario the number of comparisons by approaches 2 and 3 is equal?
  • Why is space complexity O(logn) in the divide and conquer solution? Why are there two base cases? What would be the time complexity if we remove the base case with array size 2?
  • What would be the best and worst case in the brute force approach?

Comparisons of time and space complexities

  • A brute force approach using single loop: Time complexity = O(n)

Space complexity = O(1), Total comparison count in the worst case = 2(n-1)

  • Using divide and conquer: Time complexity = O(n)

Space complexity = O(logn), Total comparison count = 3n/2 - 2 (If n is a power of 2)

  • An efficient approach using single loop: Time complexity = O(n)

Space complexity = O(1), Total comparison count in the worst-case = 3n/2 - 2

Similar coding questions to practice

Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!

Share feedback with us

More blogs to explore

Our weekly newsletter

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.