Problem 2125

Question statement:

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. $\texttt{bank[i]}$ represents the $\texttt{i}-$th row, consisting of ‘0’s and ‘1’s. ‘0’ means the cell is empty, while ‘1’ means the cell has a security device. Return the total number of laser beams in the bank, given that: There is one laser beam between any two security devices if both conditions are met.

• The two devices are located on two different rows: $r_1$ and $r_2$, where $r_1 < r_2$.
• For each row $i$ where $r_1 < i < r_2$, there are no security devices in the $i-$th row.
• Laser beams are independent, i.e., one beam does not interfere nor join with another.

Solution

Main idea:

Item 2 is basically a red-herring (or a non-issue). Any row without a laser device can essentially be ignored, and the constraints can be updated to saying “each row contains at least one device and lasers only exist between devices placed in consecutive rows”. Now, this reduces to a counting problem. If row $\texttt{r}$ has $n_r$ devices and row $\texttt{r+1}$ has $n_{r+1}$ devices, then the total number of lasers between the two rows is $n_r\times n_{r+1}$. Thus the total number of lasers is precisely
$$\texttt{res} = \sum_{r>0} n_{r} n_{r-1}$$

Code:

def numberOfBeams(self, bank: List[str]) -> int:
    res = 0
    prev = 0
    for i in bank:
        cur = i.count('1')
        if(cur == 0):
            continue
        res += prev*cur
        prev = cur
    return res

Comments:

Time complexity: O($\texttt{len(bank)}$)

At the time of submission, the above solution passes leetcode submission cases in 89ms, beats 87.59% of users. It uses 12.2MB of memory, beating 20.41% of users.