Count Good Triplets in an Array

Hard Arrays & Hashing Fenwick Tree (BIT) Original on LeetCode

Count Good Triplets in an Array is a hard arrays & hashing problem solved with the fenwick tree (bit) pattern. The best approach, optimal (fenwick tree over positions), runs in O(n log n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every triple) up.

Problem

You are given two arrays nums1 and nums2 of length n, each a permutation of 0, 1, …, n - 1.

Call a triplet of distinct values (x, y, z) good when the three values appear in the order x, y, z (left to right) in nums1 and also in that same order in nums2. Return the number of good triplets.

Examples

Example 1

Input
nums1 = [2, 0, 1, 3], nums2 = [0, 2, 1, 3]
Output
2
Why
(2, 1, 3) and (0, 1, 3) appear in that order in both arrays. Any triplet using both 2 and 0 fails, since they swap places between the arrays.

Example 2

Input
nums1 = [0, 1, 2, 3], nums2 = [0, 1, 2, 3]
Output
4
Why
The arrays are identical, so every choice of 3 values out of 4 is good.

Example 3

Input
nums1 = [0, 1, 2], nums2 = [2, 1, 0]
Output
0
Why
The arrays list the values in opposite orders, so no two values appear in the same order in both, let alone three.

Constraints

  • 3 <= n <= 10^5 where n == nums1.length == nums2.length
  • nums1 and nums2 are both permutations of 0, 1, …, n - 1.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every triple)O(n³)O(n)
Fix the middle elementO(n²)O(n)
Optimal (Fenwick tree over positions)O(n log n)O(n)

1Brute force (try every triple)

TimeO(n³)C(n, 3) triples are checked.
SpaceO(n)pos2 and arr.

Let pos2[v] be the index of value v in nums2 and build arr[i] = pos2[nums1[i]]. A triple of indices i < j < k in nums1 is good exactly when arr[i] < arr[j] < arr[k]. Check all triples.

  1. Build pos2 and arr.
  2. For every i < j < k, count it if arr[i] < arr[j] < arr[k].
class Solution {
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] pos2 = new int[n];
        for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = pos2[nums1[i]];
        long count = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                if (arr[j] <= arr[i]) continue;
                for (int k = j + 1; k < n; k++)
                    if (arr[k] > arr[j]) count++;
            }
        return count;
    }
}

2Fix the middle element

TimeO(n²)Two linear scans for each of the n middles.
SpaceO(n)pos2 and arr.

For each middle index j of arr, count the indices to its left with a smaller value and the indices to its right with a larger value. Every pairing of one from each side gives a good triplet, so add the product.

  1. Build arr as before.
  2. For each j: left = #{i < j : arr[i] < arr[j]}, right = #{k > j : arr[k] > arr[j]}.
  3. Add left × right to the answer.
class Solution {
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] pos2 = new int[n];
        for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = pos2[nums1[i]];
        long total = 0;
        for (int j = 0; j < n; j++) {
            long left = 0, right = 0;
            for (int i = 0; i < j; i++) if (arr[i] < arr[j]) left++;
            for (int k = j + 1; k < n; k++) if (arr[k] > arr[j]) right++;
            total += left * right;
        }
        return total;
    }
}

3Optimal (Fenwick tree over positions)

TimeO(n log n)One Fenwick query and one update per index, each O(log n).
SpaceO(n)The Fenwick tree plus pos2 and arr.

Scan arr from left to right with a Fenwick (binary indexed) tree that marks the values already seen. At index j, a prefix query gives left = how many seen values are smaller than arr[j]. Of the j values to the left, j - left are larger, and there are n - 1 - arr[j] larger values overall, so right = (n - 1 - arr[j]) - (j - left). Add left × right.

  1. Build arr[i] = pos2[nums1[i]].
  2. For j = 0..n-1: left = query(arr[j] - 1); right = (n - 1 - arr[j]) - (j - left).
  3. total += left × right; then add 1 at position arr[j].
  4. Return total.
class Solution {
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] pos2 = new int[n];
        for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
        int[] tree = new int[n + 1];
        long total = 0;
        for (int j = 0; j < n; j++) {
            int p = pos2[nums1[j]];
            long left = 0;
            for (int x = p; x > 0; x -= x & -x) left += tree[x];
            long right = (n - 1 - p) - (j - left);
            total += left * right;
            for (int x = p + 1; x <= n; x += x & -x) tree[x]++;
        }
        return total;
    }
}

Edge cases to test

  • n = 3: the answer is 0 or 1
  • Identical arrays: every one of the C(n, 3) triplets is good
  • One array reversed relative to the other: answer 0
  • Large n: the answer exceeds 32 bits, so use a 64-bit result

Hints

Hint 1

Rename values by their position in nums2. Then a triplet is good exactly when the renamed values form an increasing subsequence of length 3 inside nums1.

Hint 2

Fix the middle element. The number of good triplets with that middle is (smaller values to its left) × (larger values to its right).

Hint 3

Count 'smaller values to the left' for every index with a Fenwick tree over values while scanning left to right; the 'larger to the right' count follows by arithmetic.

FAQ

What is the best time complexity for Count Good Triplets in an Array?

Optimal (Fenwick tree over positions) runs in O(n log n) time and O(n) extra space. One Fenwick query and one update per index, each O(log n).

Which pattern does Count Good Triplets in an Array use?

It is a arrays & hashing problem that uses the fenwick tree (bit) pattern.

Is there a brute force solution for Count Good Triplets in an Array?

Yes. Brute force (try every triple) takes O(n³) time and O(n) space. Let pos2[v] be the index of value v in nums2 and build arr[i] = pos2[nums1[i]].

Which edge cases should I test for Count Good Triplets in an Array?

n = 3: the answer is 0 or 1; Identical arrays: every one of the C(n, 3) triplets is good; One array reversed relative to the other: answer 0; Large n: the answer exceeds 32 bits, so use a 64-bit result.