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 <= 105This 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.
The function coloredCells calculates the total number of colored cells after n minutes using a loop. It accumulates the newly colored cells added each minute in a variable total.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1)
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.
This solution in C computes the number of colored cells directly using the derived mathematical formula, optimizing calculation time by eliminating iteration.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1), Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Geometric Progression Approach | Time Complexity: O(n), Space Complexity: O(1) |
| Mathematical Formula Approach | Time Complexity: O(1), Space Complexity: O(1) |
Count Total Number of Colored Cells - Leetcode 2579 - Python • NeetCodeIO • 6,220 views views
Watch 9 more video solutions →Practice Count Total Number of Colored Cells with our built-in code editor and test cases.
Practice on FleetCode