Number of Laser Beams in a Bank - Solution & Explanation
Problem 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. 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:
- The two devices are located on two different rows:
r1andr2, wherer1 < r2. - For each row
iwherer1 < i < r2, there are no security devices in theithrow.
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'.
Approach Overview
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 1: Dynamic Programming Approach
This approach involves breaking down the problem into overlapping subproblems, solving each subproblem only once, and storing their solutions - typically in a table. This can help reduce redundant calculations and improve efficiency.
The provided C solution uses a dynamic programming array to store the results of intermediate calculations. The base case is initialized, and subsequent entries are computed based on the previous value, iterating from 1 to n, where n is the given input.
Complexity
Time Complexity: O(n), as each subproblem from 1 to n is solved once.
Space Complexity: O(n), due to the storage of results in the dp array.
Approach 2: Recursive Approach
A recursive approach solves the problem by solving smaller instances of the same problem. While this is a straightforward approach, it may lead to inefficiencies without memoization or optimizations because it can repeatedly solve the same subproblems.
This recursive C solution calls itself with a reduced problem size until it hits the base case. Each call multiplies the return value by 2.
Complexity
Time Complexity: O(2^n), due to many duplicate subproblem calculations without memoization.
Space Complexity: O(n), considering the call stack.
Approach 3: Row by Row Counting
We can count the number of safety devices row by row. If the current row does not have any safety devices, we skip it. Otherwise, we multiply the number of safety devices in the current row by the number of safety devices in the previous row, and add it to the answer. Then we update the number of safety devices in the previous row to be the number of safety devices in the current row.
The time complexity is O(m times n), where m and n are the number of rows and columns, respectively. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), as each subproblem from 1 to n is solved once. |
| Recursive Approach | Time Complexity: O(2^n), due to many duplicate subproblem calculations without memoization. |
| Row by Row Counting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Number of Laser Beams in a Bank - Leetcode 2125 - Python • NeetCodeIO • 13,738 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Laser Beams in a Bank easy or hard?
How to solve Number of Laser Beams in a Bank in O(n)?
What is the best approach for Number of Laser Beams in a Bank?
What data structure is used in Number of Laser Beams in a Bank?
What is the time complexity of Number of Laser Beams in a Bank?
Number of Laser Beams in a Bank Python or Java solution approach?
Is Number of Laser Beams in a Bank asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Number of Laser Beams in a Bank with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor