Abstract / Summary

Count the total number of cells that are colored after performing a series of painting operations on a grid.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (300k+ submissions).

Typical patterns to solve this problem:

• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a single class Solution containing the method coloredCells. The method receives an integer n and returns the count of cells that would be colored according to a specific mathematical pattern. The core of the computation is a closed-form arithmetic expression derived from the sequence of centered square numbers (OEIS A001844). By applying a simple transformation to the input and evaluating a quadratic formula, the method produces the desired result in constant time.

Key Steps

The method can be broken down into three logical steps, each reflected directly in the source code.

Input Adjustment

n -= 1

The first operation decrements the incoming parameter n by one. This shift aligns the input with the indexing used by the underlying mathematical formula, effectively converting a 1-based count into a 0-based index. The adjustment ensures that the subsequent arithmetic correctly maps the original problem statement to the centered square number sequence.

Core Calculation

return 2 * n * (n + 1) + 1

The return statement evaluates the expression 2 * n * (n + 1) + 1. Expanding the multiplication yields 2n² + 2n + 1, which matches the closed-form representation of the centered square numbers. This single line encapsulates the entire combinatorial reasoning behind the pattern of colored cells, eliminating the need for iterative construction or explicit enumeration.

Implicit Return

The method concludes with the computed integer value, which is directly returned to the caller. No additional processing, validation, or data structures are introduced after the arithmetic operation.

Edge Cases Handled

Because the algorithm relies solely on arithmetic, it gracefully accommodates the full range of integer inputs that Python’s arbitrary-precision integers can represent.

When n is zero, the decrement step yields -1. Substituting -1 into the formula results in 2 * (-1) * 0 + 1, which evaluates to 1. Thus the method returns a sensible value for the smallest non-positive input, preserving the mathematical definition of the sequence at that point.

For n equal to one, the decrement produces 0, and the formula simplifies to 1. This matches the expected base case of the centered square number series, confirming correct handling of the minimal positive input.

Larger positive values of n are processed without overflow concerns because Python automatically expands integer storage as needed, ensuring that the calculation remains accurate regardless of magnitude.

Performance Optimizations

The implementation is inherently optimized for speed and memory usage. By reducing the problem to a single arithmetic expression, the method avoids any form of looping, recursion, or auxiliary data structures. This constant-time approach eliminates overhead associated with iterative constructs and minimizes function call stack depth.

All operations are performed using native integer arithmetic, which is highly optimized in the Python runtime. The absence of temporary collections or intermediate objects means that the memory footprint stays at a minimal, fixed size throughout execution.

Because the calculation is deterministic and side-effect free, the Python interpreter can potentially apply further low-level optimizations such as constant folding when the method is invoked with literal arguments, further enhancing runtime efficiency.

Imagine a game where tiles are placed on a floor. You start with one single tile in the middle. Then, more tiles are added around it in layers to make a bigger and bigger diamond shape. If you decide how many layers of new tiles to add, the code figures out exactly how many tiles are on the floor.

The number n represents how many total layers there are. First, the code takes one away because the very first tile is already there by itself. Then, it uses a special pattern to count the rest of the tiles in the outer layers. By multiplying the numbers together in this specific way, the code calculates the total amount of tiles without needing to count every single one by hand. It is like having a magic formula that finishes the count instantly as soon as the number of layers is known.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java			C++		Python		TS
	WalkCCC	Java			C++		Python
	leetcode.ca	Java			C++	Go	Python	Rust	TS
	Progiez	Java			C++		Python
github	charles-wangkai	Java
	fsq				C++
	JoshCrozier		JS
	Shamik07			Dart
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
Shamik07	Dart
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality