aboutsummaryrefslogtreecommitdiff
path: root/count_good_triplet_arr.py
diff options
context:
space:
mode:
Diffstat (limited to 'count_good_triplet_arr.py')
-rw-r--r--count_good_triplet_arr.py38
1 files changed, 38 insertions, 0 deletions
diff --git a/count_good_triplet_arr.py b/count_good_triplet_arr.py
new file mode 100644
index 0000000..ec42ec0
--- /dev/null
+++ b/count_good_triplet_arr.py
@@ -0,0 +1,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]))