LC-2121 Medium LeetCode

2121. Intervals Between Identical Elements

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 45% Topics: Array, Hash Table, Prefix Sum

Reading material

Arrays & Hashing 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


class Solution(object):
    def getDistances(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        lookup = collections.defaultdict(list)
        for i, x in enumerate(arr):
            lookup[x].append(i)
        result = [0]*len(arr)
        for idxs in lookup.itervalues():
            prefix = [0]
            for i in idxs:
                prefix.append(prefix[-1]+i)
            for i, idx in enumerate(idxs):
                result[idx] = (idx*(i+1)-prefix[i+1]) + ((prefix[len(idxs)]-prefix[i])-idx*(len(idxs)-i))
        return result

Solution from kamyu104/LeetCode-Solutions · MIT