Count Good Triplets in an Array - Practice Coding Problems

Count Good Triplets in an Array - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Hard

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 pos1[v] as the index of the value v in nums1 and pos2[v] 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 pos1[x] < pos1[y] < pos1[z] and pos2[x] < pos2[y] < pos2[z].

Return the total number of good triplets.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: The triplet (0,1,3) is good: positions in nums1 are (1,2,3) and in nums2 are (0,1,3), both increasing.

Example 2 — No Valid Triplets

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

› Output: 4

💡 Note: Multiple valid triplets exist with the given position constraints.

Example 3 — Minimum Size

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

› Output: 0

💡 Note: No valid triplets possible with these position arrangements.

Constraints

n == nums1.length == nums2.length
3 ≤ n ≤ 100
0 ≤ nums1[i], nums2[i] ≤ n - 1
nums1 and nums2 are permutations of [0, 1, ..., n - 1].

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two permutation arrays with position constraints

Position Analysis

Find elements with increasing positions in both arrays

Count Triplets

Count all valid triplet combinations

Key Takeaway

🎯 Key Insight: Fix middle elements and count valid left/right pairs that maintain position order in both arrays

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to fix each element as a middle element and count valid left/right pairs. For each middle element, count elements that appear before it in both arrays (left) and after it in both arrays (right). The answer is sum of leftCount × rightCount for all middle elements. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Merge Sort with Inversion Count	O(n²)	O(n)	Transform problem to counting inversions using merge sort technique
Binary Search with Sorted Processing	O(n² log n)	O(n)	Process elements by position order and use binary search to count valid predecessors
Brute Force Triple Loop	O(n³)	O(n)	Check all possible triplets and verify ordering in both arrays

Merge Sort with Inversion Count — Algorithm Steps

Map nums2 elements to their relative order in nums1
Use merge sort to count inversions efficiently
Count triplets by finding increasing subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Maps

Create fast lookup for element positions

For Each Middle

Count valid left and right elements efficiently

Multiply Counts

Total triplets with this middle element

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums1, int* nums2, int n) {
    int pos1[2005], pos2[2005];
    
    for (int i = 0; i < n; i++) {
        pos1[nums1[i]] = i;
        pos2[nums2[i]] = i;
    }
    
    long long count = 0;
    // For each possible middle element
    for (int mid = 0; mid < n; mid++) {
        int leftCount = 0;
        int rightCount = 0;
        
        // Count valid left elements
        for (int left = 0; left < n; left++) {
            if (pos1[left] < pos1[mid] && pos2[left] < pos2[mid]) {
                leftCount++;
            }
        }
        
        // Count valid right elements
        for (int right = 0; right < n; right++) {
            if (pos1[right] > pos1[mid] && pos2[right] > pos2[mid]) {
                rightCount++;
            }
        }
        
        count += (long long)leftCount * rightCount;
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums1[2005], nums2[2005];
    int n1 = 0, n2 = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums1[n1++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums2[n2++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(nums1, nums2, n1));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each middle element, count valid left and right pairs in O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Arrays for coordinate compression and position mappings

⚡ Linearithmic Space

15.4K Views

Medium Frequency

~35 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Merge Sort with Inversion Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler