We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Total Number of Colored Cells

Number: 2649

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Bloomberg

Problem Description

You are given a positive integer n that represents the number of minutes to perform a coloring routine on an infinite 2D grid of uncolored unit cells. Initially, you color any one arbitrary cell blue. Every minute thereafter, every uncolored cell that touches (i.e., shares a side with) a blue cell is colored blue. The task is to determine the total number of blue cells after n minutes.

Key Insights

  • The blue region grows outward forming a diamond shape (or a Manhattan circle) centered on the initial cell.
  • At minute n, the farthest distance (in Manhattan distance) from the starting cell that becomes blue is n - 1.
  • The total number of cells in a Manhattan circle of radius k is given by the formula 2k² + 2k + 1.
  • By setting k = n - 1, the final count becomes: 2*(n - 1)² + 2*(n - 1) + 1, which can be simplified to 2n(n - 1) + 1.

Space and Time Complexity

Time Complexity: O(1) — The solution uses direct arithmetic operations. Space Complexity: O(1) — Only a constant amount of extra space is used.

Solution

The solution is based on the observation that the colored cells form a diamond pattern where every cell within a Manhattan distance of (n - 1) from the initially colored cell is blue. The count of these cells is calculated using the formula 2n(n - 1) + 1. This formula directly calculates the number of colored cells without the need for iterative or recursive simulation, ensuring an optimal O(1) time complexity.

Code Solutions

# Python implementation with line-by-line comments

def coloredCells(n: int) -> int:
    # The blue region forms a diamond with Manhattan radius (n - 1).
    # The total number of cells in a Manhattan circle of radius k is 2*k^2 + 2*k + 1.
    # For k = n - 1, this becomes: 2*(n-1)^2 + 2*(n-1) + 1 which simplifies to 2*n*(n-1) + 1.
    return 2 * n * (n - 1) + 1

# Example usage:
print(coloredCells(3))  # Expected output: 13
← Back to All Questions