2579. Count Total Number of Colored Cells

Difficulty: Medium

Topics: Math

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⁵

Hint:

Derive a mathematical relation between total number of colored cells and the time elapsed in minutes.

Solution:

We need to determine the number of colored cells in an infinitely large two-dimensional grid after n minutes, where each minute colors all uncolored cells adjacent to already colored cells.

Approach

The key observation here is that the number of colored cells follows a specific pattern. Let's analyze the expansion of colored cells over time:

At n = 1, there is 1 colored cell.
At n = 2, the initial cell plus its four immediate neighbors (up, down, left, right) form a 3x3 square, resulting in 5 colored cells.
At n = 3, the colored cells expand further outward, forming a diamond shape with an additional layer of cells around the previous square.

By examining the pattern, we notice that each subsequent minute adds a new layer of cells around the existing colored cells. The number of cells added each minute forms an arithmetic sequence. Specifically, the number of cells added at the k-th minute is 4*(k-1). Summing these values up to n minutes gives the total number of colored cells.

The formula derived from this pattern is:
Total Colored Cells = 2n² - 2n + 1

This formula efficiently computes the result in constant time O(1), making it suitable even for large values of n up to 10⁵.

Let's implement this solution in PHP: 2579. Count Total Number of Colored Cells

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function coloredCells($n) {
    return 2 * $n * $n - 2 * $n + 1;
}

// Example usage
echo coloredCells(1);  // Output: 1
echo coloredCells(2);  // Output: 5
echo coloredCells(3);  // Output: 13
?>

Explanation:

Formula Derivation: The formula 2n² - 2n + 1 is derived by summing the arithmetic sequence of cells added each minute. Each layer adds 4(k-1) cells, where k ranges from 2 to n. Summing these values and adding the initial cell gives the total colored cells.
Efficiency: The solution uses a direct mathematical formula, resulting in a constant time complexity O(1), which is optimal for large input sizes.

This approach ensures that we efficiently compute the result without iterating through each minute, making it both time and space efficient.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub