We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Laser Beams in a Bank

Number: 2244

Difficulty: Medium

Paid? No

Companies: Meta, Amazon

Problem Description

Given a bank's floor plan represented as an array of binary strings, each string corresponds to a row where '1' indicates a security device and '0' indicates an empty cell. A laser beam is established between two devices located on two distinct non-adjacent rows provided that every row between them contains no devices. The task is to determine the total number of laser beams created across the bank.

Key Insights

  • Only rows with at least one security device are valid for forming beams.
  • Laser beams are created between consecutive valid rows.
  • The number of beams between two valid rows is the product of the number of devices on each row.
  • Rows with no devices act as barriers and do not participate in forming beams.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, since each character in every row is checked. Space Complexity: O(1), as the solution only uses a few variables beyond the input storage.

Solution

The solution works by first iterating over each row of the bank to count the number of devices. We ignore rows with zero devices because they cannot contribute to forming beams. Then, for every pair of consecutive rows (with devices), we compute the number of beams as the product of devices in the previous valid row and the current row. We keep a cumulative total of these products and return it at the end. This approach utilizes simple arithmetic and iteration through the array, ensuring an efficient solution.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        total_beams = 0  # Initialize total number of beams to 0
        previous_devices = 0  # To store device count from the last valid row
        
        # Iterate over each row in the bank
        for row in bank:
            devices = row.count('1')  # Count the number of devices ('1's) in the row
            
            # If the row has at least one device, it is a valid row
            if devices > 0:
                # If there was a previous valid row, multiply its device count with current row's count
                if previous_devices:
                    total_beams += previous_devices * devices
                # Update previous_devices to current row's device count
                previous_devices = devices
        
        return total_beams
← Back to All Questions