923. 3Sum With Multiplicity

https://leetcode.com/problems/3sum-with-multiplicity/

Python

Three Pointer

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        MOD = 10**9 + 7
        arr.sort()
        counter = 0

        for l in range(len(arr)-2):
            remains = target - arr[l]
            m = l + 1
            r = len(arr) - 1

            while m < r:
                if arr[m] + arr[r] < remains:
                    m += 1
                elif arr[m] + arr[r] > remains:
                    r -= 1
                else:
                    if arr[m] != arr[r]:
                        # Move over all of the same numbers from m
                        left_count = 1
                        while m + 1 < r and arr[m] == arr[m+1]:
                            left_count += 1
                            m += 1

                        # Move over all of the same number from r
                        right_count = 1
                        while r - 1 > m and arr[r] == arr[r-1]:
                            right_count += 1
                            r -= 1

                        # Possible numbers btw m and r are left_count * right_count
                        counter += left_count * right_count
                        counter %= MOD
                        m += 1
                        r -= 1
                    else:
                        # All number btw m and r are the same
                        counter += (r-m+1) * (r-m) // 2
                        counter %= MOD
                        break

        return counter