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].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.
C++
Java
Python
C#
JavaScript
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).
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), Space Complexity: O(n)
| 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) |
Count Good Triplets - Leetcode 1534 - Python • NeetCodeIO • 8,623 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