# Count Total Number of Colored Cells
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-total-number-of-colored-cells)
Canonical: https://scaleengineer.com/dsa/problems/count-total-number-of-colored-cells
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## 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.

![](https://assets.glich.co/dsa/count-total-number-of-colored-cells/image0.png) 

Return _the number of **colored cells** at the end of_ `n` _minutes_.

**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 <= 105`

# Approaches
## Brute-force Simulation
This approach directly simulates the process described in the problem. We maintain a set of coordinates for all colored cells. For each minute, we find all uncolored neighbors of the currently colored cells and add them to the set. The final size of the set is the answer.
**Time:** O(n^3) - At each minute `i` from 2 to `n`, we iterate through O(i^2) existing cells. The total time is the sum of O(i^2) for `i` from 1 to `n-1`, which results in an overall complexity of O(n^3). · **Space:** O(n^2) - The number of colored cells grows quadratically with `n`. We need to store the coordinates of all O(n^2) cells.
**Pros:** Intuitive and easy to understand as it directly models the problem statement.
**Cons:** Extremely inefficient in both time and space.; Will result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error for the given constraints.
### Explanation
We can use a `Set` of objects representing coordinates (e.g., a custom `Point` class with `x` and `y` attributes) to keep track of the colored cells. The `Set` data structure is crucial here to automatically handle duplicate cells and provide efficient lookups (average O(1) time).

The simulation starts with a single cell `(0, 0)` in the set at minute 1. Then, we loop from minute 2 to `n`. In each minute's iteration, we create a temporary set to hold the newly colored cells. We iterate through every cell that is already colored, find its four adjacent neighbors, and if a neighbor isn't in our main set of colored cells, we add it to the temporary set. After checking all existing colored cells, we merge the temporary set into the main set. This process is repeated `n-1` times. The final answer is the total number of unique points in our main set.

```java
// This is a conceptual example that requires a Point class with proper equals() and hashCode() implementations.
// This code is too slow and will not pass the problem constraints.
import java.util.HashSet;
import java.util.Set;
import java.util.Objects;

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x && y == point.y;
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public long coloredCells(int n) {
    if (n == 1) return 1;
    
    Set<Point> colored = new HashSet<>();
    colored.add(new Point(0, 0));
    
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    
    // Loop from minute 2 to n
    for (int i = 2; i <= n; i++) {
        Set<Point> newlyColored = new HashSet<>();
        for (Point p : colored) {
            for (int j = 0; j < 4; j++) {
                Point neighbor = new Point(p.x + dx[j], p.y + dy[j]);
                if (!colored.contains(neighbor)) {
                    newlyColored.add(neighbor);
                }
            }
        }
        colored.addAll(newlyColored);
    }
    
    return colored.size();
}
```
### Algorithm
1. Define a `Point` class or use a similar structure to represent cell coordinates.
2. Initialize a `Set<Point>` called `coloredCells` and add the origin `(0,0)`.
3. Loop for `minute` from 2 to `n`.
4.   Create a temporary `Set<Point>` called `newlyColored` to store cells to be colored in the current minute.
5.   For each `point` currently in `coloredCells`:
6.     Check its four neighbors: `(x+1, y)`, `(x-1, y)`, `(x, y+1)`, and `(x, y-1)`.
7.     For each `neighbor`, if it is not already in `coloredCells`, add it to the `newlyColored` set.
8.   Add all points from `newlyColored` to the main `coloredCells` set.
9. After the loops complete, the answer is the final size of `coloredCells`.

## Iterative Calculation using Recurrence Relation
A more efficient approach is to find a pattern in the number of cells added at each step. By observing the growth, we can establish a recurrence relation and calculate the total number of cells iteratively in a single loop.
**Time:** O(n) - The solution involves a single loop that runs from 2 to `n`, performing a constant number of operations in each iteration. · **Space:** O(1) - We only use a few variables to store the running total and the loop counter, regardless of the input size `n`.
**Pros:** Much more efficient than simulation.; Passes the given constraints.; Simple to implement and understand the logic.
**Cons:** While efficient enough to pass, it is not the most optimal O(1) solution.
### Explanation
Let's analyze the number of new cells added at each minute:
- Minute 1: 1 cell is colored. Total = 1.
- Minute 2: 4 new cells are added around the first one. Total = 1 + 4 = 5.
- Minute 3: The shape at minute 2 is a diamond. The new cells are added along its perimeter. The number of new cells is 8. Total = 5 + 8 = 13.
- Minute 4: 12 new cells are added. Total = 13 + 12 = 25.

The number of new cells added at minute `i` (for `i > 1`) is `4 * (i-1)`. This gives us a recurrence relation for the total number of cells `C(n)`:
`C(n) = C(n-1) + 4 * (n-1)` with the base case `C(1) = 1`.

We can implement this by starting with a total of 1 and iterating from `i = 2` to `n`, adding `4 * (i-1)` at each step. It is crucial to use a 64-bit integer type (like `long` in Java) for the total count to prevent overflow, as the result can exceed the capacity of a 32-bit integer for large `n`.

```java
class Solution {
    public long coloredCells(int n) {
        // Start with 1 cell at n=1
        long totalCells = 1;
        
        // For each minute from 2 to n, add 4*(i-1) new cells
        for (int i = 2; i <= n; i++) {
            totalCells += 4L * (i - 1);
        }
        
        return totalCells;
    }
}
```
### Algorithm
1. Handle the base case: if `n` is 1, return 1.
2. Initialize a `long` variable `totalCells` to 1 (for the cell colored at minute 1).
3. Loop with a variable `i` from 2 to `n`.
4. In each iteration, calculate the number of new cells added at minute `i`, which is `4 * (i - 1)`.
5. Add this number to `totalCells`.
6. After the loop completes, return the final `totalCells`.

## O(1) Mathematical Formula
The most optimal approach is to derive a direct mathematical formula for the number of colored cells. By analyzing the pattern of growth or by solving the recurrence relation found in the iterative approach, we can find a closed-form expression that computes the result in constant time.
**Time:** O(1) - The result is computed using a fixed number of arithmetic operations, making it a constant time solution. · **Space:** O(1) - The calculation uses a fixed amount of space for variables, independent of the input `n`.
**Pros:** The most efficient solution with constant time complexity.; Provides an instantaneous result regardless of the size of `n`.
**Cons:** Requires mathematical analysis to derive the formula, which might not be immediately obvious.
### Explanation
The total number of colored cells, `C(n)`, can be seen as an arithmetic series. The number of new cells added at each step `i` (for `i>1`) is `4*(i-1)`. So the total is:
`C(n) = 1 (at minute 1) + 4*1 (at minute 2) + 4*2 (at minute 3) + ... + 4*(n-1) (at minute n)`

We can factor out the 4:
`C(n) = 1 + 4 * (1 + 2 + 3 + ... + (n-1))`

The sum of the first `k` integers is given by the formula `k*(k+1)/2`. Here, `k = n-1`.
Substituting this into our equation:
`C(n) = 1 + 4 * ((n-1) * ((n-1)+1) / 2)`
`C(n) = 1 + 4 * ((n-1) * n / 2)`
`C(n) = 1 + 2 * n * (n-1)`

Expanding this gives an alternative form: `C(n) = 1 + 2n^2 - 2n = 2n^2 - 2n + 1`.

This formula allows us to calculate the result directly from `n` in a single step. To avoid integer overflow when calculating `n*n` (since `n` can be up to 10^5, `n*n` can be 10^10), we must cast `n` to a `long` before the multiplication.

```java
class Solution {
    public long coloredCells(int n) {
        // Cast n to long to avoid integer overflow during multiplication.
        long long_n = n;
        
        // Formula: 1 + 2 * n * (n - 1)
        // or 2*n*n - 2*n + 1
        return 1L + 2L * long_n * (long_n - 1);
    }
}
```
### Algorithm
1. Cast the input integer `n` to a 64-bit floating-point number (e.g., `long` in Java) to prevent potential overflow during intermediate calculations. Let's call it `long_n`.
2. Apply the derived mathematical formula: `1 + 2 * long_n * (long_n - 1)`.
3. Return the computed result.

# Solutions
### Java

```java
class Solution {
public
  long coloredCells(int n) { return 2L * n * (n - 1) + 1; }
}

```

### CPP

```cpp
class Solution {
public:
  long long coloredCells(int n) { return 2LL * n * (n - 1) + 1; }
};

```

### Python

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

```