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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


![](https://assets.leetcode.com/uploads/2021/12/24/laser1.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

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2021/12/24/laser2.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'.

Solution

Method 1 – Count Devices in Non-Empty Rows

Intuition

Laser beams only exist between consecutive non-empty rows (rows with at least one device). For each such pair, the number of beams is the product of the number of devices in the two rows.

Approach

  1. For each row, count the number of devices (number of ‘1’s).
  2. For each consecutive pair of non-empty rows, multiply their device counts and sum.
  3. Return the total.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int prev = 0, ans = 0;
        for (auto& row : bank) {
            int cnt = 0;
            for (char c : row) if (c == '1') ++cnt;
            if (cnt) { ans += prev * cnt; prev = cnt; }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func numberOfBeams(bank []string) int {
    prev, ans := 0, 0
    for _, row := range bank {
        cnt := 0
        for i := 0; i < len(row); i++ {
            if row[i] == '1' { cnt++ }
        }
        if cnt > 0 {
            ans += prev * cnt
            prev = cnt
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int numberOfBeams(String[] bank) {
        int prev = 0, ans = 0;
        for (String row : bank) {
            int cnt = 0;
            for (char c : row.toCharArray()) if (c == '1') cnt++;
            if (cnt > 0) { ans += prev * cnt; prev = cnt; }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun numberOfBeams(bank: Array<String>): Int {
        var prev = 0; var ans = 0
        for (row in bank) {
            val cnt = row.count { it == '1' }
            if (cnt > 0) {
                ans += prev * cnt
                prev = cnt
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def numberOfBeams(self, bank: list[str]) -> int:
        prev, ans = 0, 0
        for row in bank:
            cnt = row.count('1')
            if cnt:
                ans += prev * cnt
                prev = cnt
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn number_of_beams(bank: Vec<String>) -> i32 {
        let mut prev = 0;
        let mut ans = 0;
        for row in bank {
            let cnt = row.chars().filter(|&c| c == '1').count() as i32;
            if cnt > 0 {
                ans += prev * cnt;
                prev = cnt;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    numberOfBeams(bank: string[]): number {
        let prev = 0, ans = 0;
        for (const row of bank) {
            const cnt = row.split('').filter(c => c === '1').length;
            if (cnt) {
                ans += prev * cnt;
                prev = cnt;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m*n), where m is the number of rows and n is the number of columns.
  • 🧺 Space complexity: O(1).