# Number of Laser Beams in a Bank
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-laser-beams-in-a-bank)
Canonical: https://scaleengineer.com/dsa/problems/number-of-laser-beams-in-a-bank
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, String, Matrix
---
## Problem
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**: `r1` and `r2`, where `r1 < r2`.
* For **each** row `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:**

![](https://assets.glich.co/dsa/number-of-laser-beams-in-a-bank/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/number-of-laser-beams-in-a-bank/image1.jpg) 

**Input:** bank = ["000","111","000"]
**Output:** 0
**Explanation:** There does not exist two devices located on two different rows.

**Constraints:**

* `m == bank.length`
* `n == bank[i].length`
* `1 <= m, n <= 500`
* `bank[i][j]` is either `'0'` or `'1'`.

# Approaches
## Pre-computation with Iterative Search
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.
**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.
**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 large `m`.; It re-scans portions of the `deviceCounts` array repeatedly, which is redundant.
### Explanation
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.
### Algorithm
*   Create an integer array `deviceCounts` of size `m` (number of rows).
*   Iterate through the `bank` to populate `deviceCounts` by 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 `i` from `0` to `m-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 `j` of the very next row (where `j > i`) that contains devices (`deviceCounts[j] > 0`).
*   If such a row `j` is found, calculate the beams by multiplying `deviceCounts[i] * deviceCounts[j]` and add it to `totalBeams`. Then, break the inner loop since we only care about the next adjacent row with devices.
*   Return `totalBeams` after the loops complete.

## Two-Pass Approach using an Auxiliary List
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.
**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.
**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.
### Explanation
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.
### Algorithm
*   Initialize an empty list of integers, `rowsWithDevices`.
*   Iterate through each row string in the `bank` array (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 `rowsWithDevices` list.
*   If the size of `rowsWithDevices` is less than 2, return 0 as no beams can be formed.
*   Initialize `totalBeams = 0`.
*   Iterate from `i = 0` to `rowsWithDevices.size() - 2` (Second Pass).
    *   The elements at `i` and `i+1` represent 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`.
*   Return `totalBeams`.

## Single-Pass Constant Space Approach
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.
**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.
**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.
### Explanation
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.
### Algorithm
*   Initialize `totalBeams = 0` and `prevRowDeviceCount = 0`.
*   Iterate through each row string in the `bank` array.
    *   Count the number of '1's in the current row, let's call it `currentRowDeviceCount`.
    *   If `currentRowDeviceCount` is greater than 0:
        *   Calculate beams with the previous device-bearing row: `beams = prevRowDeviceCount * currentRowDeviceCount`.
        *   Add this to `totalBeams`.
        *   Update `prevRowDeviceCount` to be `currentRowDeviceCount` for the next iteration.
*   Return `totalBeams`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```