Number of laser beams [Easy greedy]

XXX. Number of Laser Beams in a Bank

Array

String

Problem Statement:

Given a 2D grid bank represented as an array of binary strings, where each string represents a row of the bank and '1' indicates a security device and '0' indicates an empty space, calculate the total number of laser beams formed. A laser beam is formed when there are security devices in two different rows such that no devices are in between them.

Algorithm:

1. Initialize variables to track the count of devices in the previous row (prev) and the total number of beams (ans).
2. Iterate over each row in the bank:
• Count the number of '1's in the current row.
• If the count is greater than zero:
  • Add the product of the previous row's count and the current row's count to ans.
  • Update prev to the current count.
3. Return ans as the total number of beams.

Complexity:

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

public int numberOfBeams(String[] bank) {
    int prev = 0, ans = 0; // Initialize variables for previous count and total beams

    for (String s : bank) {
        int count = 0; // Count number of devices ('1') in the current row

        for (int i = 0; i < s.length(); i++) 
            if (s.charAt(i) == '1') count++; // Increment count for each '1'
        

        if (count > 0) { // If the row contains devices
            ans += prev * count; // Add beams formed with the previous row
            prev = count; // Update previous row's count
        }
    }

    return ans; // Return the total number of beams
}
                

Python Implementation:

def number_of_beams(bank):
    prev = 0
    ans = 0 # Initialize variables for previous count and total beams

    for row in bank:
        count = row.count('1') # Count number of devices ('1') in the current row

        if count > 0: # If the row contains devices
            ans += prev * count # Add beams formed with the previous row
            prev = count # Update previous row's count

    return ans # Return the total number of beams
                

C++ Implementation:

#include 
#include 
using namespace std;

int numberOfBeams(vector& bank) {
    int prev = 0, ans = 0; // Initialize variables for previous count and total beams

    for (const string& row : bank) {
        int count = 0; // Count number of devices ('1') in the current row

        for (char c : row) {
            if (c == '1') count++; // Increment count for each '1'
        }

        if (count > 0) { // If the row contains devices
            ans += prev * count; // Add beams formed with the previous row
            prev = count; // Update previous row's count
        }
    }

    return ans; // Return the total number of beams
}