What is the time complexity of Count Good Triplets in an Array?

The optimal solution has a time complexity of O(n*log(n)).

What data structures are used to solve Count Good Triplets in an Array?

This problem uses Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Count Good Triplets in an Array?

Insight 1: Precompute the positions of each number in `nums2` to make it easier to check the second condition (increasing order in `nums2`). Insight 2: The core idea is to iterate through all possible 'y' values and efficiently count the number of 'x' values to its left and the number of 'z' values to its right that satisfy the required conditions.

Which companies ask LeetCode 2179. Count Good Triplets in an Array in interviews?

This problem is frequently asked at Walmart Labs.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Count Good Triplets in an Array - LeetCode 2179 Solution

Q: How to solve Count Good Triplets in an Array?

The solution uses a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to efficiently count the number of elements smaller than a given value in a range. First, the positions of each number in `nums2` are stored in an array `pos2`. Then, a new array `A` is created, where `A[i]` stores the position of `nums1[i]` in `nums2`. Now, the problem is reduced to finding triplets (i, j, k) such that i < j < k and A[i] < A[j] < A[k]. The code iterates through the array `A` and for each element `A[j]`, it counts the number of elements `A[i]` to the left of `j` that are less than `A[j]` and the number of elements `A[k]` to the right of `j` that are greater than `A[j]`. The product of these two counts gives the number of good triplets with 'j' as the middle element. The sum of these products over all possible values of 'j' is the total number of good triplets.

Count Good Triplets in an Array - Complete Solution Guide

Count Good Triplets in an Array is LeetCode problem 2179, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 < pos

Detailed Explanation

The problem asks us to find the number of "good triplets" in two arrays, `nums1` and `nums2`, which are permutations of the numbers from 0 to n-1. A good triplet (x, y, z) satisfies two conditions: 1) x, y, and z are distinct values within the range [0, n-1], 2) The indices of x, y, and z are in increasing order in both `nums1` and `nums2`. In other words, if `pos1[v]` is the index of value `v` in `nums1`, and `pos2[v]` is the index of value `v` in `nums2`, then a good triplet (x, y, z) must satisfy `pos1[x] < pos1[y] < pos1[z]` and `pos2[x] < pos2[y] < pos2[z]`.

Solution Approach

The solution uses a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to efficiently count the number of elements smaller than a given value in a range. First, the positions of each number in `nums2` are stored in an array `pos2`. Then, a new array `A` is created, where `A[i]` stores the position of `nums1[i]` in `nums2`. Now, the problem is reduced to finding triplets (i, j, k) such that i < j < k and A[i] < A[j] < A[k]. The code iterates through the array `A` and for each element `A[j]`, it counts the number of elements `A[i]` to the left of `j` that are less than `A[j]` and the number of elements `A[k]` to the right of `j` that are greater than `A[j]`. The product of these two counts gives the number of good triplets with 'j' as the middle element. The sum of these products over all possible values of 'j' is the total number of good triplets.

Step-by-Step Algorithm

Step 1: Create an array `pos2` to store the positions of each element in `nums2`. `pos2[i]` will store the index of the element `i` in `nums2`.
Step 2: Create an array `A` where `A[i] = pos2[nums1[i]]`. This transforms the problem into finding triplets `i < j < k` such that `A[i] < A[j] < A[k]`.
Step 3: Initialize two Binary Indexed Trees (BITs), `left_bit` and `right_bit`. `left_bit` will store the count of elements seen so far from the left, and `right_bit` will store the count of elements to the right.
Step 4: Initially, populate the `right_bit` with all elements from array `A`. This is done because at the start, all elements are to the right of the current middle element we're considering.
Step 5: Iterate through the array `A`. In each iteration (for the current middle element `A[i]`):
Step 6: Remove the element `A[i]` from `right_bit` since it is no longer to the right.
Step 7: Query `left_bit` to find the number of elements to the left of `i` that are less than `A[i]`. This is `less_on_left`.
Step 8: Query `right_bit` to find the number of elements to the right of `i` that are greater than `A[i]`. This is done by subtracting the number of elements less than or equal to `A[i]` from the total number of elements present in `right_bit`.
Step 9: Update the `ans` with `less_on_left * greater_on_right`.
Step 10: Add the element `A[i]` to `left_bit`.
Step 11: After iterating through all elements, return the `ans`.

Key Insights

Insight 1: Precompute the positions of each number in `nums2` to make it easier to check the second condition (increasing order in `nums2`).
Insight 2: The core idea is to iterate through all possible 'y' values and efficiently count the number of 'x' values to its left and the number of 'z' values to its right that satisfy the required conditions.
Insight 3: Use Binary Indexed Trees (BITs) or Fenwick Trees to efficiently count the number of elements less than or greater than a specific value in a given range.

Complexity Analysis

Time Complexity: O(n*log(n))

Space Complexity: O(n)

Topics

This problem involves: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set.

Companies

Asked at: Walmart Labs.

Count Good Triplets in an Array | LeetCode 2179

Hard

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

Time: O(n*log(n))Space: O(n)

Solution Code

Available in:

