Problem Statement in English

You’re given a 0-indexed binary string array bank representing a bank where bank[i] is a string consisting of '0's and '1's. '0' represents an empty cell, while '1' represents a security device. The security devices are connected by laser beams. A laser beam is formed between any two security devices located in different rows r1 and r2 if both conditions are met:

  1. The security devices are located in different rows.
  2. There is no security device on a row that lies between the two security device rows.

Your task is to return the total number of laser beams in the bank.

Approach

This is just implementation and multiplication.

Solution in Python


class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        res = 0
        prevRow = 0

        for i in range(len(bank)):
            thisRow = 0
            for j in range(len(bank[0])):
                if bank[i][j] == "1":
                    thisRow += 1
            
            res += prevRow * thisRow
            if thisRow:
                prevRow = thisRow

        return res

Complexity

  • Time: $O(n \cdot m)$, where $n$ is the number of rows and $m$ is the number of columns in the bank.

  • Space: $O(1)$, as we are using a constant amount of space for variables.

And we are done.