You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, ..., n - 1].
A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1v as the index of the value v in nums1 and pos2v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n - 1, such that pos1x < pos1y < pos1z and pos2x < pos2y < pos2z.
Return the total number of good triplets.
Example 1:
Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3] Output: 1 Explanation: 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 Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).
Constraints:
n == nums1.length == nums2.length3 <= n <= 1050 <= nums1[i], nums2[i] <= n - 1nums1 and nums2 are permutations of [0, 1, ..., n - 1].Problem Overview: You receive two permutations nums1 and nums2 of length n. A triplet (i, j, k) is considered good if i < j < k and the relative order of the values in nums2 is also increasing. The task reduces to counting how many index triplets maintain the same ordering in both arrays.
The key observation: instead of comparing elements across two arrays repeatedly, map each value in nums1 to its index in nums2. This converts the problem into counting increasing triplets in a single array of positions.
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
Check every possible triple (i, j, k) with three nested loops. For each triplet, compare their positions in nums2 and verify the order constraint. This works because both arrays contain the same elements. The approach is simple and confirms the definition of a good triplet, but the cubic runtime becomes impractical even for moderate n. Still useful for reasoning about the problem and validating smaller test cases.
Approach 2: Relative Position Array + Binary Indexed Tree (O(n log n) time, O(n) space)
Create a map from value to index in nums2. Transform nums1 into a new array pos where pos[i] represents the position of nums1[i] inside nums2. Now the task becomes counting increasing triplets in pos. For each index j, compute how many values smaller than pos[j] appear to the left and how many larger values appear to the right. Multiply these counts to determine how many triplets use j as the middle element.
A Binary Indexed Tree efficiently maintains prefix counts while iterating. Each query finds how many processed elements are smaller than the current position, and updates insert the current position into the structure. This converts the naive counting problem into logarithmic updates and queries.
Other structures like a Segment Tree or divide-and-conquer methods such as merge-based counting from divide and conquer can solve the same increasing-triplet counting task with similar O(n log n) complexity.
Recommended for interviews: The relative position + Binary Indexed Tree approach is the expected solution. Interviewers want to see that you recognize the permutation mapping trick and reduce the problem to counting increasing subsequence triplets. Mentioning the brute force method shows you understand the baseline, but implementing the O(n log n) counting solution demonstrates strong data structure skills.
In this approach, we try all possible triplets (x, y, z) and check if they satisfy the good triplet condition.
This function iterates over all possible triplets, checking if the positions in both arrays are in increasing order. It uses a nested loop structure to achieve this.
Time Complexity: O(n^3), Space Complexity: O(1)
Instead of checking every possible triplet, we utilize position arrays to track indices, reducing unnecessary checks and improving efficiency.
This C solution initializes arrays to store the position of each element, cutting down the outer operations from O(n^3) to O(n^2) since position lookups are O(1).
Time Complexity: O(n^2), Space Complexity: O(n)
For this problem, we first use pos to record the position of each number in nums2, and then process each element in nums1 sequentially.
Consider the number of good triplets with the current number as the middle number. The first number must have already been traversed and must appear earlier than the current number in nums2. The third number must not yet have been traversed and must appear later than the current number in nums2.
Take nums1 = [4,0,1,3,2] and nums2 = [4,1,0,2,3] as an example. Consider the traversal process:
4. At this point, the state of nums2 is [4,X,X,X,X]. The number of values before 4 is 0, and the number of values after 4 is 4. Therefore, 4 as the middle number forms 0 good triplets.0. The state of nums2 becomes [4,X,0,X,X]. The number of values before 0 is 1, and the number of values after 0 is 2. Therefore, 0 as the middle number forms 2 good triplets.1. The state of nums2 becomes [4,1,0,X,X]. The number of values before 1 is 1, and the number of values after 1 is 2. Therefore, 1 as the middle number forms 2 good triplets.2. The state of nums2 becomes [4,1,0,2,3]. The number of values before 2 is 4, and the number of values after 2 is 0. Therefore, 2 as the middle number forms 0 good triplets.We can use a Binary Indexed Tree (Fenwick Tree) to update the occurrence of numbers at each position in nums2, and quickly calculate the number of 1s to the left of each number and the number of 0s to the right of each number.
A Binary Indexed Tree, also known as a Fenwick Tree, efficiently supports the following operations:
update(x, delta): Add a value delta to the number at position x in the sequence.query(x): Query the sum of the sequence in the range [1, ..., x], i.e., the prefix sum at position x.Both operations have a time complexity of O(log n). Therefore, the overall time complexity is O(n log n), where n is the length of the array nums1. The space complexity is O(n).
Python
Java
C++
Go
TypeScript
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.
The segment tree divides the entire interval into multiple non-overlapping subintervals, with the number of subintervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, all of which are contained within a larger interval that includes the element.
[1, N].[x, x].[l, r], its left child represents [l, mid], and its right child represents [mid + 1, r], where mid = ⌊(l + r) / 2⌋ (floor division).The time complexity is O(n log n), where n is the length of the array nums1. The space complexity is O(n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), Space Complexity: O(1) |
| Optimized Approach Using Relative Position Arrays | Time Complexity: O(n^2), Space Complexity: O(n) |
| Binary Indexed Tree (Fenwick Tree) | — |
| Segment Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Check | O(n^3) | O(1) | Small inputs or when demonstrating the basic definition of a good triplet |
| Relative Position Array + Binary Indexed Tree | O(n log n) | O(n) | General case; efficient for large permutations and common interview solution |
| Merge Sort / Divide and Conquer Counting | O(n log n) | O(n) | Alternative when using merge-based counting techniques for ordered triplets |
Count Good Triplets in an Array | Segment Tree Concepts & Qns | Video 12 | Leetcode 2179 | MIK • codestorywithMIK • 13,742 views views
Watch 9 more video solutions →Practice Count Good Triplets in an Array with our built-in code editor and test cases.
Practice on FleetCode