'2025/04/15'에 해당되는 글 1건

Leetcode Problem:

• Count Good Triplets in an Array

Summary

• Given two 0-indexed arrays of length n, find the total number of good triplets which are in increasing order in both arrays.

Approach

• The approach used is to create a Fenwick Tree to efficiently calculate prefix sums, then for each value in the first array, calculate the number of good triplets by querying the Fenwick Tree for the number of elements to the left and right, and multiplying these counts together.

Complexity

• O(n log n) due to the Fenwick Tree operations, where n is the length of the input arrays.

Solution Code:

class FenwickTree {
private:
    vector tree;

public:
    FenwickTree(int size) : tree(size + 1, 0) {}

    void update(int index, int delta) {
        index++;
        while (index < tree.size()) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    int query(int index) {
        index++;
        int res = 0;
        while (index > 0) {
            res += tree[index];
            index -= index & -index;
        }
        return res;
    }
};

class Solution {
public:
    long long goodTriplets(vector& nums1, vector& nums2) {
        int n = nums1.size();
        vector pos2(n), reversedIndexMapping(n);
        for (int i = 0; i < n; i++) {
            pos2[nums2[i]] = i;
        }
        for (int i = 0; i < n; i++) {
            reversedIndexMapping[pos2[nums1[i]]] = i;
        }
        FenwickTree tree(n);
        long long res = 0;
        for (int value = 0; value < n; value++) {
            int pos = reversedIndexMapping[value];
            int left = tree.query(pos);
            tree.update(pos, 1);
            int right = (n - 1 - pos) - (value - left);
            res += (long long)left * right;
        }
        return res;
    }
};