Number of Laser Beams in a Bank

medium array math string matrix

Problem

You are given an m × n binary grid where each row is a floor of a bank and '1' marks a security device. Two devices form a laser beam if they lie on adjacent non-empty rows (any rows in between must be empty). Return the total number of beams.

Inputbank = ["011001", "000000", "010100", "001000"]

Output8

Counts of non-empty rows: 3, 2, 1 → 3*2 + 2*1 = 8.

bank (rows separated by ';', each row of 0/1)

def number_of_beams(bank):
    prev = 0
    total = 0
    for row in bank:
        c = row.count('1')
        if c > 0:
            total += prev * c
            prev = c
    return total

function numberOfBeams(bank) {
  let prev = 0, total = 0;
  for (const row of bank) {
    let c = 0;
    for (const ch of row) if (ch === '1') c++;
    if (c > 0) {
      total += prev * c;
      prev = c;
    }
  }
  return total;
}

class Solution {
    public int numberOfBeams(String[] bank) {
        int prev = 0, total = 0;
        for (String row : bank) {
            int c = 0;
            for (int i = 0; i < row.length(); i++) if (row.charAt(i) == '1') c++;
            if (c > 0) {
                total += prev * c;
                prev = c;
            }
        }
        return total;
    }
}

int numberOfBeams(vector<string>& bank) {
    int prev = 0, total = 0;
    for (auto& row : bank) {
        int c = 0;
        for (char ch : row) if (ch == '1') c++;
        if (c > 0) {
            total += prev * c;
            prev = c;
        }
    }
    return total;
}

Explanation

A laser beam connects a device on one non-empty row to a device on the next non-empty row. So the real question is: how many device pairs span each gap between consecutive non-empty rows? The neat insight is you never need to look at exact positions — only the count of devices in each row matters.

If one non-empty row has prev devices and the next non-empty row has c devices, every device above can shoot to every device below, giving prev * c beams. We just add that up for every adjacent pair of non-empty rows.

The code walks the rows top to bottom, keeping prev = the device count of the last non-empty row seen. For each row we compute c = row.count('1'). Empty rows (where c is 0) are simply skipped, which automatically lets a pair "see through" them.

When a row is non-empty, we do total += prev * c and then set prev = c so the next non-empty row pairs with this one.

Example: ["011001", "000000", "010100", "001000"] has device counts 3, 0, 2, 1. The empty middle row is ignored, so the non-empty counts are 3, 2, 1. The answer is 3*2 + 2*1 = 8.

Time: O(m · n) Space: O(1)