2125. Number of Laser Beams in a Bank - Explanation

Description

The equal-length strings in bank describe rows of cells. A 1 marks a security device and a 0 marks an empty cell. Two devices form one laser beam exactly when they are on different rows and every row strictly between them contains no devices. Their columns do not matter, and beams do not block each other. Return the total number of beams.

Filled circles mark security devices; dashed lines connect devices with laser beams.

Example 1:

Number of Laser Beams in a Bank, example 1: illustration of the example

Input: bank = ["101","000","011"]

Output: 4

Explanation: The first and last rows each have two devices, with an empty row between them. Every device in the first row connects to both in the last row, giving 2 times 2 = 4 beams.

Example 2:

Number of Laser Beams in a Bank, example 2: illustration of the example

Input: bank = ["111"]

Output: 0

Explanation: All devices are in the same row, so no pair meets the different-row condition.

Example 3:

Number of Laser Beams in a Bank, example 3: illustration of the example

Input: bank = ["10","01","10"]

Output: 2

Explanation: There is one beam from row 0 to row 1 and one from row 1 to row 2. Row 1 contains a device, so row 0 cannot connect directly to row 2.

Constraints:

1 <= bank.length <= 500
1 <= bank[i].length <= 500
All rows have the same length.
Each character is 0 or 1.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Iteration - Traversing rows of a 2D grid and processing each element
String Counting - Counting occurrences of a specific character in a string
Basic Math (Multiplication) - Understanding that pairs between two groups form a * b combinations

1. Counting

Intuition

Laser beams only form between adjacent rows that contain at least one security device. If one row has a devices and the next non-empty row has b devices, they form a * b beams. We track the count from the previous non-empty row and multiply it by the current row's count whenever we encounter a new row with devices.

Algorithm

Initialize prev with the count of '1's in the first row and res to zero.
For each subsequent row, count the number of '1's (curr).
If curr > 0, add prev * curr to res and update prev = curr.
Return res.

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        prev = bank[0].count("1")
        res = 0

        for i in range(1, len(bank)):
            curr = bank[i].count("1")
            if curr:
                res += prev * curr
                prev = curr

        return res

public class Solution {
    public int numberOfBeams(String[] bank) {
        int prev = countOnes(bank[0]);
        int res = 0;

        for (int i = 1; i < bank.length; i++) {
            int curr = countOnes(bank[i]);
            if (curr > 0) {
                res += prev * curr;
                prev = curr;
            }
        }

        return res;
    }

    private int countOnes(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') count++;
        }
        return count;
    }
}

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int prev = countOnes(bank[0]);
        int res = 0;

        for (int i = 1; i < bank.size(); i++) {
            int curr = countOnes(bank[i]);
            if (curr > 0) {
                res += prev * curr;
                prev = curr;
            }
        }

        return res;
    }

private:
    int countOnes(const string& s) {
        return count(s.begin(), s.end(), '1');
    }
};

class Solution {
    /**
     * @param {string[]} bank
     * @return {number}
     */
    numberOfBeams(bank) {
        const countOnes = (s) => {
            let cnt = 0;
            for (let c of s) {
                if (c === '1') cnt += 1;
            }
            return cnt;
        };

        let prev = countOnes(bank[0]);
        let res = 0;

        for (let i = 1; i < bank.length; i++) {
            let curr = countOnes(bank[i]);
            if (curr > 0) {
                res += prev * curr;
                prev = curr;
            }
        }

        return res;
    }
}

public class Solution {
    public int NumberOfBeams(string[] bank) {
        int prev = CountOnes(bank[0]);
        int res = 0;

        for (int i = 1; i < bank.Length; i++) {
            int curr = CountOnes(bank[i]);
            if (curr > 0) {
                res += prev * curr;
                prev = curr;
            }
        }

        return res;
    }

    private int CountOnes(string s) {
        int count = 0;
        foreach (char c in s) {
            if (c == '1') count++;
        }
        return count;
    }
}

func numberOfBeams(bank []string) int {
    countOnes := func(s string) int {
        count := 0
        for _, c := range s {
            if c == '1' {
                count++
            }
        }
        return count
    }

    prev := countOnes(bank[0])
    res := 0

    for i := 1; i < len(bank); i++ {
        curr := countOnes(bank[i])
        if curr > 0 {
            res += prev * curr
            prev = curr
        }
    }

    return res
}

class Solution {
    fun numberOfBeams(bank: Array<String>): Int {
        fun countOnes(s: String): Int {
            return s.count { it == '1' }
        }

        var prev = countOnes(bank[0])
        var res = 0

        for (i in 1 until bank.size) {
            val curr = countOnes(bank[i])
            if (curr > 0) {
                res += prev * curr
                prev = curr
            }
        }

        return res
    }
}

class Solution {
    func numberOfBeams(_ bank: [String]) -> Int {
        func countOnes(_ s: String) -> Int {
            return s.filter { $0 == "1" }.count
        }

        var prev = countOnes(bank[0])
        var res = 0

        for i in 1..<bank.count {
            let curr = countOnes(bank[i])
            if curr > 0 {
                res += prev * curr
                prev = curr
            }
        }

        return res
    }
}

impl Solution {
    pub fn number_of_beams(bank: Vec<String>) -> i32 {
        let count_ones = |s: &str| -> i32 {
            s.chars().filter(|&c| c == '1').count() as i32
        };

        let mut prev = count_ones(&bank[0]);
        let mut res = 0;

        for i in 1..bank.len() {
            let curr = count_ones(&bank[i]);
            if curr > 0 {
                res += prev * curr;
                prev = curr;
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(1)$ extra space.

Where $m$ is the number of rows and $n$ is the number of columns.

Common Pitfalls

Counting Empty Rows in Beam Calculations

Rows with zero security devices should be skipped entirely. A common mistake is to update prev = 0 when encountering an empty row, which resets the chain and causes incorrect beam counts. Only update prev when curr > 0.

Multiplying Beams Between Non-Adjacent Rows

The problem states beams form between adjacent rows containing devices. This means if rows 0 and 2 have devices but row 1 is empty, beams still form between rows 0 and 2. The key insight is that "adjacent" refers to consecutive non-empty rows, not consecutive row indices.

Off-by-One Errors with Row Iteration

When iterating from row 1 to the end, ensure prev is initialized correctly from row 0. Starting the loop at index 0 and trying to access bank[-1] or similar patterns will cause index errors or incorrect initialization.