Leetcode Problem 2179. Count Good Triplets in an Array

2179. Count Good Triplets in an Array

Leetcode Solutions

Using Fenwick Tree (Binary Indexed Tree) for Counting Good Triplets

  1. Create a dictionary to map each element in nums1 to its index.
  2. Re-index nums2 based on the mapping from nums1.
  3. Initialize a Fenwick Tree to keep track of the count of elements.
  4. Iterate through the re-indexed nums2 array. a. For each element, use the Fenwick Tree to find the count of elements smaller than the current element that have appeared so far. b. Update the Fenwick Tree with the current element. c. Use the count from step 4a to calculate the number of good triplets centered at the current element.
  5. Sum up the counts from step 4c to get the total number of good triplets.
UML Thumbnail

Brute Force Approach with Optimization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...