Difficulty: 🟡 Medium
Topics: Array, Math, String, Matrix

Solution

LeetCode 2125 - Number of Laser Beams in a Bank

Problem Understanding

The problem describes a bank floor plan as a binary matrix, represented by an array of strings. Each row corresponds to one row in the bank, and each character in the string represents a cell. A '1' means there is a security device installed in that cell, while a '0' means the cell is empty.

A laser beam exists between two devices if they are located on different rows and every row between them contains no devices at all. In other words, laser beams can only connect devices from consecutive non-empty rows. If there is any intermediate row that contains at least one device, then the connection cannot skip over it.

The key observation is that if two non-empty rows are consecutive with respect to device-containing rows, then every device in the upper row connects to every device in the lower row. If one row contains a devices and the next non-empty row contains b devices, then they contribute a * b laser beams.

The input size constraints are important. Both the number of rows and columns can be as large as 500. This means the total number of cells can reach 250,000. A quadratic or cubic solution involving pairwise device comparisons could become unnecessarily expensive, while a linear scan over all cells is completely reasonable.

Several edge cases are important to consider. A bank with only one non-empty row cannot produce any beams because beams require devices on different rows. Rows filled entirely with zeros must be ignored because they break continuity between non-empty rows. Another important case occurs when every row is empty, which should correctly return zero. The problem guarantees that every character is either '0' or '1', so no additional input validation is needed.

Approaches

Brute Force Approach

A straightforward brute-force solution would first identify every security device in the matrix, then examine every pair of devices located on different rows. For each pair, we would check whether all rows between them are empty. If they are, we count one beam.

This approach is correct because it directly follows the problem definition. Every possible device pair is evaluated independently, and the intermediate rows are verified exactly as required.

However, this approach is inefficient. If there are many devices, the number of device pairs grows rapidly. In the worst case, almost every cell could contain a device, leading to a very large number of comparisons and repeated scans of intermediate rows.

Optimal Approach

The important insight is that beams only exist between consecutive non-empty rows. Suppose one non-empty row has a devices and the next non-empty row has b devices. Every device in the first row connects to every device in the second row, producing exactly a * b beams.

Rows containing only zeros do not participate directly. They merely separate rows, and because the problem explicitly allows beams through completely empty rows, we only need to remember the most recent non-empty row.

This means we can process the matrix row by row. For each row, count how many devices it contains. If the row is non-empty, multiply its device count by the device count of the previous non-empty row and add the result to the answer.

This reduces the problem to a single pass through the matrix.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m² × n²)	O(m × n)	Compares device pairs and checks intermediate rows
Optimal	O(m × n)	O(1)	Counts devices row by row

Algorithm Walkthrough

Initialize a variable previous_devices to store the number of devices in the most recent non-empty row.
Initialize another variable total_beams to store the final answer.
Iterate through each row in the bank.
For the current row, count how many '1' characters appear. This gives the number of devices in that row.
If the current row contains zero devices, skip it entirely. Empty rows do not create or terminate beams.
If the row is non-empty, multiply the current device count by previous_devices. This represents all possible beams between the current row and the previous non-empty row.
Add this product to total_beams.
Update previous_devices to the current row's device count.
Continue until all rows are processed.
Return total_beams.

Why it works

The algorithm works because beams can only exist between consecutive non-empty rows. Any non-empty row blocks beams from extending farther downward. Therefore, when processing a row, the only valid beam connections come from the immediately preceding non-empty row. Multiplying the device counts correctly computes all pairwise connections between those two rows.

Python Solution

from typing import List

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        previous_devices = 0
        total_beams = 0

        for row in bank:
            current_devices = row.count('1')

            if current_devices == 0:
                continue

            total_beams += previous_devices * current_devices
            previous_devices = current_devices

        return total_beams

The implementation follows the algorithm directly. The variable previous_devices tracks the number of devices in the last non-empty row encountered so far. For each row, row.count('1') determines how many devices exist in that row.

If a row is empty, it is ignored because empty rows do not affect beam formation. When a row contains devices, the number of beams formed with the previous non-empty row is calculated using multiplication. After adding those beams to the total, the current row becomes the new reference row.

The solution performs a single scan through the matrix and uses only constant extra memory.

Go Solution

func numberOfBeams(bank []string) int {
    previousDevices := 0
    totalBeams := 0

    for _, row := range bank {
        currentDevices := 0

        for _, cell := range row {
            if cell == '1' {
                currentDevices++
            }
        }

        if currentDevices == 0 {
            continue
        }

        totalBeams += previousDevices * currentDevices
        previousDevices = currentDevices
    }

    return totalBeams
}

