Problem Description
Given a positive integer n, you need to color unit cells in an infinitely large two-dimensional grid according to the following rules for n minutes: At the first minute, color any arbitrary unit cell blue. Every subsequent minute, color every uncolored cell that touches a blue cell. Return the total number of colored cells after n minutes.
Key Insights
- The first minute colors one cell.
- Each subsequent minute colors additional cells that are adjacent to previously colored cells.
- The pattern of coloring expands outward in a diamond shape, effectively leading to a formula for the total number of colored cells based on n.
Space and Time Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Solution
The problem can be solved using a mathematical approach. For any given minute n, the total number of colored cells can be calculated using the formula:
- Total colored cells = n * (n + 1) + (n - 1) * n This formula derives from the fact that each minute, the number of new cells added is proportional to the perimeter of the already colored area.