Intervals Between Identical Elements LeetCode solution in Python

1
# helper data structure Scout
2
class Scout:
3

4
    def __init__(self, prev_idx=-1, count_of_equal=0):
5

6
        # record of index of last identical element
7
        self.prev_idx = prev_idx
8

9
        # count of identical elements so far
10
        self.count_of_equal = count_of_equal
11

12
    def __iter__(self):
13
        # ouput previous index, and count of equal in order
14
        return iter((self.prev_idx, self.count_of_equal))
15

16

17
class Solution:
18
    def getDistances(self, arr: List[int]) -> List[int]:
19

20
        size = len(arr)
21

22
        pre_scout = defaultdict(Scout)
23
        pre_dist_sum = [0 for _ in range(size)]
24

25
        post_scout = defaultdict(Scout)
26
        post_dist_sum = [0 for _ in range(size)]
27

28
        ## Step_1:
29
        # update for pre_dist_sum table, direction is from left to right
30
        for i, element in enumerate(arr):
31

32
            prev_equal_idx, prev_count_of_equal = pre_scout[element]
33

34
            # update pre_dist_sum table if we have identical elements before index i
35
            if prev_count_of_equal:
36
                pre_dist_sum[i] += (
37
                    pre_dist_sum[prev_equal_idx]
38
                    + (i - prev_equal_idx) * prev_count_of_equal
39
                )
40

41
            # update Scout information for current element
42
            pre_scout[element] = i, prev_count_of_equal + 1
43

44
        # --------------------------------------------------------------
45

46
        ## Step_2:
47
        # update for pos_dist_sum table, direction is from right to left
48
        for i, element in reversed([*enumerate(arr)]):
49

50
            post_equal_idx, post_count_of_equal = post_scout[element]
51

52
            # update post_dist_sum table if we have identical elements after index i
53
            if post_count_of_equal:
54
                post_dist_sum[i] += (
55
                    post_dist_sum[post_equal_idx]
56
                    + (post_equal_idx - i) * post_count_of_equal
57
                )
58

59
            # update Scout information for current element
60
            post_scout[element] = i, post_count_of_equal + 1
61

62
        ## Step_3:
63
        # Generate final output by definition
64
        return [pre_dist_sum[i] + post_dist_sum[i] for i in range(size)]