Problem

There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer n, indicating that you must do the following routine for n minutes:

  • At the first minute, color any arbitrary unit cell blue.
  • Every minute thereafter, color blue every uncolored cell that touches a blue cell.

Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.

Return _the number ofcolored cells at the end of _n minutes.

Examples

Example 1:

Input: n = 1
Output: 1
Explanation: After 1 minute, there is only 1 blue cell, so we return 1.

Example 2:

Input: n = 2
Output: 5
Explanation: After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5.

Constraints:

  • 1 <= n <= 10^5

Solution

Method 1 - Maths

The task is to determine the number of coloured cells in a two-dimensional grid after n minutes. The grid expands in all four directions each minute since every blue cell “spreads” to its uncoloured neighbours.

  • The process starts at one arbitrary cell (minute 1).
  • For subsequent minutes, each blue cell adds its neighbouring cells to the coloured set.

By observing the growth pattern geometrically:

  • At minute 1, there is 1 cell coloured.
  • At minute 2, the 1 cell coloured from minute 1 expands, resulting in a total of 5 cells (1 original + 4 new cells).
  • At minute 3, the previously coloured cells and their adjacent cells combine, resulting in 13 cells, and so on.

The key is to observe the pattern of total coloured cells:

  • At minute 1 → 1.
  • At minute 2 → 5 (1 + 4).
  • At minute 3 → 13 (5 + 8).
  • At minute 4 → 25 (13 + 12).

This forms an arithmetic pattern where for each minute i, the increment is 4 × (i - 1). Using this, we derive a formula for the total number of coloured cells after n minutes:

Formula

Total coloured cells at minute n: 1 + 4 * (1 + 2 + ... + (n-1)), which can be simplified to: 1 + 2 * (n * (n - 1))

Approach

Utilize the mathematical calculation: $$ ans = 1 + 2 * (n * (n - 1)) $$

Code

Java
class Solution {
    public long coloredCells(int n) {
        return 1L + 2L * n * (n - 1);
    }
}
Python
class Solution:
    def colored_cells(self, n: int) -> int:
        return 1 + 2 * n * (n - 1)

Complexity

  • ⏰ Time complexity: O(1) as it’s constant-time arithmetic calculation.
  • 🧺 Space complexity: O(1), since no additional data structures are used.