Problem Description

You are given a 2D floor plan of a bank represented as a binary string array called bank. Each string in the array represents a row of the floor plan, where '0' means an empty cell and '1' means there's a security device in that cell.

The security system creates laser beams between security devices according to these rules:

• A laser beam connects two security devices only if they are on different rows
• For a beam to exist between devices on row r1 and row r2 (where r1 < r2), all rows between them must have no security devices

Each pair of devices that meets these conditions creates exactly one laser beam, and beams don't interfere with each other.

Your task is to count the total number of laser beams in the bank.

For example, if you have security devices on row 0 and row 2, with row 1 being empty, then each device on row 0 forms a beam with each device on row 2. If row 0 has 3 devices and row 2 has 2 devices, there would be 3 × 2 = 6 laser beams between these two rows.

The key insight is that laser beams only form between consecutive rows that have security devices (ignoring empty rows in between). So you need to find each pair of non-empty rows and multiply their device counts to get the number of beams between them.

Intuition

Let's think about when laser beams actually form. If we have security devices on multiple rows, beams only connect devices between "adjacent" rows that have devices (where "adjacent" means no other rows with devices in between, though there can be empty rows).

Consider this example: if row 0 has devices, row 1 is empty, row 2 has devices, row 3 is empty, and row 4 has devices. The beams would form between:

• Row 0 and Row 2 (since row 1 is empty)
• Row 2 and Row 4 (since row 3 is empty)

There would be NO beams between row 0 and row 4 because row 2 has devices in between them.

This means we can simplify the problem: we only need to consider consecutive non-empty rows. For each pair of consecutive non-empty rows, the number of beams is simply the product of the number of devices in each row.

The algorithm becomes straightforward:

1. Skip any empty rows (rows with no '1's)
2. When we find a row with devices, multiply its device count by the previous non-empty row's device count
3. Add this product to our total
4. Update our "previous row" count to the current row's count for the next iteration

This works because we're essentially tracking pairs of consecutive non-empty rows and calculating devices_in_row1 × devices_in_row2 for each pair, which gives us the total number of beams between those rows.

Learn more about Math patterns.

Solution Approach

The solution uses a simple row-by-row counting approach with two key variables:

• ans: accumulates the total number of laser beams
• pre: stores the count of security devices from the previous non-empty row

Here's the step-by-step implementation:

1. Initialize variables: Start with ans = 0 (total beams) and pre = 0 (no previous row initially).

2. Iterate through each row: For each row in the bank:

   • Count the number of '1's in the current row using row.count("1") and store it in cur
   • If cur > 0 (the row has security devices):
     • Calculate beams between this row and the previous non-empty row: pre * cur
     • Add these beams to the total: ans += pre * cur
     • Update pre = cur for the next iteration

3. Return the result: After processing all rows, ans contains the total number of laser beams.

The key insight is that we only update pre when we encounter a non-empty row, effectively skipping empty rows. This ensures we're always calculating beams between consecutive non-empty rows.

For example, with rows having [3, 0, 2, 0, 1] devices:

• Row 0 (3 devices): ans = 0 + 0*3 = 0, pre = 3
• Row 1 (0 devices): skip
• Row 2 (2 devices): ans = 0 + 3*2 = 6, pre = 2
• Row 3 (0 devices): skip
• Row 4 (1 device): ans = 6 + 2*1 = 8, pre = 1
• Final answer: 8 beams

The time complexity is O(m*n) where m is the number of rows and n is the length of each row (for counting '1's). The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this bank floor plan:

bank = ["011", "000", "101", "001"]

This represents:

• Row 0: "011" → 2 security devices
• Row 1: "000" → 0 security devices (empty)
• Row 2: "101" → 2 security devices
• Row 3: "001" → 1 security device

Step-by-step execution:

1. Initialize: ans = 0, pre = 0

2. Process Row 0 ("011"):

   • Count devices: cur = 2 (two '1's)
   • Since cur > 0:
     • Calculate beams: pre * cur = 0 * 2 = 0
     • Update total: ans = 0 + 0 = 0
     • Update previous: pre = 2

3. Process Row 1 ("000"):

   • Count devices: cur = 0 (no '1's)
   • Since cur = 0, skip this row
   • pre remains 2, ans remains 0

4. Process Row 2 ("101"):

   • Count devices: cur = 2 (two '1's)
   • Since cur > 0:
     • Calculate beams: pre * cur = 2 * 2 = 4
     • Update total: ans = 0 + 4 = 4
     • Update previous: pre = 2

   These 4 beams connect: device at (0,0) to both devices in row 2, and device at (0,2) to both devices in row 2

5. Process Row 3 ("001"):

   • Count devices: cur = 1 (one '1')
   • Since cur > 0:
     • Calculate beams: pre * cur = 2 * 1 = 2
     • Update total: ans = 4 + 2 = 6
     • Update previous: pre = 1

   These 2 beams connect the 2 devices in row 2 to the 1 device in row 3

Final Result: Total beams = 6

The algorithm correctly identifies that beams form between:

• Row 0 and Row 2: 2 × 2 = 4 beams
• Row 2 and Row 3: 2 × 1 = 2 beams
• Total: 4 + 2 = 6 beams

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n), where m is the number of rows in the bank array and n is the length of each string (number of columns). The algorithm iterates through each row (m iterations), and for each row, the count("1") operation scans through all n characters in the string, resulting in O(n) time per row. Therefore, the total time complexity is O(m × n).

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for variables ans, pre, and cur, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting Beams Within the Same Row

Issue: A common misunderstanding is thinking that devices within the same row can form laser beams with each other. This would lead to incorrectly adding combinations like C(n, 2) for each row with n devices.

Wrong Approach:

for row in bank:
    curr_devices = row.count("1")
    if curr_devices > 1:
        # WRONG: counting beams within the same row
        total_beams += curr_devices * (curr_devices - 1) // 2

Solution: Remember that laser beams only form between devices on different rows, never within the same row. The correct approach multiplies device counts between different rows only.

Pitfall 2: Incorrectly Handling the First Row

Issue: Some might think the first row with devices doesn't contribute any beams since there's no previous row, leading to skipping it entirely or handling it as a special case.

Wrong Approach:

first_row_processed = False
for row in bank:
    curr_devices = row.count("1")
    if curr_devices > 0:
        if not first_row_processed:
            first_row_processed = True
            prev_devices = curr_devices
            continue  # WRONG: skipping first row entirely
        total_beams += prev_devices * curr_devices
        prev_devices = curr_devices

Solution: The correct implementation naturally handles the first row. When prev_devices = 0 initially, the multiplication 0 * curr_devices = 0 correctly adds no beams for the first row, then updates prev_devices for subsequent calculations.

Pitfall 3: Counting Beams Between Non-Adjacent Rows with Devices

Issue: Misinterpreting that devices can form beams across multiple empty rows might lead to tracking all previous rows with devices and calculating beams between all pairs.

Wrong Approach:

rows_with_devices = []
for i, row in enumerate(bank):
    curr_devices = row.count("1")
    if curr_devices > 0:
        # WRONG: calculating beams between all pairs of rows
        for prev_count in rows_with_devices:
            total_beams += prev_count * curr_devices
        rows_with_devices.append(curr_devices)

Solution: The problem clearly states beams only form between consecutive non-empty rows (ignoring empty rows in between). The correct approach only tracks the immediately previous non-empty row using a single variable prev_devices.