Difficulty: Medium, Asked-in: Facebook, Microsoft
Key takeaways
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
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.
Solution idea and steps
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)
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!
Solution steps
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]
}
}
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]
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.
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.
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.
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.
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.
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
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
}
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
}
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!
Space complexity = O(1), Total comparison count in the worst case = 2(n-1)
Space complexity = O(logn), Total comparison count = 3n/2 - 2 (If n is a power of 2)
Space complexity = O(1), Total comparison count in the worst-case = 3n/2 - 2
Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.