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).
How GhostInterview Helps
- Automatically maps values to positions in both arrays to reduce error-prone manual indexing.
- Tracks prefix and suffix counts efficiently using binary indexed tree to avoid O(n^3) checks.
- Provides step-by-step validation for each value y to ensure only valid triplets contribute to the total.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Count Good Triplets in an Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Count Good Triplets in an Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count pairs in two arrays satisfying a given inequality condition using binary search over the valid answer space.
Open problem page#1649 Create Sorted Array through InstructionsThe problem asks to compute the cost of inserting elements into a sorted array using a series of instructions.
Open problem page#493 Reverse PairsCount the number of reverse pairs in a given integer array using efficient algorithms like binary search and merge sort.
Open problem page