1399.Count_Largest_Group(Easy).md

1399. Count Largest Group (Easy)

Date and Time: Apr 23, 2025

Link: https://leetcode.com/problems/count-largest-group

Walk-through:

Use a dictionary to map each digit_sum to map a list of intergers with the same digit_sum. At the same time, use two variables max_cnt, max_size to keep track of the max length of list after we append the current digit i into its digit_sum.

Python Solution:

class Solution:
    def countLargestGroup(self, n: int) -> int:
        # Q: Return # of largest group size
        # Use dictionary to keep track of each digit_sum's list {digit_sum: [digits]}
        # Variables max_sum, max_cnt to keep track
        # After add the current digit into dictionary
        # Check if digit_sum > max_sum, update max_cnt = 1. Elif digit_sum == max_sum, increment max_cnt

        # TC: O(n), SC: O(n)
        digitsMap = collections.defaultdict(list)
        cnt, max_size = 0, 0
        for i in range(1, n+1):
            # Calculate digit_sum
            digit_sum = 0
            for j in str(i):
                digit_sum += int(j)
            # Add current digit to dictionary and update max_cnt, max_sum
            digitsMap[digit_sum].append(i)
            # Update max_cnt, max_size if we have greater group size
            if len(digitsMap[digit_sum]) > max_size:
                cnt = 1
                max_size = len(digitsMap[digit_sum])
            elif max_size == len(digitsMap[digit_sum]):
                cnt += 1
        return cnt

Time Complexity: $O(n)$
Space Complexity: $O(n)$