Number of Laser Beams in a Bank

Problem Description

You are given a 0-indexed binary string array bank representing the floor plan of a bank, which is an m x n 2D matrix. Each cell either contains a security device ('1') or is empty ('0'). A laser beam can be established between two security devices located on different rows, provided there are no security devices in the rows between them. Your task is to return the total number of laser beams in the bank.

Key Insights

• A laser beam can only exist between two security devices in different rows.
• The rows between the two devices must be completely empty of security devices.
• The number of beams between two rows is determined by the product of the number of devices in each row.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Solution

To solve this problem, we can iterate through each row of the bank to count the number of security devices ('1's) in each row. We maintain a variable to keep track of the number of devices in the previous row. When we find a row with security devices, if there are devices in the previous row, we calculate the number of beams formed by multiplying the current row's device count with the previous row's device count. We then update the previous row's count and continue to the next row.

Data Structures:

• An integer variable to store the count of devices in the previous row.
• An integer variable to store the total number of beams.

Algorithmic Approach:

1. Initialize previousCount to 0 and totalBeams to 0.
2. Loop through each row in the bank:
   • Count the number of '1's in the current row (currentCount).
   • If currentCount > 0:
     • Multiply previousCount with currentCount and add it to totalBeams.
     • Update previousCount to currentCount.
3. Return totalBeams.

Code Solutions