Count values less than or equal to in another array

Difficulty: Easy, Asked-in: Amazon

Key takeaway: An excellent problem to learn problem solving using sorting and searching.

Let’s understand the problem

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.

Examples

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.

Discussed Solution Approaches

• Brute force approach using two nested loops
• Using the sorting and binary search
• Using sorting and two pointers approach
• Using direct address table: Similar to counting sort

Brute force approach using two nested loops

Solution idea

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.

Solution steps

1. We define an array output[m] to store the output.
2. Now we run an outer loop from i = 0 to m - 1 to iterate over each element in X[]. Inside the outer loop, we initialize a variable count as 0. This variable will keep track of the count of elements in Y[] that are less than or equal to the current element X[i].
3. Next, we run an inner loop from j = 0 to n - 1 to iterate over each element in Y[]. Within the inner loop, we check if Y[j] ≤ X[i]. If the condition is true, we increment the count variable by 1.
4. After the inner loop, we store the value of the count in the output[i].
5. Finally, after the completion of the outer loop, we return output[].

Solution code C++

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;
}

Solution code Python

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

Time and space complexity analysis

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).

Using the sorting and binary search

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!

Solution idea

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[].

Solution steps

1. We sort the second array Y[] in increasing order.
2. Now, for each element X[i] in the first array, we perform a modified binary search on the array Y[] to find the index of the largest element that is smaller than or equal to X[i]. In the case of duplicate elements, the modified binary search will return the last index of occurrence of X[i].
3. The index + 1 is the count of elements. We store this value in the output array.

Solution code C++

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;
}

Solution code Python

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

Time and space complexity analysis

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).

Using sorting and two pointers approach

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].

Solution Idea

1. Sort both arrays to enable efficient element comparison.
2. Initialize a pointer j as 0 to traverse array Y[].
3. Iterate over each element of X[] from i = 0 to m - 1.
4. For each X[i], compare it with Y[j] using an inner while loop. The loop runs until j < n and Y[j] ≤ X[i].
5. In each iteration of the while loop, if Y[j] ≤ X[i], increment pointer j to the next element in Y[] that might be less than or equal to X[i].
6. After the while loop, the count of elements in Y[] that are less than or equal to X[i] is j. Store this value in the output array.

Note: The output of this solution will be sorted.

Solution code C++

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;
}

Solution code Python

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

Time and space complexity analysis

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).

Using direct address table: Similar to counting sort

Solution idea

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].

Solution steps

1. We first create a count[] array of size K + 1 and initialize all values to 0.
2. Next, we traverse the array Y[] and increment the count of each element Y[i] at count[Y[i]]. We do this to build a frequency distribution of elements in Y[]. For example, if Y[] contains the elements [2, 3, 2, 1], then the count array would be [0, 1, 2, 1]. 
3. After that, we calculate the prefix sum of the count[] array. To do this, we run a loop from 1 to K and add the value at the current index with the value at the previous index i.e. count[i] = count[i-1] + count[i]. This will update each element in the count array to store the cumulative count of elements up to that index. For example, if the count[] array is [0, 1, 2, 1], then the count[] array after this step would be [0, 1, 3, 4]. This means that there is 1 element less than or equal to 1, 3 elements less than or equal to 2, and 4 elements less than or equal to 3. 
4. Next, we traverse X[] and for each element X[i], we can use the count array to directly access the count of elements in Y[] that are less than or equal to element X[i]. For example, if X[] contains the elements [2, 1, 3], and the count array after step 3 is [0, 1, 3, 4], then the output would be [3, 1, 4] because there are 3 elements less than or equal to 2, 1 element less than or equal to 1, and 4 elements less than or equal to 3.

Solution code C++

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;
}

Solution code Python

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

Time and space complexity analysis

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).

Critical ideas to think!

• In the second approach, can you think of a different way to perform a modified binary search to find the index of the largest element that is smaller than or equal to X[i]?
• In the third approach, can you think of a different implementation of the two-pointer loop?
• Is it possible to solve this problem using a hash table or prefix array?
• Do the above approaches handle duplicates correctly in the array?
• Can you think of any other ideas to solve this problem?

Similar problems to solve

1. Given an array of integers, for each element, count the number of elements to its right that are smaller than or equal to it.
2. Given a sorted array of integers, count the number of elements that are within a given range [lower, upper].
3. Given an array of intervals, for each interval, find the index of the interval in the array such that the start of that interval is greater than or equal to the end of the current interval. Return the indices in an array or data structure.
4. Given a non-negative integer n, count the number of numbers with unique digits that are less than or equal to n.
5. Given four arrays of integers, count the number of quadruples (a, b, c, d) where a is from the first array, b is from the second array, c is from the third array, and d is from the fourth array, such that a + b + c + d equals zero.

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!