Number of Laser Beams in a Bank

How it works

Laser beams only form between adjacent rows that contain at least one security device. If one row has a devices and the next non-empty row has b devices, they form a * b beams. We track the count from the previous non-empty row and multiply it by the current row's count whenever we encounter a new row with devices.

Steps

1. Initialize prev with the count of '1's in the first row and res to zero.
2. For each subsequent row, count the number of '1's (curr).
3. If curr > 0, add prev * curr to res and update prev = curr.
4. Return res.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(1) extra space.

Where m is the number of rows and n is the number of columns.

Things to watch for

Counting Empty Rows in Beam Calculations

Rows with zero security devices should be skipped entirely. A common mistake is to update prev = 0 when encountering an empty row, which resets the chain and causes incorrect beam counts. Only update prev when curr > 0.

Multiplying Beams Between Non-Adjacent Rows

The problem states beams form between adjacent rows containing devices. This means if rows 0 and 2 have devices but row 1 is empty, beams still form between rows 0 and 2. The key insight is that "adjacent" refers to consecutive non-empty rows, not consecutive row indices.

Off-by-One Errors with Row Iteration

When iterating from row 1 to the end, ensure prev is initialized correctly from row 0. Starting the loop at index 0 and trying to access bank[-1] or similar patterns will cause index errors or incorrect initialization.

from typing import List

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        prev = bank[0].count("1")
        res = 0

        for i in range(1, len(bank)):
            curr = bank[i].count("1")
            if curr:
                res += prev * curr
                prev = curr

        return res

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int prev = countOnes(bank[0]);
        int res = 0;

        for (int i = 1; i < bank.size(); i++) {
            int curr = countOnes(bank[i]);
            if (curr > 0) {
                res += prev * curr;
                prev = curr;
            }
        }

        return res;
    }

private:
    int countOnes(const string& s) {
        return count(s.begin(), s.end(), '1');
    }
};