How can I efficiently count distinct chronological (a, b, b) triplets in a large array using Python?

Do you want to check only for contiguous triplets of the form (a, b, b)? Based on your example, that doesn't seem to be the case. Then, to get the number of triplets, you can just count the number of unique values and repeated values and multiply them.

In the example [5,6,7,3,3,3],

PYTHONCopied
count_of_unique_vals = 3     # 5, 6 and 7
count_of_repeated_vals = 1   # 3
count_of_triplets = 3        # 3*1, or len(unique_vals) * len(repeated_vals)

My idea is to break it down into three tasks:

1. Find the last two occurrences of duplicate values.
2. Check how many unique values exist to the left of those occurrences.
3. Check whether the value found in the 1. is included among those unique values.

And here is a two-pass solution with O(n) memory consumption.
The worst case time complexity is O(n^2), but since it is O(n) x dictionary accesses, it should be quite efficient.

PYTHONCopied
def count_from_right(arr):
    # A mapping that maps each distinct value to its first occurrence index.
    first_occurrence_index_map = {}

    # A mapping where unique_value_counts[i] represents the number of distinct values in arr[:i].
    unique_value_counts = [0]

    for i, value in enumerate(arr):
        if value not in first_occurrence_index_map:
            first_occurrence_index_map[value] = i
        unique_value_counts.append(len(first_occurrence_index_map))

    # A mapping where count[k] represents the number of triples of the form (*, k, k).
    ans_counts = {}

    for i in range(len(arr))[::-1]:  # Iterate from right to left.
        if arr[i] not in ans_counts:
            # If this is the last occurrence of arr[i], mark it with 0.
            ans_counts[arr[i]] = 0
        elif ans_counts[arr[i]] == 0:
            # Here, arr[i] is the second-to-last occurrence of this value.
            # The number of possible triplets is the count of unique values in arr[:i], excluding arr[i] itself.
            ans_counts[arr[i]] = unique_value_counts[i] - int(first_occurrence_index_map[arr[i]] < i)

    return sum(ans_counts.values())

At the second-to-last occurrence of each b-value, add the number of different values that came before it. Takes about 1.5 seconds for array length 10^6.

PYTHONCopied
from collections import Counter

def linear(arr):
    ctr = Counter(arr)
    A = set()
    result = 0
    for b in arr:
        if ctr[b] == 2:
            result += len(A) - (b in A)
        ctr[b] -= 1
        A.add(b)
    return result

Testing your small example and five larger arrays:

PYTHONCopied
import random
from time import time

def original(arr):
    n = len(arr)
    ans = set()
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] != arr[j]:
                for k in range(j + 1, n):
                    if arr[j] == arr[k]:
                        ans.add((arr[i], arr[j], arr[k]))
    return len(ans)

def test(arr):
    expect = original(arr)
    result = linear(arr)
    print(result == expect, expect, result)

# Correctness
test([5, 6, 7, 3, 3, 3])
for _ in range(5):
    test(random.choices(range(100), k=100))

# Speed
n = 10**6
arr = random.choices(random.sample(range(10**9), n), k=n)
t = time()
print(linear(arr))
print(time() - t)

Sample output (Attempt This Online!):

PLAINTEXTCopied
True 3 3
True 732 732
True 1038 1038
True 629 629
True 754 754
True 782 782
80414828386
1.4968228340148926