Interview AiBox logo
Interview AiBox
#2179
Hard
auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Count Good Triplets in an Array

Count Good Triplets in an Array requires tracking index orders across two permutations efficiently using binary search.

arraybinary searchdivide and conquerbinary indexed treesegment tree
category

7

Topics

code_blocks

5

Code langs

hub

3

Related

play_arrowStart Solutionarrow_forward
speedComplexityopen_in_newLeetCode

Practice Focus

Hard · Binary search over the valid answer space

bolt

Answer-first summary

Count Good Triplets in an Array requires tracking index orders across two permutations efficiently using binary search.

Interview AiBox logo

Ace coding interviews with Interview AiBox guidance for Binary search over the valid answer space

Try AiBox Copilotarrow_forward

This problem focuses on finding triplets (x, y, z) where the relative order in both nums1 and nums2 is increasing. Use a binary search over positions to efficiently count how many valid x exist before each y and how many valid z exist after. Properly indexing values in both arrays and combining counts avoids O(n^3) brute force.

Problem Statement

Given two arrays nums1 and nums2 of length n, both are permutations of [0, 1, ..., n - 1]. A triplet (x, y, z) is good if in both arrays, the positions of x, y, z are strictly increasing.

Return the total number of good triplets. For example, with nums1 = [2,0,1,3] and nums2 = [0,1,2,3], there is only 1 triplet that satisfies the order condition in both arrays.

Examples

Example 1

Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]

Output: 1

There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3). Out of those triplets, only the triplet (0,1,3) satisfies pos2x < pos2y < pos2z. Hence, there is only 1 good triplet.

Example 2

Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]

Output: 4

The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).

Constraints

  • n == nums1.length == nums2.length
  • 3 <= n <= 105
  • 0 <= nums1[i], nums2[i] <= n - 1
  • nums1 and nums2 are permutations of [0, 1, ..., n - 1].

Solution Approach

Map values to indices

Create a mapping of each value to its index in nums2. Then transform nums1 into an array of nums2 indices. This allows converting the problem into counting increasing subsequences of length 3.

Use Binary Indexed Tree

Iterate through the transformed nums1. For each value y, use a BIT to count how many x exist before it and update counts for z candidates. This ensures O(n log n) time complexity.

Combine counts for final result

For each y, multiply the number of valid x before it by the number of valid z after it using prefix and suffix counts. Summing these products gives the total number of good triplets efficiently.

Complexity Analysis

Metric Value
Time O(n\times\log{n})
Space O(n)

Time complexity is O(n\times\log{n}) due to binary indexed tree queries and updates for each element. Space complexity is O(n) for mapping indices and auxiliary BIT arrays.

What Interviewers Usually Probe

  • Check if candidate triplets satisfy order in both arrays instead of just one.
  • Expect O(n log n) solution using index mapping and efficient counting structures.
  • Be careful with off-by-one errors when transforming positions into counts for BIT.

Common Pitfalls or Variants

Common pitfalls

  • Attempting a brute-force O(n^3) approach which will time out for n up to 10^5.
  • Mixing positions of values instead of using consistent index mapping.
  • Counting x, y, z independently without considering their relative order in both arrays.

Follow-up variants

  • Count good quadruplets instead of triplets with similar order constraints.
  • Arrays are not full permutations but contain distinct values in a limited range.
  • Instead of counting, return all good triplets explicitly (may need O(n^3) time).

FAQ

What is a good triplet in Count Good Triplets in an Array?

A good triplet is (x, y, z) where the positions of x, y, z are strictly increasing in both nums1 and nums2.

Why use binary search or BIT in this problem?

Binary search or BIT allows counting how many x exist before each y efficiently, avoiding the O(n^3) brute-force approach.

Can nums1 and nums2 contain duplicates?

No, both arrays are permutations of [0, 1, ..., n - 1], so each value appears exactly once.

What is the time complexity of the efficient solution?

The time complexity is O(n\times\log{n}) due to binary indexed tree operations for each element.

How can I verify my solution?

Transform nums1 into nums2 index positions and check counts of increasing sequences length 3 using BIT; test small examples first.

terminal

Solution

Solution 1: Binary Indexed Tree (Fenwick Tree)

For this problem, we first use `pos` to record the position of each number in `nums2`, and then process each element in `nums1` sequentially.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        pos = {v: i for i, v in enumerate(nums2, 1)}
        ans = 0
        n = len(nums1)
        tree = BinaryIndexedTree(n)
        for num in nums1:
            p = pos[num]
            left = tree.query(p)
            right = n - p - (tree.query(n) - tree.query(p))
            ans += left * right
            tree.update(p, 1)
        return ans

Solution 2: Segment Tree

We can also use a segment tree to solve this problem. A segment tree is a data structure that efficiently supports range queries and updates. The basic idea is to divide an interval into multiple subintervals, with each subinterval represented by a node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        pos = {v: i for i, v in enumerate(nums2, 1)}
        ans = 0
        n = len(nums1)
        tree = BinaryIndexedTree(n)
        for num in nums1:
            p = pos[num]
            left = tree.query(p)
            right = n - p - (tree.query(n) - tree.query(p))
            ans += left * right
            tree.update(p, 1)
        return ans

Continue Practicing

#2426 number of pairs satisfying inequality#1649 create sorted array through instructions#493 reverse pairs
category

Continue Topic

array

Practice more edge cases under the same topic.

arrow_forwardauto_awesome

Continue Pattern

Binary search over the valid answer space

Expand the same solving frame across more problems.

arrow_forwardsignal_cellular_alt

Same Difficulty Track

Hard

Stay on this level to stabilize interview delivery.

arrow_forward
Count Good Triplets in an Array Solution: Binary search over the valid answer s… | LeetCode #2179 Hard