#2125

Medium

LeetCode Problem Workspace

Number of Laser Beams in a Bank

Calculate total laser beams in a bank floor plan using array counting and math logic between security devices on different rows.

array math string matrix

Problem Statement

You are given a 0-indexed binary string array bank representing the layout of a bank floor, where bank[i][j] is '1' if a security device exists in that cell and '0' if it is empty. Each device can form laser beams with devices on other rows under strict conditions.

A laser beam forms between two devices only if there are no devices in any intermediate row between their rows. Beams are independent and do not interfere. Count all valid beams across the entire bank matrix using efficient array traversal and multiplication of device counts.

Examples

Example 1

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

Output: 8

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

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 Approach

Count devices per row

Iterate through each row of the bank array and count the number of security devices. Store these counts in a separate list to represent active devices per row, skipping rows with zero devices since they cannot form beams.

Compute beams between consecutive non-empty rows

Traverse the list of non-zero device counts. For each pair of consecutive rows with devices, multiply their counts to find the total beams between them. This leverages the array plus math pattern to efficiently calculate interactions without checking each cell individually.

Aggregate total beams

Sum the products from all consecutive non-empty row pairs to get the total number of laser beams. This approach avoids double-counting and naturally handles rows with zero devices by skipping them.

Complexity Analysis

Metric	Value
Time	O(M * N)
Space	O(1)

Time complexity is O(M * N) because each cell in the bank matrix is checked once to count devices. Space complexity is O(1) extra space, aside from storing temporary counts per row, making it efficient for large matrices.

What Interviewers Usually Probe

Emphasize counting devices per row and skipping empty rows for efficiency.
Ask why multiplying counts of consecutive non-empty rows correctly represents laser beams.
Check if candidates handle large bank matrices without nested cell-to-cell comparisons.

Common Pitfalls or Variants

Common pitfalls

Counting beams for rows with zero devices, which incorrectly inflates the total.
Multiplying non-consecutive rows and ignoring the requirement of no intermediate devices.
Iterating through each possible cell pair, leading to timeouts for large matrices.

Follow-up variants

Modify the problem to include diagonal laser beams and adjust counting accordingly.
Consider banks with variable row lengths and handle missing cells in the array.
Count beams when devices can only connect within a maximum row distance instead of any row.

FAQ

What is the main strategy to count laser beams in a bank?

Use an array to count devices per row, then multiply counts of consecutive non-empty rows to find total beams.

Why do we skip rows with zero devices?

Rows without devices cannot form beams and must be skipped to prevent overcounting in the array plus math calculation.

Can this approach handle large matrices efficiently?

Yes, because it avoids nested loops over all cells and only processes counts of non-empty rows, keeping O(M*N) time.

Does the order of rows affect the laser beam count?

Yes, only consecutive non-empty rows are considered for multiplication; intermediate empty rows break potential beams.

What pattern is this problem best associated with?

It is an array plus math pattern, focusing on counting elements and applying multiplication across valid row pairs.

terminal

Solution

Solution 1: Row by Row Counting

We can count the number of safety devices row by row. If the current row does not have any safety devices, we skip it. Otherwise, we multiply the number of safety devices in the current row by the number of safety devices in the previous row, and add it to the answer. Then we update the number of safety devices in the previous row to be the number of safety devices in the current row.

1

2

3

4

5

6

7

8

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        ans = pre = 0
        for row in bank:
            if (cur := row.count("1")) > 0:
                ans += pre * cur
                pre = cur
        return ans

Continue Practicing

#2033 minimum operations to make a uni value grid #2019 the score of students solving math expression #1878 get biggest three rhombus sums in a grid