Watch 10 video solutions for Number of Laser Beams in a Bank, a medium level problem involving Array, Math, String. This walkthrough by NeetCodeIO has 13,667 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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. bank[i] represents the ith row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.
There is one laser beam between any two security devices if both conditions are met:
r1 and r2, where r1 < r2.i where r1 < i < r2, there are no security devices in the ith row.Laser beams are independent, i.e., one beam does not interfere nor join with another.
Return the total number of laser beams in the bank.
Example 1:
Input: bank = ["011001","000000","010100","001000"] Output: 8 Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams: * bank[0][1] -- bank[2][1] * bank[0][1] -- bank[2][3] * bank[0][2] -- bank[2][1] * bank[0][2] -- bank[2][3] * bank[0][5] -- bank[2][1] * bank[0][5] -- bank[2][3] * bank[2][1] -- bank[3][2] * bank[2][3] -- bank[3][2] Note that there is no beam between any device on the 0th row with any on the 3rd row. This is because the 2nd row contains security devices, which breaks the second condition.
Example 2:
Input: bank = ["000","111","000"] Output: 0 Explanation: There does not exist two devices located on two different rows.
Constraints:
m == bank.lengthn == bank[i].length1 <= m, n <= 500bank[i][j] is either '0' or '1'.Problem Overview: You are given a binary m x n matrix representing a bank security system. Each row shows security devices ('1') and empty cells ('0'). A laser beam forms between two rows if both contain devices and every row between them has zero devices. The task is to count the total number of such beams.
Approach 1: Dynamic Programming / Row Device Counting (O(m*n) time, O(1) space)
Scan the matrix row by row and count the number of devices ('1') in each row. Only rows with at least one device participate in beam formation. If the current row has curr devices and the previous non-empty row had prev devices, they form prev * curr beams because every device in the earlier row connects with every device in the current row. Update prev whenever you encounter a non-empty row. This approach works because rows containing zero devices naturally break beam connections. Implementation relies on simple iteration over a matrix and counting within each string row.
Approach 2: Recursive Row Processing (O(m*n) time, O(m) space)
The recursive approach processes rows sequentially while carrying the device count of the previous valid row. For each row, count the number of devices and recursively evaluate the remaining rows. When the current row has devices, compute beams with the previous non-empty row using prev * curr, then update the state before moving forward. The recursion depth is at most m, and each row scan costs O(n). This approach models the same logic as the iterative solution but uses recursion to maintain state across rows.
Recommended for interviews: The dynamic programming style row-count approach is what interviewers expect. It demonstrates recognition that only consecutive non-empty rows matter and avoids unnecessary comparisons. A brute force comparison of all row pairs would be inefficient, while the optimal solution uses simple array iteration and multiplication to achieve linear time over the grid.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming / Row Device Counting | O(m*n) | O(1) | Best general solution. Efficient for large matrices and uses constant extra space. |
| Recursive Row Processing | O(m*n) | O(m) | Useful for understanding row relationships or practicing recursion patterns. |