Difficulty: Medium, Asked-in: Facebook, Microsoft
Key takeaways
Given an array X[] of size n, we need to find the maximum and minimum element 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 solve this problem. If solved, then well done! We would like to hear your ideas in the comment. Otherwise no problem, this is an 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 in a step-by-step manner. Practicing these steps could help us to arrive at an efficient solution during a coding interview.
Solution idea and steps
Solution Pseudocode
Time and space complexity analysis
Time complexity = O(n), Space complexity = O(1)
Solution Idea
Now the critical question is: can we solve the problem using another approach? can we think recursively to arrive at an efficient solution? Here is an idea!
The above idea looks similar to the divide and conquers idea of merge sort. Think!
Solution Steps
Base case 2: If the array size is 2, compare the two 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 calculate the overall maximum and minimum by comparing the min and max of both halves. We need to do two comparisons only.
if (lminMax[0] > rminMax[0])
max = lminMax[0]
else
max = rminMax[0]
if (lminMax[1] < rminMax[1])
min = lminMax[1]
else
min = rminMax[1]
Solution Pseudocode
Time and space complexity analysis
Let’s define the recurrence relation to analyze the time complexity. Let's T(n) is the time complexity of the problem of input size n and we are dividing the problem into two equal-size sub-problems of size n/2.
T(n) = T(n/2) + T(n/2) + 2 = 2 T(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, n/2^i = 2 => n = 2^(i+1) ……. (1)
In the above recursion tree, the total count of comparison operations
= Sum of comparison count at each level
= 2 + 4 + 8 + 2^i + 2^i
= 2 (2^i — 1) + 2^i (From the sum of the geometric series)
= 2^(i+1) + 2^i — 2
= n + n/2–2 = 3n/2–2
if n is not a power of 2, it does more than 3n/2 -2 comparisons.
=> Time complexity = O(n)
=> Space complexity = Height of the recursion tree = O(logn), for recursion call stack.
Note — Here time complexity is also O(n) but the total number of the 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 scenario. Now the critical question : can we optimize it further and reduce the total number of comparison operations? Let’s think!!
One idea is — let's pick the elements in pairs and try to update the minimum and maximum. Suppose till (i-1)th index, maximum and minimum have been updated in the max and min variable. Now we are considering a pair of ith and (i+1)th index in the next iteration.
Scenario 1 : if (X[i] < X[i+1]), then there can be a chance that X[i] can be less than the minimum and X[i+1] can be greater than maximum.
if (X[i] < min) => min = X[i]
if(X[i+1] > max) => max = X[i+1]
Scenario 2 : if (X[i] > X[i+1]), then there can be a chance that X[i] can be greater than maximum and X[i+1] can be less than the minimum.
if (X[i] > max) => max = X[i]
if (X[i+1] < min) => min = X[i+1]
In both the scenario, we are only doing 3 comparisons (worst case) to update the maximum and minimum of 2 elements. I think we are saving one comparison with respect to the first approach where we need 4 comparisons for 2 elements (worst case).
Initialization : If the array size is odd, we initialize the first element as both min and max, and if it’s 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 bigger value
if (n is odd)
{
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 the min, update the min if required.
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
Time and space complexity analysis
For each pair, there are a total of 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)
= 1 + 3*(n-2)/2 = 3n/2 – 2 (If n is even)
Time Complexity = O(n), but 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(1), 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
You can find some of these problems on leetcode or other coding platforms. Explore and Practice!
Enjoy learning, Enjoy coding, Enjoy algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.