Scale Engineer

Count Total Number of Colored Cells

Med
#2359Time: 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`.
Patterns
Math

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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

  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.

Walkthrough

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

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`.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem