Solution Explanation for Number of Laser Beams in a Bank

This problem asks us to count the number of laser beams formed between security devices in a bank represented by a binary string array. A laser beam exists between two devices if they are on different rows, and no other devices are present in the rows between them.

Approach: Iterative Counting

The most efficient approach is to iterate through the rows of the bank and count the number of security devices (1s) in each row. We maintain a variable pre to store the count from the previous row. For each row with security devices:

1. Calculate the current count: Count the number of 1s in the current row (cur).
2. Calculate beam contribution: If cur is greater than 0 (meaning there are devices in the current row), multiply cur by pre (the number of devices in the previous row). This gives us the number of beams formed between the current and previous row. Add this to the total beam count (ans).
3. Update pre: Update pre with cur for the next iteration.

This approach avoids nested loops, resulting in a significantly faster solution than checking all pairs of devices.

Time and Space Complexity Analysis

• Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns in the input array. This is because we iterate through each row and count the 1s in each row. The counting operation within each row takes at most O(n) time.

• Space Complexity: O(1). We only use a few integer variables to store the counts and the total number of beams, which uses constant extra space regardless of the input size.

Code Implementation in Multiple Languages

The code implementations below showcase this approach in several popular programming languages. Note that slight variations may exist due to language-specific features, but the core logic remains the same.

Python3

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        ans = pre = 0
        for row in bank:
            cur = row.count('1')  # Efficiently counts '1's in a row
            if cur:
                ans += pre * cur
                pre = cur
        return ans
 

Java

class Solution {
    public int numberOfBeams(String[] bank) {
        int ans = 0, pre = 0;
        for (String row : bank) {
            int cur = 0;
            for (char c : row.toCharArray()) {
                if (c == '1') cur++;
            }
            if (cur > 0) {
                ans += pre * cur;
                pre = cur;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int ans = 0, pre = 0;
        for (const string& row : bank) {
            int cur = count(row.begin(), row.end(), '1'); // Efficient count using STL algorithm
            if (cur > 0) {
                ans += pre * cur;
                pre = cur;
            }
        }
        return ans;
    }
};

JavaScript

/**
 * @param {string[]} bank
 * @return {number}
 */
var numberOfBeams = function(bank) {
    let ans = 0;
    let pre = 0;
    for (let row of bank) {
        let cur = row.split("").filter(x => x === "1").length;
        if (cur > 0) {
            ans += pre * cur;
            pre = cur;
        }
    }
    return ans;
};

Go

func numberOfBeams(bank []string) int {
	ans, pre := 0, 0
	for _, row := range bank {
		cur := strings.Count(row, "1")
		if cur > 0 {
			ans += pre * cur
			pre = cur
		}
	}
	return ans
}

These code snippets demonstrate the efficient iterative approach to solving the problem, ensuring both accuracy and optimal performance. Remember that the choice of language may slightly affect the exact syntax, but the underlying algorithm remains consistent for all implementations.