Difficulty: Easy, Asked-in: Amazon
Key takeaway: An excellent problem to learn problem solving using sorting and searching.
Given two unsorted arrays X[] and Y[] of sizes m and n respectively, for each element in the first array X[], count the elements in the second array Y[] whose value is less than or equal to it. There can be duplicate elements in the arrays.
Input: X[] = [1, 2, 3, 4, 7, 9], Y[] = [0, 1, 2, 1, 1, 4], Output: [4, 5, 5, 6, 6, 6]
Explanation: The number of elements less than or equal to 1 is 4, 2 is 5, 3 is 5, 4 is 6, 7 is 6, and 9 is 6.
Input: X[] = [5, 10, 2, 6, 1, 8, 6, 12], Y[] = [6, 5, 11, 4, 2, 3, 7], Output: [4, 6, 1, 5, 0, 6, 5, 7]
Explanation: The number of elements less than or equal to 5 is 4, 10 is 6, 2 is 1, 6 is 5, 1 is 0, 8 is 6, 6 is 5, and 12 is 7.
One basic idea would be to use two nested loops: Iterate over each element X[i] using the outer loop and count the number of elements in Y[] that are less than or equal to element X[i] using an inner loop.
int* countElementsLessThanOrEqual(int X[], int m, int Y[], int n)
{
int* output = new int[m];
for (int i = 0; i < m; i = i + 1)
{
int count = 0;
for (int j = 0; j < n; j = j + 1)
{
if (Y[j] <= X[i])
{
count = count + 1;
}
}
output[i] = count;
}
return output;
}
def countElementsLessThanOrEqual(X, m, Y, n):
output = [0] * m
for i in range(m):
count = 0
for j in range(n):
if Y[j] <= X[i]:
count = count + 1
output[i] = count
return output
We are using two nested loops and doing constant operations at each iteration. The total number of nested loop iterations = m*n. So time complexity = m*n*O(1) = O(mn). We are using constant extra space. So space complexity = O(1).
Now the critical question is: How can we improve the time complexity further? In the above approach, we are performing a linear search to find all elements less than X[i] in Y[]. So, searching is one of the critical operations for solving this problem. Can we think of a more efficient idea for searching to improve efficiency? Let's think!
Searching in a sorted array can be done in O(logn) time. So, if we sort the second array Y[], we can use the binary search on Y[] to find elements that are less than or equal to each element in the first array X[].
int binarySearch(int Y[], int low, int high, int target)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (Y[mid] <= target)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
int* countElementsLessThanOrEqual(int X[], int m, int Y[], int n)
{
sort(Y, Y + n);
int* output = new int[m];
for (int i = 0; i < m; i = i + 1)
{
int index = binarySearch(Y, 0, n - 1, X[i]);
output[i] = index + 1;
}
return output;
}
def binarySearch(Y, low, high, target):
while low <= high:
mid = low + (high - low) // 2
if Y[mid] <= target:
low = mid + 1
else:
high = mid - 1
return high
def countElementsLessThanOrEqual(X, m, Y, n):
Y.sort()
output = [0] * m
for i in range(m):
index = binarySearch(Y, 0, n - 1, X[i])
output[i] = index + 1
return output
We sort the second array, and for each element in the second array, we perform a binary search on it. Let's assume we are using an efficient O(nlogn) sorting algorithm like heap sort and an iterative binary search.
Time complexity = Time complexity of heap sort + m * Time complexity of binary search = O(nlogn) + m * O(logn) = O((m + n) * logn).
Space complexity = Space complexity of heap sort + Space complexity of binary search = O(1) + O(1) = O(1).
Can we solve this problem without using binary search? One idea would be to sort both arrays and use a two-pointer approach to count the number of elements in Y[] that are less than or equal to element X[i].
Note: The output of this solution will be sorted.
int* countElementsLessThanOrEqual(int X[], int m, int Y[], int n)
{
int* output = new int[m];
sort(X, X + m);
sort(Y, Y + n);
int j = 0;
for (int i = 0; i < m; i = i + 1)
{
while (j < n && Y[j] <= X[i])
j = j + 1;
output[i] = j;
}
return output;
}
def countElementsLessThanOrEqual(X, m, Y, n):
output = [0] * m
X.sort()
Y.sort()
j = 0
for i in range(m):
while j < n and Y[j] <= X[i]:
j = j + 1
output[i] = j
return output
We are sorting both arrays and running a nested two-pointer loop. Suppose we are using an efficient O(nlogn) sorting algorithm heap sort.
The time complexity of the loop looks O(mn) at first sight. But this is not the correct analysis. At each iteration of the outer loop, based on the condition, we either increment pointer j from the same position as the previous iteration or do not increment it at all. So in the worst case, the pointer will traverse each element of the second array only once.
So time complexity of two pointers loop = Time complexity of traversing each element of array X[] using pointer i + Time complexity of traversing each element of the array Y[] using pointer j = O(m + n).
The overall time complexity = Time complexity of sorting the first array + Time complexity of sorting the second array + Time complexity of two pointers loop = O(nlogn) + O(mlogm) + O(m + n) = O(nlogn + mlogm). Here time complexity is still dominated by the sorting algorithm.
We are using the in-place sorting algorithm heap sort and some additional constant extra space. So space complexity = O(1) + O(1) = O(1).
In this approach, we use an idea similar to counting sort. So this approach works best when the values are in a small range that can be used as an index in an array. Suppose the input elements are in the range from 0 to some small value K.
Here, we count the occurrences of elements in array Y[] using the count[] array, calculate the prefix sum of the count[] array, and then use the count array to directly access the count of elements in Y[] that are less than or equal to element X[i].
int* countElementsLessThanOrEqual(int X[], int m, int Y[], int n)
{
int* output = new int[m];
int count[K + 1] = {0};
for (int i = 0; i < n; i = i + 1)
count[Y[i]] = count[Y[i]] + 1;
for (int i = 1; i <= K; i = i + 1)
count[i] = count[i] + count[i - 1];
for (int i = 0; i < m; i = i + 1)
output[i] = count[X[i]];
return output;
}
def countElementsLessThanOrEqual(X, m, Y, n):
output = [0] * m
count = [0] * (max(Y) + 1)
for i in range(n):
count[Y[i]] += 1
for i in range(1, len(count)):
count[i] = count[i] + count[i - 1]
for i in range(m):
output[i] = count[X[i]]
return output
We are using three single loops of size n, K and m. So time complexity = O(n) + O(K) + O(m) = O(n + K + m). We are using an extra array of size K + 1, so space complexity = O(K).
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.