Count Total Number of Colored Cells

MEDIUM

Description

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 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 <= 10⁵

Approaches

Checkout 3 different approaches to solve Count Total Number of Colored Cells. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Handle the base case: if n is 1, return 1.
Initialize a long variable totalCells to 1 (for the cell colored at minute 1).
Loop with a variable i from 2 to n.
In each iteration, calculate the number of new cells added at minute i, which is 4 * (i - 1).
Add this number to totalCells.
After the loop completes, return the final totalCells.

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.

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;
    }
}

Complexity Analysis

Time Complexity: O(n) - The solution involves a single loop that runs from 2 to `n`, performing a constant number of operations in each iteration.Space Complexity: O(1) - We only use a few variables to store the running total and the loop counter, regardless of the input size `n`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Total Number of Colored Cells. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Count Total Number of Colored Cells

Patterns:

Math