Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each number belongs to the group identified by its decimal digit sum. We need the number of groups tied for greatest size, not that size itself or the number of elements in those groups.

Approach

For every integer from one through n, sum its decimal digits and increment that sum's frequency. Then scan the group sizes. On a new maximum, replace the maximum and reset the number of largest groups to one; on a tie, increment that count. Return the count after all groups are examined. Resetting on improvement discards ties for an earlier, smaller maximum.

class Solution:
    def countLargestGroup(self, n: int) -> int:
        map = defaultdict(int)

        for x in range(1, n + 1):
            txt = str(x)
            sum = 0
            for y in txt:
                sum += int(y)
            map[sum] += 1

        mx = -1
        groups = 0

        for k in map:
            if map[k] > mx:
                mx = map[k]
                groups = 1
            elif map[k] == mx:
                groups += 1

        return groups

Complexity analysis

For every integer through n, the code converts and sums O(log n) digits, giving O(n log n) time. Auxiliary space is O(log n) for the possible digit-sum frequency entries.