Watch 10 video solutions for Count Total Number of Colored Cells, a medium level problem involving Math. This walkthrough by NeetCodeIO has 6,590 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 105Problem Overview: You start with one colored cell. Each minute, the colored region expands in four directions, forming a diamond pattern. Given n, compute the total number of colored cells after n expansions.
Approach 1: Geometric Growth Pattern (O(n) time, O(1) space)
The grid grows outward layer by layer. At minute 1, there is only one cell. Every additional minute adds a ring around the diamond. The number of new cells added at step i is 4 * (i - 1). You iterate from 2 to n, accumulating these additions into the total. This effectively sums the expansion of the diamond perimeter at each step. The method works well when you want to visualize or simulate the pattern growth and is easy to derive during interviews by writing out the first few values: 1, 5, 13, 25....
The insight comes from observing that each new layer contributes four directional arms extending from the previous boundary. Using a simple loop, you keep adding the incremental increase until reaching n. Time complexity is O(n) because you iterate once through the expansion steps, and space complexity remains O(1) since only a few variables track the running total.
Approach 2: Mathematical Formula (O(1) time, O(1) space)
The pattern from the iterative approach forms a clear mathematical sequence. Expanding the recurrence shows the total colored cells equal 1 + 4(1 + 2 + ... + (n-1)). The sum of the first k integers is k(k+1)/2, which simplifies the expression to 1 + 2n(n-1). Another equivalent form is n^2 + (n-1)^2. Both represent the number of cells inside the diamond formed after n steps.
This removes iteration entirely. You compute the value directly using constant-time arithmetic operations. Time complexity becomes O(1) and space complexity remains O(1). Problems like this often appear under Math pattern recognition where deriving the closed-form expression is the key optimization.
Recommended for interviews: Start by explaining the layer expansion pattern using the iterative reasoning. That demonstrates understanding of the grid geometry. Then derive the closed-form formula 1 + 2n(n-1) to reach the optimal O(1) solution. Interviewers typically expect the mathematical insight because it shows strong pattern recognition and familiarity with sequence summation in math and geometry-style grid problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Geometric Growth Pattern (Iterative) | O(n) | O(1) | When deriving the pattern step‑by‑step or explaining the grid expansion visually |
| Mathematical Formula | O(1) | O(1) | Best for production and interviews once the sequence pattern is recognized |