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

LeetCode

https://leetcode.com/problems/number-of-laser-beams-in-a-bank/description/

Constraints

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

Examples

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.

Different Approaches

1️⃣ Traversing

Approach:

1. Initialize two variables
   1. prev = 0: To store the number of devices in the last non-empty row.
   2. beams = 0: Final count of laser beams.
2. Loop through each row in the bank
   1. For each row:
      1. Count how many '1's (devices) are in that row → call this curr.
      2. If curr == 0: It's an empty row → ignore it.
      3. Else:
         1. Calculate beams += prev * curr
         2. Update prev = curr (this row becomes the new "last non-empty row")
3. Return beams at the end.

Code:

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int prev = 0;     // Stores the number of devices in the last non-empty row
        int beams = 0;    // Final result - total number of laser beams

        for (int i = 0; i < bank.size(); i++) {
            int curr = 0;   // Count devices in the current row

            // Count number of '1's in the current row
            for (char ch: bank[i]) {
                if (ch - '0' == 1) {
                    curr++;
                }
            }

            // If current row has devices, add beams between this row and previous one
            beams += prev * curr;

            // Update prev only if current row has any devices
            if (curr != 0) {
                prev = curr;
            }
        }

        return beams;
    }
};

Complexity Analysis:

• Time Complexity:O(m * n)
• Space Complexity:O(1)