The Go implementation follows the same logic as the Python version. Since Go strings are iterable by rune, the inner loop checks each character individually. Integer overflow is not a concern because the maximum possible answer fits comfortably within Go's standard integer range for the given constraints.

Unlike Python, Go does not provide a built-in count method for strings, so device counting is performed manually inside the nested loop.

Worked Examples

Example 1

Input:
bank = ["011001","000000","010100","001000"]

Process each row one at a time.

Row	Devices in Row	Previous Non-Empty Devices	New Beams	Total
"011001"	3	0	0 × 3 = 0	0
"000000"	0	3	skipped	0
"010100"	2	3	3 × 2 = 6	6
"001000"	1	2	2 × 1 = 2	8

Final answer:

Example 2

Input:
bank = ["000","111","000"]

Row	Devices in Row	Previous Non-Empty Devices	New Beams
"000"	0	0	skipped
"111"	3	0	0 × 3 = 0
"000"	0	3	skipped

Final answer:

Example 3

Input:
bank = ["1"]

Row	Devices in Row	Previous Non-Empty Devices	New Beams	Total
"1"	1	0	0 × 1 = 0	0

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is visited exactly once
Space	O(1)	Only a few integer variables are used

The algorithm scans every row and every column exactly once. No additional data structures proportional to input size are required. Therefore, the runtime is linear in the size of the matrix, and the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        previous_devices = 0
        total_beams = 0

        for row in bank:
            current_devices = row.count('1')

            if current_devices == 0:
                continue

            total_beams += previous_devices * current_devices
            previous_devices = current_devices

        return total_beams

sol = Solution()

assert sol.numberOfBeams(
    ["011001", "000000", "010100", "001000"]
) == 8  # provided example with multiple beam groups

assert sol.numberOfBeams(
    ["000", "111", "000"]
) == 0  # only one non-empty row

assert sol.numberOfBeams(
    ["1"]
) == 0  # single row with one device

assert sol.numberOfBeams(
    ["000", "000"]
) == 0  # all rows empty

assert sol.numberOfBeams(
    ["111", "111"]
) == 9  # every device in first row connects to every device in second row

assert sol.numberOfBeams(
    ["101", "000", "101"]
) == 4  # empty row between non-empty rows still allows beams

assert sol.numberOfBeams(
    ["100", "010", "001"]
) == 2  # consecutive single-device rows

assert sol.numberOfBeams(
    ["11111"]
) == 0  # only one row, no cross-row beams

assert sol.numberOfBeams(
    ["001", "000", "000", "100"]
) == 1  # distant non-empty rows separated by empty rows

assert sol.numberOfBeams(
    ["110", "011", "101"]
) == 10  # multiple consecutive non-empty rows

Test	Why
`["011001","000000","010100","001000"]`	Validates standard multi-row beam counting
`["000","111","000"]`	Ensures a single non-empty row produces zero beams
`["1"]`	Smallest possible non-empty input
`["000","000"]`	Verifies all-empty bank handling
`["111","111"]`	Tests dense beam generation
`["101","000","101"]`	Confirms empty rows do not block consecutive non-empty rows
`["100","010","001"]`	Tests chaining across consecutive rows
`["11111"]`	Verifies single-row behavior
`["001","000","000","100"]`	Tests multiple empty separator rows
`["110","011","101"]`	Validates accumulation across several non-empty rows

Edge Cases

One important edge case occurs when the bank contains only empty rows. In this situation, no devices exist anywhere in the matrix, so no beams can possibly form. A buggy implementation might incorrectly attempt to connect empty rows or assume at least one device exists. The current implementation handles this naturally because rows with zero devices are skipped entirely.

Another important case happens when there is exactly one non-empty row. Since beams require devices on different rows, the answer must be zero. The implementation correctly handles this because previous_devices starts at zero, so the first non-empty row contributes no beams.

A third tricky case involves multiple empty rows between two non-empty rows. It might seem that distance matters, but the problem only requires intermediate rows to contain no devices. The implementation correctly ignores all empty rows and directly connects consecutive non-empty rows, regardless of how many empty rows separate them.

A final edge case appears when two consecutive non-empty rows contain many devices. In this case, every device in the first row connects to every device in the second row, producing a large multiplicative contribution. The algorithm correctly computes this using previous_devices * current_devices, ensuring all pairwise beams are counted exactly once.