Number of Laser Beams in a Bank

Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the i<sup>th</sup> row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.

There is one laser beam between any two security devices if both conditions are met:

• The two devices are located on two different rows: r1 and r2, where r1 < r2.
• For each row i where r1 < i < r2, there are no security devices in the i<sup>th</sup> row.

Laser beams are independent, i.e., one beam does not interfere nor join with another.

Return the total number of laser beams in the bank.

Example 1:

bank = ["011001","000000","010100","001000"]

Output: 8

Example 2:

bank = ["000","111","000"]

Output: 0

Can you write a function to solve this?

def numberOfBeams(bank):
    rows = len(bank)
    beams = 0
    previous_devices = 0
    
    for i in range(rows):
        devices = bank[i].count('1')
        if devices > 0:
            beams += previous_devices * devices
            previous_devices = devices
            
    return beams

Naive Solution

The naive solution would involve iterating through all possible pairs of rows and checking if the condition for forming a laser beam is met. This would involve checking every row between the two selected rows to ensure no security devices are present. This approach has a higher time complexity.

Optimal Solution

The optimal solution iterates through the rows of the bank, counts the number of security devices in each row, and skips empty rows. It maintains a variable to store the number of security devices in the previous non-empty row. The total number of laser beams is calculated by multiplying the number of devices in the current non-empty row with the number of devices in the previous non-empty row. This approach avoids unnecessary checks and calculations, resulting in a more efficient solution.

Big(O) Run-Time Analysis

The time complexity of the provided solution is O(m * n), where m is the number of rows and n is the number of columns in the bank. This is because, in the worst-case scenario, the algorithm iterates through each cell of the bank to count the number of security devices in each row.

Big(O) Space Usage Analysis

The space complexity of the provided solution is O(1), which means it uses a constant amount of extra space. This is because the algorithm only uses a few variables to store the number of rows, total beams, and the number of devices in the previous row. The space usage does not depend on the size of the input.

Edge Cases

1. Empty Bank: If the input bank is empty (i.e., no rows), the function should return 0 since no laser beams can be formed.
2. No Security Devices: If there are no security devices in the bank (all cells are '0'), the function should return 0 since no laser beams can be formed.
3. Single Row: If the bank has only one row, no laser beams can be formed between different rows. The function should return 0.
4. Consecutive Rows with Devices: If there are consecutive rows with security devices, the laser beams can be formed between those rows as long as there are no devices in between them.
5. Large Bank: The solution should handle large banks efficiently without exceeding the available memory or execution time. The time and space complexity should be optimized to accommodate large input sizes.