LeetCode - The World's Leading Online Programming Learning Platform

Intuition

Using two variables, one for the previous floor with security devices and the other for the current floor with security devices.

Iterate through the bank. The sum of the product of the two variables in each iteration is the answer.

Approach

1. Find the first floor with security devices.
2. Starting from this floor, traverse all floors, and add the product to the answer.

Complexity

• Time complexity: O(N)
• Space complexity: O(1)

Code

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        if len(bank) == 1:
            return 0
        
        start_idx = 0
        prev = 0
        beams = 0
        counts = [f.count("1") for f in bank]

        # Find the first floor with security devices 
        for i, count in enumerate(counts):
            if count > 0:
                prev = count
                start_idx = i
                break

        # Handle edge cases
        if start_idx == len(bank)-1:
            return 0
        
        # Iterate the remaining floors
        for j in range(start_idx + 1, len(bank)):
            # Skip the floow without security devices
            if counts[j] == 0:
                continue
            beams += prev * counts[j]
            prev = counts[j]
        
        return beams