Count Total Number of Colored Cells

LeetCode 2579, Medium. Topics: Math. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2579   # by problem number
lcpy gen -s count_total_number_of_colored_cells   # by problem name

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.

Return the number of colored cells at the end of n minutes.

Examples

Input: n = 1
Output: 1
Explanation: After 1 minute, there is only 1 blue cell, so we return 1.

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^5

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(1)
    # Space: O(1)
    def colored_cells(self, n: int) -> int:
        return 2 * n * n - 2 * n + 1

Complexity

Time	Space
O(1)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Count Total Number of Colored Cells

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags