[Leetcode] 2179. Count Good Triplets in an Array (i dont get)

https://leetcode.com/problems/count-good-triplets-in-an-array/description/?envType=daily-question&envId=2025-04-15

initial

very obv n^3 method but there is tle
Then I tried googling and saw n^2 sol with considering just the middle idx and iterating through middle idx. Like

from collections import defaultdict
class Solution:
    def goodTriplets(self, nums1, nums2) -> int:
        dic1= defaultdict(int)
        dic2= defaultdict(int)
        ans=0
        for i, (v1,v2) in enumerate(zip(nums1,nums2)):
            dic1[v1]=i
            dic2[v2]=i
        length = len(nums1)
        for mid1 in range(1,length-1):
            val1=nums1[mid1]
            mid2=dic2[val1]
            small,big=0,0
            for j in range(mid1):
                left=nums1[j]
                if mid2>dic2[left]:
                    small+=1
            for k in range(mid1+1,length):
                right=nums1[k]
                if dic2[right]>mid2:
                    big+=1
            ans+=small*big
        return ans     

sol

But to solve this, u need to solve in n log n time. With bisect left, here is sol.

but this is sitll n^2 cuz insert is n. I dk why this dosnt cause tle maybe the binary search helps optimise

class Solution:
    def goodTriplets(self, nums1, nums2) -> int:
        N = len(nums1)
        b_pos = dict(zip(nums2, range(N)))        
        visited_idx = [b_pos[nums1[0]]]        
        res = 0
        for i in range(1, N-1):    # No need to process the first and the last element in A
            common_found = bisect.bisect_left(visited_idx, b_pos[nums1[i]])  
            visited_idx.insert(common_found, b_pos[nums1[i]])
            res += common_found * (N - i - b_pos[nums1[i]] + common_found - 1)
                                    
        return res   

complexity

n log n time