Count Good triplets in an Array in Java
In this tutorial, we are going to Count good triplets in an array in Java. Our task is to identify "good triplets" in the two arrays, numA1 and numA2, that are provided. These arrays are permutations of [0, 1,..., n - 1]. A good triplet is a set of three distinct numerical values that appear in numA1 and numA2 in increasing order of the correct position. In order to clarify, a good triplet is defined as a set (x, y, z) such that posn1[x] < posn1[y]< posn1[z] and posn2[x] < posn2[y] < posn2[z], and 0 <= x, y, z <= n - 1. The reason for this is due to the fact that posV1 and posV2 are the index values of v in numA1 and numA2, respectively. The overall number of good triplets can be returned.
Example 1:
Input: numA1 = {3, 0, 2, 1}
numA2 = {0, 3, 2, 1}
Output: 2
Explanation: (0, 1, 2), (0, 1, 3), (0, 2, 3), and (1,2,3) are 4 possible combinations of triplets (x, y, z) which are in order of pos1[x] < pos1[y] < pos1[z]. Among these triplets, only (0,1,2) and (0, 2, 3) positions satisfies pos2[x] < pos2[y] < pos2[z] among the triplets. Therefore, the 2 good triplets are returned.
Example 2:
Input: numA1 = {2, 4, 3, 0, 1}
numA2 = {4, 2, 3, 1, 0}
Output: 4
Explanation: There are 10 combinations of triplets (x, y, z), which are in order of pos1[x] < pos1[y] < pos1[z]. The subsequent four combinations (0, 1, 2), (0, 2, 3), (0, 3, 4), and (2, 3, 4) are meet the two prerequisites among the ten combinations.
Approach: Using Divide and Conquer
In this approach, we efficiently count "good triplets" within two arrays named numA1 and numA2. First of all, we initialise the arrays named numA1, numA2, indices, left, and right counts and compute the element indices from Array called numA1 for quick and easy lookup during merging. Now, we will recursively divide the arrays into small sub-arrays and merge them while simultaneously counting the number of good triplets that occured. Let's multiply the corresponding elements of the left and right count arrays and add them to the final result to determine the count of good triplets by iterating across the arrays during the merging step. Finally, we return the count of good triplets.
FileName: GoodTripletsCountInArr.java
public class GoodTripletsCountInArr {
int[] numA1, numA2, indicies1;
int[] left, right;
public long goodTriplets(int[] numA1, int[] numA2) {
int len = numA1.length;
this.numA1 = numA1;
this.numA2 = numA2;
indicies1 = new int[len];
for (int i = 0; i < len; ++i) {
indicies1[numA1[i]] = i;
}
left = new int[len];
right = new int[len];
divideAndConquer(0, len - 1);
long output = 0L;
for (int i = 0; i < len; ++i) {
output += (long)left[i] * (long)right[i];
}
return output;
}
public void divideAndConquer(int l, int r) {
if (l == r) {
return;
}
// Divide
int mid = l + (r - l) / 2;
divideAndConquer(l, mid);
divideAndConquer(mid + 1, r);
// Conquer
int i = 0, j = 0, k = 0;
int[] temp1 = new int[mid - l + 1];
int[] temp2 = new int[r - mid];
System.arraycopy(numA2, l, temp1, 0, mid - l + 1);
System.arraycopy(numA2, mid + 1, temp2, 0, r - mid);
int[] temp = new int[r - l + 1];
// populating left
while (i < temp1.length && j < temp2.length) {
if (indicies1[temp1[i]] < indicies1[temp2[j]]) {
temp[k] = temp1[i];
++i;
} else {
temp[k] = temp2[j];
left[temp2[j]] += i;
++j;
}
++k;
}
while (i < temp1.length) {
temp[k] = temp1[i];
++i;
++k;
}
while (j < temp2.length) {
temp[k] = temp2[j];
left[temp2[j]] += i;
++j;
++k;
}
System.arraycopy(temp, 0, numA2, l, r - l + 1);
// Populating right
i = temp1.length - 1;
j = temp2.length - 1;
k = temp.length - 1;
while (i >= 0 && j >= 0) {
if (indicies1[temp1[i]] > indicies1[temp2[j]]) {
right[temp1[i]] += temp2.length - j - 1;
--i;
} else {
--j;
}
}
while (i >= 0) {
right[temp1[i]] += temp2.length - j - 1;
--i;
}
}
// main method
public static void main(String[] args) {
// provide input values
int[] numA1 = {4, 0, 1, 3, 2};
int[] numA2 = {4, 1, 0, 2, 3};
GoodTripletsCountInArr gt = new GoodTripletsCountInArr ();
long res = gt.goodTriplets(numA1, numA2);
System.out.println("Number of good triplets: " + res);
}
}
Output:
Number of good triplets: 4
Complexity Analysis: The program uses a divide and conquer algorithm that gives time complexity of O(n) because of a recursive division of arrays. Merging subarrays and updating left and right arrays also takes O(N) time, so the final result is O(N * log(N)) complexity. The space complexity is O(N) because the algorithm uses n arrays. Also, the recursion stack takes extra space of O(logN) during the divide and conquer process. Hence, the overall space complexity is O(N).
Approach: Using Binary Indexed Tree
In this approach, firstly, we initialize variables that are required, including arrays left and right to monitor the counts for each element on the left and right, and resl to keep the count of good triplets. Also, declare an array called posn to store the positions of elements in the numA2 array. Now, initialise a BIT with the length of numA1, iterate over the numA2 array to fill the posn array with element indices, and then move from left to right through the numA1 array. Using BIT, update the left array. After that, repeat the traversal, compute the index of each element as well as the count of elements remaining on the right, and update the right array with the help of BIT. Iterate over the numA1 array and multiply the corresponding elements from both arrays. Let's store the outcome in the variable called resl. Finally, we should return the count of good triplets.
FileName: FindTheCountOfGoodTriplets.java
public class FindTheCountOfGoodTriplets {
public long goodTriplets(int[] numA1, int[] numA2) {
long resl = 0;
// arrays to store count values
long[] leftCnt = new long[numA1.length];
long[] rightCnt = new long[numA1.length];
int[] posn = new int[numA1.length];
for (int i = 0; i < numA1.length; i++) posn[numA2[i]] = i;
// creating a binary indexed tree
BinaryIndexedTree bTree = new BinaryIndexedTree (numA1.length);
// left counts
for (int i = 0; i < numA1.length; i++){
int idx = posn[numA1[i]] + 1;
leftCnt[i] = bTree.queryBIT(idx - 1);
bTree.updateBIT(idx, 1);
}
bTree = new BinaryIndexedTree (numA1.length);
// right counts
for (int i = numA1.length - 1; i >= 0; i--){
int idx = posn[numA1[i]] + 1;
int currTotal = numA1.length - 1 - i;
rightCnt[i] = currTotal - bTree.queryBIT(idx);
bTree.updateBIT(idx, 1);
}
// counting for good triplets
for (int i = 0; i < numA1.length; i++)
resl += leftCnt[i] * rightCnt[i];
return resl;
}
// binary indexed tree class
class BinaryIndexedTree {
private int[] tree;
public BinaryIndexedTree(int n){
tree = new int[n + 2];
}
// find least significant bit
private int lsb(int i){
return i &(-i);
}
// query method
public int queryBIT(int i){
int Totalsum = 0;
for (; i > 0; i -= lsb(i)) Totalsum += tree[i];
return Totalsum;
}
// update method
public void updateBIT(int i, int val){
for (; i < tree.length; i += lsb(i)) tree[i] += val;
}
}
// main method
public static void main(String[] args) {
FindTheCountOfGoodTriplets gt = new FindTheCountOfGoodTriplets();
// Provide input values
int[] numA1 = {3, 0, 2, 1};
int[] numA2 = {0, 3, 2, 1};
long resl = gt.goodTriplets(numA1, numA2);
System.out.println("Count of good triplets: " + resl);
}
}
Output:
Count of good triplets: 2
Complexity Analysis: The Program has the time complexity of O(n log n), where n is the length of input arrays numA1 and numA2. Because it uses a Binary Indexed Tree (BIT) for efficient range queries and updates, taking O(n log n) time for the construction and calculation of left and right counts. The space complexity is O(n) due to the use of two additional arrays, leftCnt and rightCnt, of length n, and the BIT data structure requires an array of length n+2.
Approach: Using Segment Tree
The approach follows a systematic process. Firstly, to quickly access an element's index in numA2, construct a mapping named elemToIdxMappingInB. Initialize a segment tree named segTree with a size of n * 4 + 1, where n is the length of numA1. Now, Iterate over numA1 and retrieve the current element index. Let's calculate the number of common elements on the left side, then find the number of unique elements; after that, compute the number of common elements on the right side. Update the result by adding the product of the number of common elements on the left and right sides. Return the final result, which represents the count of good triplets.
FileName: FindTheCountOfGoodTriplets.java
// importing HashMap and Map interfaces
import java.util.HashMap;
import java.util.Map;
public class FindTheCountOfGoodTriplets {
public long goodTriplets(int numA1[], int numA2[]) {
Map<Integer, Integer> elemToIdxMappingInB = new HashMap<>();
int n = numA1.length;
long segTree[] = new long[n * 4 + 1];
long resl = 0;
for (int i = 0; i < numA2.length; i++) {
elemToIdxMappingInB.put(numA2[i], i);
}
update(segTree, 1, 0, n - 1, elemToIdxMappingInB.get(numA1[0]));
for (int i = 1; i < n; i++) {
int indexInB = elemToIdxMappingInB.get(numA1[i]);
// left count
long commonEleOnLeft = query(segTree, 1, 0, n - 1, 0, indexInB);
long uniqueEleOnLeftInA = i - commonEleOnLeft;
long eleAfterIndexInB = n - 1 - indexInB;
// right count
long commonEleOnRight = eleAfterIndexInB - uniqueEleOnLeftInA;
resl += commonEleOnLeft * commonEleOnRight;
update(segTree, 1, 0, n - 1, indexInB);
}
return resl;
}
// update method
private void update(long[] st, int idx, int start, int end, int updateIdx) {
if (start == end) {
st[idx] += 1;
return;
}
int mid = start + (end - start) / 2;
if (updateIdx <= mid) update(st, idx * 2, start, mid, updateIdx);
else update(st, idx * 2 + 1, mid + 1, end, updateIdx);
st[idx] = st[idx * 2] + st[idx * 2 + 1];
}
// query method
private long query(long[] st, int idx, int start, int end, int queryStart, int queryEnd) {
if (end < queryStart || start > queryEnd) return 0;
if (start >= queryStart && end <= queryEnd) return st[idx];
int mid = start + (end - start) / 2;
long left = query(st, idx * 2, start, mid, queryStart, queryEnd);
long right = query(st, idx * 2 + 1, mid + 1, end, queryStart, queryEnd);
return left + right;
}
// main method
public static void main(String[] args) {
FindTheCountOfGoodTriplets gt = new FindTheCountOfGoodTriplets();
// provide input values
int[] numA1 = {2, 4, 3, 0, 1};
int[] numA2 = {4, 2, 3, 1, 0};
long resl = gt.goodTriplets(numA1, numA2);
System.out.println("Count of good triplets: " + resl);
}
}
Output:
Count of good triplets: 4
Time complexity: The program consumes time complexity of O(n) to loop over numA2, and for loop over numA1 takes O(n log N). Therefore, the overall time complexity is O(n log n + n), i.e., O(n log n).
Space complexity: The space complexity is O(2n) = O(n) because the program takes space for the elemToIdxMappingInB map and segment tree.
Approach: Using Brute Force
In this approach, first of all, we create an array called posn to store positions of elements from array numA2 and iterate through it. Then, store the elements index in it. For each at index I in numA1, find its position mid numA2 by using array posn. Now, initialize two variables named cntLeft and cntRight to count the elements on the left and right sides of numA1. Multiply the variables cntLeft and cntRight to find the count of good triplets. Let's store the result in a variable called resl. Finally, whatever the count of good triplets obtained are returned.
FileName: FindTheCountOfGoodTriplets.java
public class FindTheCountOfGoodTriplets {
public long goodTriplets(int[] numA1, int[] numA2) {
long resl = 0;
int posn[] = new int[numA1.length];
for (int i = 0; i < numA2.length; i++)
posn[numA2[i]] = i;
for (int i = 1; i < numA1.length - 1; i++) {
int mid = posn[numA1[i]];
int cntLeft = 0, cntRight = 0;
for (int j = 0; j < i; j++) if (posn[numA1[j]] < mid) cntLeft++;
for (int j = i + 1; j < numA1.length; j++) if (posn[numA1[j]] > mid) cntRight++;
resl += cntLeft * cntRight;
}
return resl;
}
// main method
public static void main(String[] args) {
FindTheCountOfGoodTriplets gt = new FindTheCountOfGoodTriplets();
// provide input values
int numA1[] = {2, 4, 3, 0, 1};
int numA2[] = {4, 2, 3, 1, 0};
long resl = gt.goodTriplets(numA1, numA2);
System.out.println("Number of good triplets: " + resl);
}
}
Output:
Number of good triplets: 4
Time complexity: The above program uses the Brute force approach, taking the time complexity of O(n^2) for two nested loops to iterate over arrays numA1 and numA2.
Space Complexity: The space complexity is O(n) because an array called posn of the same length as numA1 is used to store the positions of elements in numA2. Therefore, the space complexity is O(n), where n is the length of numA1 and numA2 arrays.