Number of Laser Beams in a Bank

main.md

Question

Approach

I scan the rows and count the number of security devices ('1') in each row. I only care about rows that contain at least one device. For every pair of consecutive non-empty rows (i.e., rows with devices and no device-containing rows between them) each device in the earlier row forms a beam with every device in the later row, so I add prev_count * curr_count to the answer and then update prev_count = curr_count. This gives the total beams in a single pass.

Implementation

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        prev = 0
        ans = 0
        for row in bank:
            cnt = row.count('1')
            if cnt > 0:
                if prev > 0:
                    ans += prev * cnt
                prev = cnt
        return ans

Complexities

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