class Solution {
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] pos2 = new int[n];
        for (int i = 0; i < n; i++) {
            pos2[nums2[i]] = i;
        }

        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = pos2[nums1[i]];
        }

        int[] left_bit = new int[n + 1];
        int[] right_bit = new int[n + 1];

        
        for (int val : A) {
            update(right_bit, val, 1, n);
        }
        
        long ans = 0;
        for (int val : A) {
            update(right_bit, val, -1, n);
            
            long less_on_left = query(left_bit, val - 1);
            
            long total_on_right = query(right_bit, n - 1);
            long less_or_equal_on_right = query(right_bit, val);
            long greater_on_right = total_on_right - less_or_equal_on_right;
            
            ans += less_on_left * greater_on_right;
            
            update(left_bit, val, 1, n);
            
        }
        
        return ans;
    }
    
    private void update(int[] bit_array, int index, int delta, int n) {
        index += 1;
        while (index <= n) {
            bit_array[index] += delta;
            index += index & -index;
        }
    }
    
    private long query(int[] bit_array, int index) {
        if (index < 0) {
            return 0;
        }
        index += 1;
        long s = 0;
        while (index > 0) {
            s += bit_array[index];
            index -= index & -index;
        }
        return s;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2179: Count Good Triplets in an Array - Detailed explanation and solution approaches.

Topics

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

Companies

Walmart Labs

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:2179

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Create an array `pos2` to store the positions of each element in `nums2`. `pos2[i]` will store the index of the element `i` in `nums2`.
2
Step 2: Create an array `A` where `A[i] = pos2[nums1[i]]`. This transforms the problem into finding triplets `i < j < k` such that `A[i] < A[j] < A[k]`.
3
Step 3: Initialize two Binary Indexed Trees (BITs), `left_bit` and `right_bit`. `left_bit` will store the count of elements seen so far from the left, and `right_bit` will store the count of elements to the right.
4
Step 4: Initially, populate the `right_bit` with all elements from array `A`. This is done because at the start, all elements are to the right of the current middle element we're considering.
5
Step 5: Iterate through the array `A`. In each iteration (for the current middle element `A[i]`):
6
Step 6: Remove the element `A[i]` from `right_bit` since it is no longer to the right.
7
Step 7: Query `left_bit` to find the number of elements to the left of `i` that are less than `A[i]`. This is `less_on_left`.
8
Step 8: Query `right_bit` to find the number of elements to the right of `i` that are greater than `A[i]`. This is done by subtracting the number of elements less than or equal to `A[i]` from the total number of elements present in `right_bit`.
9
Step 9: Update the `ans` with `less_on_left * greater_on_right`.
10
Step 10: Add the element `A[i]` to `left_bit`.
11
Step 11: After iterating through all elements, return the `ans`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n*log(n))

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is dominated by the n iterations, each containing log(n) operations from the BIT queries and updates. The space complexity stems from the auxiliary arrays used to store positions and BIT states.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible triplets (x, y, z) and check if they satisfy the good triplet conditions.

Time: O(n^3)Space: O(1)

Trade-offs: Very simple to implement, but extremely inefficient for larger values of 'n'. This is only feasible for very small input sizes due to its cubic time complexity. Should be avoided for constraints where n can be 10^5.

Merge Sort Tree / Segment Tree

Use a merge sort tree or segment tree to count the number of elements less than or greater than a specific value in a range. This is another way to perform the range queries necessary for the problem.

Time: O(n log n)Space: O(n log n)

Trade-offs: Merge sort trees and segment trees provide the same asymptotic time complexity, but often have higher constant factors and more complex implementations compared to BIT. Use only when needing more complex queries that BITs cannot readily support.

✨

Key Insights

1Insight 1: Precompute the positions of each number in `nums2` to make it easier to check the second condition (increasing order in `nums2`).
2Insight 2: The core idea is to iterate through all possible 'y' values and efficiently count the number of 'x' values to its left and the number of 'z' values to its right that satisfy the required conditions.
3Insight 3: Use Binary Indexed Trees (BITs) or Fenwick Trees to efficiently count the number of elements less than or greater than a specific value in a given range.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: When n is small (e.g., n=3). The algorithm will still work correctly because the BIT operations handle small inputs efficiently.
Edge case 2: When the arrays are already sorted (or reverse sorted). The algorithm will still correctly count the good triplets, but it might result in zero good triplets for reverse sorted arrays.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly calculating the `greater_on_right` count. It's important to subtract the count of elements *less than or equal to* A[i] from the total count on the right, not just the count of elements less than A[i].

✗Common mistake 2: Not understanding the BIT data structure and how it enables efficient prefix sum queries and updates. This can lead to attempting to solve the problem using slower methods.

✗Common mistake 3: Integer Overflow. The number of good triplets can be large, so use `long long` (C++, C), or `long` (Java) for variables that store the count of triplets.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing trends in ordered datasets. For example, identifying sequences of stock prices that exhibit a specific increasing trend over time.

🏦Real-world scenario 2: Ranking systems, where you want to find consistent rankings across multiple different ranking criteria. For example, finding products that are consistently highly ranked across different user reviews and expert opinions.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 20, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Can binary search be applied to non-sorted arrays?

Binary search requires a monotonic property, not necessarily sorted data. It can be applied to any search space where you can determine if the answer is in the left or right half. Examples include searching rotated arrays or finding minimum in optimization problems.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Count Good Triplets in an Array"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?