Count Total Number of Colored Cells solution and explanation
Google
9 more videos on this problem
Count Total Number of Colored Cells - Leetcode 2579 - PythonNeetCodeIO · 11:53 · 6K views
Count Total Number of Colored Cells | Leetcode 2579Techdose · 8:44 · 2K views
2579. Count Total Number of Colored Cells | leetcode daily challenge | faang | shashcodeShashCode · 11:00 · 1K views
Count Total Number of Colored Cells || Pattern Recognition || Leetcode-2579Aryan Mittal · 4:41 · 1K views
Daily Leetcode #1800: Mar 05, 2025 - 2579. Count Total Number of Colored CellsProgramming Live with Larry · 19:30 · 565 views
2579. Count Total Number of Colored Cells - JAVA (Biweekly Contest 99)Sourin Majumdar · 5:48 · 300 views
Leetcode 2579: Count total number of Colored CellC-mmon · 4:14 · 299 views
2579. Count Total Number of Colored Cells (Leetcode Medium)Programming Live with Larry · 9:23 · 188 views
LeetCode 2579 - Count Total Number of Colored Cells - PythonAlpha-Code · 11:18 · 187 views
leetcode 2579 Count Total Number of Colored Cells | Elementary MathCode-Yao · 8:43 · 110 views
The problem
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
Approach overview
Problem 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 1: Geometric Progression Approach
This approach utilizes the fact that as the minutes pass, the cells form a pattern around the initial blue cell. Each minute, a new layer of cells is added around the existing structure, forming a diamond shape. The nth diamond layer will add 4*(n-1) cells, considering four new cells around each previous edge cell and a single central cell for the initial step.
def colored_cells(n):
if n == 1:
return 1
total = 1
for i in range(2, n + 1):
total += 4 * (i - 1)
return total
n = 2
print(colored_cells(n))public class ColoredCells {
public static long coloredCells(int n) {
if (n == 1) return 1;
long total = 1;
for (int i = 2; i <= n; i++) {
total += 4 * (i - 1);
}
return total;
}
public static void main(String[] args) {
int n = 2;
System.out.println(coloredCells(n));
}
}#include <iostream>
using namespace std;
long long coloredCells(int n) {
if (n == 1) return 1;
long long total = 1;
for (int i = 2; i <= n; i++) {
total += 4 * (i - 1);
}
return total;
}
int main() {
int n = 2;
cout << coloredCells(n) << endl;
return 0;
}function coloredCells(n) {
if (n === 1) return 1;
let total = 1;
for (let i = 2; i <= n; i++) {
total += 4 * (i - 1);
}
return total;
}
const n = 2;
console.log(coloredCells(n));#include <stdio.h>
long long coloredCells(int n) {
if (n == 1) return 1;
long long total = 1;
for (int i = 2; i <= n; i++) {
total += 4 * (i - 1);
}
return total;
}
int main() {
int n = 2;
printf("%lld\n", coloredCells(n));
return 0;
}using System;
public class ColoredCells {
public static long ColoredCellsCalc(int n) {
if (n == 1) return 1;
long total = 1;
for (int i = 2; i <= n; i++) {
total += 4 * (i - 1);
}
return total;
}
public static void Main() {
int n = 2;
Console.WriteLine(ColoredCellsCalc(n));
}
}This Python code calculates the total colored cells by iteratively adding the number of newly colored cells each minute.
Time Complexity: O(n), Space Complexity: O(1)
Approach 2: Mathematical Formula Approach
This approach leverages a derived formula to directly calculate the total count of colored cells at any given minute n. The formula is derived from the observation of the expanding diamond pattern around the initial cell. Specifically, the total number of colored cells at minute n can be expressed as (2n^2 - 2n + 1), eliminating the need for iteration.
def colored_cells(n):
return 2 * n * n - 2 * n + 1
n = 2
print(colored_cells(n))public class ColoredCells {
public static long coloredCells(int n) {
return 2L * n * n - 2 * n + 1;
}
public static void main(String[] args) {
int n = 2;
System.out.println(coloredCells(n));
}
}#include <iostream>
using namespace std;
long long coloredCells(int n) {
return 2LL * n * n - 2 * n + 1;
}
int main() {
int n = 2;
cout << coloredCells(n) << endl;
return 0;
}function coloredCells(n) {
return 2 * n * n - 2 * n + 1;
}
const n = 2;
console.log(coloredCells(n));#include <stdio.h>
long long coloredCells(int n) {
return 2LL * n * n - 2 * n + 1;
}
int main() {
int n = 2;
printf("%lld\n", coloredCells(n));
return 0;
}using System;
public class ColoredCells {
public static long ColoredCellsCalc(int n) {
return 2L * n * n - 2 * n + 1;
}
public static void Main() {
int n = 2;
Console.WriteLine(ColoredCellsCalc(n));
}
}The Python solution uses arithmetic operations to compute the colored cells in constant time, leveraging the derived formula.
Time Complexity: O(1), Space Complexity: O(1)
Approach 3: Mathematics
We find that after the nth minute, there are a total of 2 times n - 1 columns in the grid, and the numbers on each column are respectively 1, 3, 5, cdots, 2 times n - 1, 2 times n - 3, cdots, 3, 1. The left and right parts are both arithmetic progressions, and the sum can be obtained by 2 times n times (n - 1) + 1.
The time complexity is O(1), and the space complexity is O(1).
function coloredCells(n: number): number {
return 2 * n * (n - 1) + 1;
}func coloredCells(n int) int64 {
return int64(2*n*(n-1) + 1)
}impl Solution {
pub fn colored_cells(n: i32) -> i64 {
2 * (n as i64) * ((n as i64) - 1) + 1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Geometric Progression Approach | Time Complexity: O(n), Space Complexity: O(1) |
| Mathematical Formula Approach | Time Complexity: O(1), Space Complexity: O(1) |
| Mathematics | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Total Number of Colored Cells easy or hard?
The problem is rated Medium on LeetCode but conceptually closer to an easy math insight. Once you observe the expansion pattern of the diamond grid, deriving the formula becomes straightforward and leads to a constant-time solution.
Count Total Number of Colored Cells Python/Java solution
The Python or Java implementation typically uses the formula 1 + 2*n*(n-1). This calculates the total colored cells directly in constant time. The code is only a single arithmetic expression and works efficiently even for large values of n.
How to solve Count Total Number of Colored Cells in O(1)?
Recognize that each step adds 4(i-1) new cells, forming a sequence. Summing these additions leads to the closed form 1 + 2n(n-1). Implementing this formula requires only basic arithmetic operations, giving an O(1) time and O(1) space solution.
What is the best approach for Count Total Number of Colored Cells?
The mathematical formula approach is the best solution. The total number of colored cells after n steps follows the pattern 1 + 2n(n-1), which can also be written as n^2 + (n-1)^2. This computes the result in O(1) time and O(1) space without iterating through expansions.
Is Count Total Number of Colored Cells asked at Google/Amazon/Meta?
This problem reflects the type of mathematical pattern recognition questions asked in interviews at companies like Google, Amazon, and Meta. Variants involving grid expansion, geometric growth, or sequence derivation frequently appear in coding interviews.
What data structure is used in Count Total Number of Colored Cells?
No complex data structure is required. The solution relies purely on mathematical pattern recognition and arithmetic operations. Only a few integer variables are needed to compute the final count.
What is the time complexity of Count Total Number of Colored Cells?
Two common solutions exist. The iterative pattern approach runs in O(n) time because it sums the cells added at each expansion step. The optimal mathematical formula computes the result directly in O(1) time with constant space.