Count Asterisks - Leetcode Solution

Problem Statement: Given a 2D grid of size m x n containing '*' and '.', find the number of asterisks present in the grid considering only the following rules:

• An asterisk at position (i, j) can be part of a plus sign centered at (i, j) if all four arms of the plus sign can expand to the same size.
• An arm of the plus sign is defined as a contiguous sequence of asterisks that are only connected to the central asterisk at (i, j).
• Return the number of asterisks that can be part of any valid plus sign.

Solution: The question asks us to find the number of asterisks that can be part of any valid plus sign. A plus sign can be described as having a central asterisk with four arms that can expand equally in all four directions. Therefore, our approach would be to iterate over each cell of the grid and find the size of the arm in all four directions. If the size is greater than or equal to 2, then we can say that that asterisk can be part of a valid plus sign.

Algorithm:

1. Initialize a variable count with 0 that will represent the number of asterisks that can be part of a valid plus sign.
2. Iterate over the grid and check each cell.
3. If the current cell is an asterisk, then find the size of the arm in all four directions with the help of nested for loops.
4. If the size of any arm is less than or equal to 1, then continue with the next cell. Otherwise, add the minimum size of all arms to the count and go to the next cell.
5. Return the resulting count.

Pseudo Code:

count = 0
for i in range(m):
    for j in range(n):
        if grid[i][j] == '*':
            up, down, left, right = 0, 0, 0, 0
            k = 1
            while i - k >= 0 and grid[i-k][j] == '*':
                up += 1
                k += 1
            k = 1
            while i + k < m and grid[i+k][j] == '*':
                down += 1
                k += 1
            k = 1
            while j - k >= 0 and grid[i][j-k] == '*':
                left += 1
                k += 1
            k = 1
            while j + k < n and grid[i][j+k] == '*':
                right += 1
                k += 1
            if min(up, down, left, right) >= 1:
                count += min(up, down, left, right) + 1
return count

Time Complexity: The time complexity of the solution is O(m * n * L), where L is the maximum size of the arm. In the worst case, L can be equal to min(m, n), but in practice, it is much smaller. Therefore, the time complexity of the solution is O(m * n).

Space Complexity: The space complexity of the solution is O(1) as we are not using any extra space other than the given grid.

Summary: In this problem, we have learned how to find the number of asterisks that can be part of any valid plus sign in a 2D grid using basic iteration and checking each cell. The solution has a time complexity of O(m * n) and a space complexity of O(1).

1