LeetCode 2579 - Count Total Number of Colored Cells

LeetCode Problem 2579

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

The problem describes a process of coloring cells on an infinite two-dimensional grid over n minutes. At minute 1, we start by coloring exactly one arbitrary cell blue. For every minute after that, every uncolored cell that shares a side with an already blue cell also becomes blue.

In simpler terms, the colored region expands outward one layer at a time. Since only cells that touch existing blue cells by edges are colored, the shape grows symmetrically into a diamond pattern centered around the original cell.

The input is a single positive integer n, which represents how many minutes the coloring process runs. The output should be the total number of colored cells after exactly n minutes.

The constraints are relatively small, 1 <= n <= 10^5, but this is still large enough that simulating every cell minute by minute could become inefficient. Since the grid is theoretically infinite, any brute-force simulation would need careful bookkeeping to avoid excessive memory usage.

The important observation is that the problem guarantees n is always positive, so we never need to handle invalid values such as 0 or negative integers. The smallest case is n = 1, where only the initial cell exists. Larger values of n create increasingly larger diamond-shaped expansions, and naive simulations may become unnecessarily expensive.

Approaches

Brute Force Simulation

A direct way to solve this problem is to simulate the coloring process minute by minute.

We could maintain a set of currently colored cells. Initially, the set contains one cell, such as (0, 0). At every new minute, we inspect all currently colored cells and add any uncolored neighboring cells in the four cardinal directions: up, down, left, and right.

This approach works because it faithfully follows the exact process described in the problem statement. By repeatedly expanding outward from all blue cells, we eventually reach the correct final configuration.

However, this method is inefficient. The number of colored cells grows quadratically with n, meaning the simulation requires storing and processing many coordinates. Since n can be as large as 100000, explicitly tracking billions of cells is completely impractical.

Mathematical Observation

Instead of simulating the process, we can analyze the pattern mathematically.

If we observe the number of cells added each minute:

• Minute 1: 1
• Minute 2: +4
• Minute 3: +8
• Minute 4: +12

We notice a clear pattern. Every new minute adds 4 × (minute - 1) cells.

This happens because the shape expands like a diamond, and each new layer contributes four growing edges.

Therefore, the total number of colored cells becomes:

$$1 + 4(1 + 2 + 3 + ... + (n-1))$$

Using the arithmetic series formula:

$$1 + 4 \cdot \frac{(n-1)n}{2}$$

Simplifying:

$$1 + 2n(n-1)$$

This gives us an O(1) solution that computes the answer directly without simulation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n²)	Simulates every colored cell explicitly
Optimal	O(1)	O(1)	Uses mathematical pattern recognition

Algorithm Walkthrough

1. Start with the observation that at minute 1, exactly 1 cell is colored.
2. Notice that every subsequent minute adds a predictable number of cells. At minute 2, 4 cells are added. At minute 3, 8 cells are added. At minute k, exactly 4 × (k - 1) cells are added.
3. Sum all added cells across the n minutes:

$$1 + 4(1 + 2 + 3 + ... + (n-1))$$ 4. Replace the arithmetic sum using the formula:

$$\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2}$$ 5. Simplify the expression:

$$1 + 4 \cdot \frac{(n-1)n}{2}$$

$$1 + 2n(n-1)$$ 6. Return the computed value directly.

Why it works

The key invariant is that after each minute, the colored cells form a perfectly symmetric diamond. Every expansion layer increases the perimeter uniformly, causing exactly 4 × (minute - 1) new cells to appear. Since this growth pattern is deterministic and forms an arithmetic sequence, summing these additions gives the exact total number of colored cells.

Python Solution

class Solution:
    def coloredCells(self, n: int) -> int:
        return 1 + 2 * n * (n - 1)

The implementation is intentionally simple because the mathematical formula already captures the entire process.

The expression 2 * n * (n - 1) computes the total contribution from all expansion layers beyond the initial cell. The +1 accounts for the original blue cell colored at minute 1.

Python integers automatically support arbitrarily large values, so overflow is not a concern, even though the answer can become fairly large for n = 100000.

Go Solution

func coloredCells(n int) int64 {
	return 1 + int64(2*n*(n-1))
}

The Go implementation follows the same formula as the Python version.

The main difference is integer handling. Since Go's int type can vary depending on platform and the result may become large, the function returns int64 as required by the problem signature. We explicitly cast the computed result to int64 to ensure correctness and avoid overflow concerns.

Worked Examples

Example 1

Input: n = 1

At minute 1, we color only the starting cell.

Minute	Newly Added Cells	Total Colored Cells
1	1	1

Using the formula:

$$1 + 2 \times 1 \times (1 - 1)$$

$$1 + 0 = 1$$

Final answer: 1

Example 2

Input: n = 2

The expansion proceeds as follows:

Minute	Newly Added Cells	Total Colored Cells
1	1	1
2	4	5

Using the formula:

$$1 + 2 \times 2 \times (2 - 1)$$

$$1 + 4 = 5$$

Final answer: 5

Additional Example

Consider n = 3.

Minute	Newly Added Cells	Total Colored Cells
1	1	1
2	4	5
3	8	13

Formula calculation:

$$1 + 2 \times 3 \times (3 - 1)$$

$$1 + 12 = 13$$

Final answer: 13

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a constant number of arithmetic operations are performed
Space	O(1)	No extra memory proportional to input size is used

The solution performs a direct mathematical computation regardless of the input value. There are no loops, recursive calls, or auxiliary data structures, so both time and space usage remain constant.

Test Cases

solution = Solution()

assert solution.coloredCells(1) == 1      # Minimum input
assert solution.coloredCells(2) == 5      # Example from problem
assert solution.coloredCells(3) == 13     # Third expansion layer
assert solution.coloredCells(4) == 25     # Continued arithmetic growth
assert solution.coloredCells(5) == 41     # Larger pattern verification
assert solution.coloredCells(10) == 181   # Mid-sized input
assert solution.coloredCells(100) == 19801  # Larger input check
assert solution.coloredCells(100000) == 19999800001  # Maximum constraint

Test	Why
n = 1	Validates the smallest possible input
n = 2	Confirms the provided example
n = 3	Verifies second expansion layer
n = 4	Ensures arithmetic growth continues correctly
n = 5	Tests multiple iterations of pattern
n = 10	Confirms medium-sized correctness
n = 100	Validates large number handling
n = 100000	Stress test at maximum constraint

Edge Cases

Minimum Input, n = 1

This is the smallest valid input and a common source of off-by-one errors. A flawed implementation might mistakenly assume expansion begins immediately and incorrectly return 5. Our formula correctly handles this because:

$$1 + 2 \times 1 \times (1 - 1) = 1$$

The multiplication by zero naturally prevents any extra cells from being added.

Large Input Near Constraint Limit

When n = 100000, the answer becomes very large:

$$19999800001$$

A brute-force simulation would be infeasible because it would require tracking billions of cells. The mathematical solution handles this efficiently in constant time.

Off-by-One Errors in Pattern Recognition

A common mistake is incorrectly assuming minute k adds 4k cells instead of 4(k-1). This would overcount every layer and produce incorrect results. Our implementation avoids this issue by deriving the formula directly from the observed sequence and arithmetic progression.