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
- A beam only exists between devices in rows with no device in between, so empty rows act as separators and contribute nothing.
- Collapse each row to the count of devices it holds.
- Walk the rows keeping the count of the most recent non-empty row; each new non-empty row adds
prev_count * current_countbeams. - 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
prevmust 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.