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
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 res[2] = {max, min}
return res
}
Solution 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!
Solution Steps
Base case 2: If the array size is 2, we 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 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 (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
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 lminMax[2] = findMinMax(X, l, mid)
int rminMax[2] = findMinMax(X, mid+1, r)
if (lminMax[0] > rminMax[0])
max = lminMax[0]
else
max = rminMax[0]
if (lminMax[1] < rminMax[1])
min = lminMax[1]
else
min = rminMax[1]
}
int res[2] = {max, min}
return res
}
Solution Analysis
Let’s define the recurrence relation to analyze the 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, 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 scenarios, we are only doing 3 comparisons (in the 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 (in the 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
int[] findMinMax(int X[], int n)
{
int max, min, i
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
}
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 res[2] = {max, min}
return res
}
Solution 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 =
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(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
Enjoy learning, Enjoy coding, Enjoy algorithms!
Given two integer arrays X[] and Y[] of size m and n, respectively, write a program to find the intersection of these two arrays. The intersection of two arrays is a list of distinct numbers which are present in both arrays. The numbers in the intersection can be in any order.
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!