⚡Flashcard Drill➔
NeetCode #808LC-2125MediumGreedy
← Back to All Problems

#808 · #2125 · Number of Laser Beams in a Bank(银行中的激光束数量)

📌 Problem Statement & Constraints

A bank is represented as an m x n grid of strings where bank[i] describes row i: 1 is a security device and 0 is empty. A laser beam connects two devices on two different rows if no device lies between them. Return the total number of beams. Constraints: 1 <= m, n <= 500, each bank[i] contains only 0 and 1.

💡 Core Algorithmic Approaches

  1. A beam only exists between devices in rows with no device in between, so empty rows act as separators and contribute nothing.
  2. Collapse each row to the count of devices it holds.
  3. Walk the rows keeping the count of the most recent non-empty row; each new non-empty row adds prev_count * current_count beams.
  4. This is correct because every device in the previous non-empty row can pair with every device in the current row, and no other rows sit between them.

💻 Benchmark Python3 Implementation

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        prev = 0
        total = 0
        for row in bank:
            cnt = row.count("1")
            if cnt == 0:
                continue                    # empty rows break the chain
            total += prev * cnt             # every device pairs across
            prev = cnt
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell of the grid is read once.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Pairing across empty rows: an empty row between two device rows blocks the beam, so prev must not be updated by empty rows.
  • Counting adjacent devices within a row: beams are strictly between different rows; devices in the same row never connect.
  • Summing counts instead of products: the number of beams is the product of the two row counts, not their sum.
  • Using row.count(1): the rows are strings, so the argument must be the string "1", not the integer 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems