Number of Pairs Satisfying Inequality in Java
In this tutorial, we will learn about number of pairs satisfying inequality in Java. Counting pairs of elements in an array or collection that match a condition specified by an inequality is commonly referred to as the "number of pairs satisfying an inequality". Counting the number of pairs in an array (or two arrays) that satisfy a certain inequality can be approached in a basic way by looking at all possible pairings and determining whether they match the given condition.
Examples:
Example 1:
Input: nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
Output: 3
Explanation:
Three sets of objects meet the required criteria:
- 3 - 2 <= 2 - 2 + 1 for i = 0 and j = 1. Given that 1 <= 1 and i < j, this pair meets the requirements.
- 3 - 5 <= 2 - 1 + 1 for i = 0 and j = 2. These requirements are met by this combination because i < j and -2 <= 2.
- If i = 1 and j = 2, then 2 - 5 <= 2 - 1 + 1. These requirements are met by this combination because i < j and -3 <= 2.
Therefore, we return 3.
Example 2:
Input: nums1 = [3,-1], nums2 = [-2,2], diff = -1
Output: 0
Explanation:
Since there does not exist any pair that satisfies the conditions, we return 0.
Approach: Using binary indexed tree
ALGORITHM:
Step 1: Make a Binary Indexed Tree called tree, with a size large enough to accommodate every possible value after normalization (to account for negative integers).
Step 2: Accommodate negative values, a fixed number is added to each index. BIT does not allow for negative indices, this adjusts the index range to accommodate query and update operations with negative values.
Step 3: Determine the difference, v = a - b, for each element an in nums1 and b in nums2. Next, add v to the BIT (tree) so that this value is effectively counted.
Step 4: Find the count of all values in the BIT that are less than or equal to v + diff, the query will use the identical values, a and b. This is so that nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff, the all-time previous indices i that we are searching for.
Step 5: Return the count of valid i indices that precede the current index j of the query method. In order to meet our pairs requirement. For each j, this count is added to our response answer.
Step 6: Determine, the least significant bit that has been set to for a given number x. The BinaryIndexedTree class has a static function called lowbit. This function aids in navigating to parent or child nodes during update and query operations within the bidirectional update table (BIT).
Filename: PairInequality.java
public class PairInequality
{
public static void main(String[] args)
{
// Given array
int[] array = {1, 2, 3, 4, 5,6};
int[] bit = new int[array.length + 1];
// initialize the count
int count = 0;
for (int i = 0; i<array.length; i++) {
update(bit, array[i], 1);
count += query(bit, array[i] - 1);
}
System.out.println("Number of pairs satisfying the inequality: " + count);
}
private static void update(int[] bit, int index, int value)
{
for (; index <bit.length; index += index & -index)
{
bit[index] += value;
}
}
private static int query(int[] bit, int index) {
int sum = 0;
for (; index > 0; index -= index & -index)
{
sum += bit[index];
}
return sum;
}
}
Output:
Number of pairs satisfying the inequality: 15
Time complexity: The time complexity of the program is O( nlogn), where n is the number of elements in the given array.
Space complexity: The space complexity of the program is O(n), where n is the number of elements in the given array.