aboutsummaryrefslogtreecommitdiff
path: root/count_good_triplet_arr.py
blob: ec42ec0e7241019179d994b806d443c1e1f412c0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 2179. Count Good Triplets in an Array
import bisect

"""
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
three distinct values which are present in increasing order by position in
both 'nums1' and 'nums2'. in other words, if we consider 'pos1v' as the index
of the value 'v' in 'nums1' and 'pos2v' as the index of the value 'v' in
'nums2', then a good triplet will be a set '(x, y, z)'. return the total
number of good triplets.
"""


class Solution(object):
    def goodTriplets(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        arr, n = {}, len(nums1)
        for i, j in enumerate(nums1):
            arr[j] = i
        ans, stk = 0, []
        for i in nums2:
            idx = arr[i]
            left = bisect.bisect_left(stk, idx)
            right = (n - 1 - idx) - (len(stk) - left)
            ans += left * right
            bisect.insort(stk, idx)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.goodTriplets(nums1=[2, 0, 1, 3], nums2=[0, 1, 2, 3]))
    print(obj.goodTriplets(nums1=[4, 0, 1, 3, 2], nums2=[4, 1, 0, 2, 3]))