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.

Video Solution

Watch the video walkthrough for Count Total Number of Colored Cells

Patterns:

Math