How do I calculate the total number of colored cells in the "Count Total Number of Colored Cells" problem?

The formula to calculate the total number of colored cells after n minutes is total = n^2 + (n-1)^2.

What is the time complexity of the solution for this problem?

The solution has a time complexity of O(1) because the formula can be computed directly without iteration.

What is the relationship between n and the total number of colored cells?

The total number of colored cells grows quadratically as n increases, with the formula total = n^2 + (n-1)^2.

How can I optimize the solution for larger values of n?

The formula provides a constant-time solution, O(1), so no further optimization is needed, even for large values of n.

What are common mistakes to avoid in this problem?

Avoid confusing the problem as a linear growth scenario and ensure you understand the quadratic pattern in the number of colored cells.

#2579

Medium

auto_awesome数学·driven

LeetCode 题解工作台

统计染色格子数

有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：第一分钟，将任一格子染成蓝色。之后的每一分钟，将与蓝色格子相邻的所有未染色格子染成蓝色。下图分别是 1、2、3 分钟后的网格图。请你返回 n 分钟之后被染色的格子数目。示例…

数学

题目描述

有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：

第一分钟，将任一格子染成蓝色。
之后的每一分钟，将与蓝色格子相邻的所有未染色格子染成蓝色。

下图分别是 1、2、3 分钟后的网格图。

请你返回 n 分钟之后 被染色的格子 数目。

示例 1：

输入：n = 1
输出：1
解释：1 分钟后，只有 1 个蓝色的格子，所以返回 1 。

示例 2：

输入：n = 2
输出：5
解释：2 分钟后，有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子，所以返回 5 。

提示：

1 <= n <= 10⁵

lightbulb

解题思路

方法一：数学

我们观察发现，第 $n$ 分钟后，网格中共有 $2 \times n - 1$ 列，每一列上的数字分别为 $1, 3, 5, \cdots, 2 \times n - 1, 2 \times n - 3, \cdots, 3, 1$ 。左右两部分均为等差数列，求和可以得到答案 $2 \times n \times (n - 1) + 1$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def coloredCells(self, n: int) -> int:
        return 2 * n * (n - 1) + 1

speed

复杂度分析

指标	值
时间	O(1)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate should demonstrate an ability to recognize mathematical patterns and derive efficient formulas.
question_mark
Look for clarity in explaining the relation between n and the total colored cells.
question_mark
Check if the candidate is able to explain how constant time complexity is achieved in this solution.

warning

常见陷阱

外企场景

error
Candidates might confuse the total number of colored cells with a simpler linear growth pattern, missing the quadratic nature.
error
Over-complicating the problem by trying to simulate the grid's growth instead of using a direct formula.
error
Failure to recognize that the problem can be solved in constant time may lead to inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to include a constraint on the grid size, limiting the total number of colored cells after n minutes.
arrow_right_alt
Ask the candidate to calculate the total number of colored cells after k minutes given multiple values of n.
arrow_right_alt
Extend the problem to handle multiple grids and calculate the total number of colored cells across several test cases.

help

常见问题

外企场景

继续练习

#2578 最小和分割 #2582 递枕头 #2575 找出字符串的可整除数组