Number of Laser Beams in a Bank
MedPrompt
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'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach first pre-computes the number of security devices in each row and stores them in an array. It then iterates through the rows. For each row containing devices, it performs a search to find the next subsequent row that also has devices, and then calculates the beams between this pair.
Algorithm
- Create an integer array
deviceCountsof sizem(number of rows). - Iterate through the
bankto populatedeviceCountsby counting '1's in each row. This is the pre-computation step. - Initialize
totalBeams = 0. - Use a primary loop to iterate through each row index
ifrom0tom-1. - If
deviceCounts[i]is greater than zero, it means we have found a row with devices. - Start a nested secondary loop to find the index
jof the very next row (wherej > i) that contains devices (deviceCounts[j] > 0). - If such a row
jis found, calculate the beams by multiplyingdeviceCounts[i] * deviceCounts[j]and add it tototalBeams. Then, break the inner loop since we only care about the next adjacent row with devices. - Return
totalBeamsafter the loops complete.
Walkthrough
The strategy here is to separate the counting of devices from the calculation of beams. First, we perform a full pass over the m x n grid to determine the number of security devices in each of the m rows, storing these values in an auxiliary array, deviceCounts. This step takes O(m*n) time.
Next, we iterate through the deviceCounts array. For each row i that has one or more devices, we initiate another loop that starts from i+1 to find the first row j that also contains devices. Because these two rows are adjacent in terms of containing devices (no other rows between them have devices), they satisfy the problem's condition. We then add the product of their device counts (deviceCounts[i] * deviceCounts[j]) to our total. This nested search for the next valid row leads to a time complexity of O(m^2) for the calculation part, making it less efficient than more optimized solutions.
Complexity
Time
O(m*n + m^2) - `O(m*n)` for pre-computing device counts and `O(m^2)` for the nested loops to find adjacent device rows.
Space
O(m) - to store the `deviceCounts` array, where `m` is the number of rows.
Trade-offs
Pros
It's a conceptually straightforward improvement over a pure brute-force
O(m^3)check of all pairs.Separating device counting from beam calculation can make the logic easier to follow.
Cons
The time complexity is quadratic with respect to the number of rows (
m), making it inefficient for largem.It re-scans portions of the
deviceCountsarray repeatedly, which is redundant.
This approach improves efficiency by filtering out all the rows that do not contain any security devices in a first pass. It collects the device counts of only the relevant rows into a list and then calculates the beams in a second, much shorter pass over this new list.
Algorithm
- Initialize an empty list of integers,
rowsWithDevices. - Iterate through each row string in the
bankarray (First Pass).- Count the number of '1's in the current row string.
- If the count is greater than 0, add the count to the
rowsWithDeviceslist.
- If the size of
rowsWithDevicesis less than 2, return 0 as no beams can be formed. - Initialize
totalBeams = 0. - Iterate from
i = 0torowsWithDevices.size() - 2(Second Pass).- The elements at
iandi+1represent device counts of two adjacent rows with devices. Calculate beams by multiplying them:rowsWithDevices.get(i) * rowsWithDevices.get(i+1). - Add the result to
totalBeams.
- The elements at
- Return
totalBeams.
Walkthrough
The key insight for this method is that rows with zero devices are only important as separators. We can ignore them and focus only on the rows that contain devices.
In the first pass, we iterate through the entire m x n bank. For each row, we count its devices. If a row's device count is positive, we add that count to a dynamic list, say rowsWithDevices. After this pass, this list will contain the device counts of all device-bearing rows, in their original order. For example, if rows 0, 2, and 3 have devices, the list will be [count(row 0), count(row 2), count(row 3)].
In the second pass, we simply iterate through our rowsWithDevices list. Since the list only contains adjacent device-bearing rows, we can calculate the beams between each consecutive pair. For each index i (from 0 to size-2), we add the product rowsWithDevices[i] * rowsWithDevices[i+1] to our total. This approach avoids the inefficient O(m^2) search by pre-processing the input into a compact form.
Complexity
Time
O(m*n) - The time is dominated by the first pass, which iterates through every cell of the bank once. The second pass takes at most `O(m)` time.
Space
O(m) - In the worst-case scenario where every row has at least one device, the `rowsWithDevices` list will store `m` integers.
Trade-offs
Pros
Efficient time complexity as it processes the grid and the resulting list linearly.
The logic is clean and easy to understand, clearly separating the data gathering and calculation phases.
Cons
Requires extra space proportional to the number of rows, which might be a concern for very large inputs with memory constraints.
This is the most optimal approach, calculating the total number of beams in a single pass through the bank's rows while using only a constant amount of extra space. It avoids storing all device counts by only keeping track of the count from the most recent row with devices.
Algorithm
- Initialize
totalBeams = 0andprevRowDeviceCount = 0. - Iterate through each row string in the
bankarray.- Count the number of '1's in the current row, let's call it
currentRowDeviceCount. - If
currentRowDeviceCountis greater than 0:- Calculate beams with the previous device-bearing row:
beams = prevRowDeviceCount * currentRowDeviceCount. - Add this to
totalBeams. - Update
prevRowDeviceCountto becurrentRowDeviceCountfor the next iteration.
- Calculate beams with the previous device-bearing row:
- Count the number of '1's in the current row, let's call it
- Return
totalBeams.
Walkthrough
This approach refines the two-pass method by recognizing that to calculate the beams, we don't need a list of all device counts. We only ever need the count from the current row and the count from the immediately preceding row that had devices.
We can achieve this with a single pass and two variables: totalBeams and prevRowDeviceCount. We iterate through each row of the bank. For each row, we first compute its currentRowDeviceCount. If this count is zero, the row is empty, and we do nothing, preserving the prevRowDeviceCount from an earlier row. If currentRowDeviceCount is positive, we have found a row with devices. We can now form beams with the devices from the last non-empty row we saw, so we add prevRowDeviceCount * currentRowDeviceCount to our totalBeams. After that, we update prevRowDeviceCount = currentRowDeviceCount, as this row now becomes the 'previous' one for any subsequent rows with devices. This elegant solution processes the bank in one go with minimal memory overhead.
Complexity
Time
O(m*n) - We iterate through each of the `m` rows of length `n` exactly once.
Space
O(1) - We only use a few integer variables (`totalBeams`, `prevRowDeviceCount`, `currentRowDeviceCount`), which does not depend on the input size.
Trade-offs
Pros
Optimal time complexity of
O(m*n).Optimal space complexity of
O(1), making it highly memory-efficient.Solves the problem in a single, elegant pass through the input data.
Cons
The logic, while simple, might be slightly less intuitive to derive initially compared to a two-pass approach.
Solutions
Solution
class Solution {public int numberOfBeams(String[] bank) { int last = 0; int ans = 0; for (String b : bank) { int t = 0; for (char c : b.toCharArray()) { if (c == '1') { ++t; } } if (t > 0) { ans += last * t; last = t; } } return ans; }}class Solution {public: int numberOfBeams(vector<string> &bank) { int ans = 0; int last = 0; for (auto &b : bank) { int t = 0; for (char &c : b) if (c == '1') ++t; if (t) { ans += last * t; last = t; } } return ans; }};class Solution: def numberOfBeams(self, bank: List[str]) -> int: last = ans = 0 for b in bank: if (t: = b . count('1')) > 0: ans += last * t last = t return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.