How do you solve Number of Laser Beams in a Bank on LeetCode?

Number of Laser Beams in a Bank (LeetCode #2125) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Laser beams can only exist between rows that have security devices, with no devices in between.

What is the brute force solution for Number of Laser Beams in a Bank?

The brute force approach for Number of Laser Beams in a Bank is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of rows to count the laser beams. It does this by iterating through each pair of rows and counting the devices in those rows while ensuring there are no devices in the rows in between. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Laser Beams in a Bank?

Number of Laser Beams in a Bank uses the following concepts: Array, Math, String, Matrix. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Number of Laser Beams in a Bank?

Always clarify the problem constraints and edge cases before diving into coding. Think about how to optimize your solution after writing the brute force version. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Number of Laser Beams in a Bank?

Not checking for rows in between that contain devices, leading to incorrect beam counts. Overcomplicating the problem by trying to store all pairs instead of just counting.

#2125

Number of Laser Beams in a Bank

Medium

ArrayMathStringMatrixHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach counts the number of devices in each row and only considers rows with devices. It uses a single pass to calculate the total beams by keeping track of the last row with devices and the count of devices in the current row.

⚙️

Algorithm

4 steps

1Step 1: Initialize a variable to count the total beams and a variable to store the count of devices in the last row with devices.
2Step 2: Loop through each row of the bank and count the devices in the current row.
3Step 3: If the current row has devices, multiply the count of devices in the last row with devices by the count in the current row and add to total beams.
4Step 4: Update the last row device count to the current row's device count.

solution.py9 lines

1def numberOfBeams(bank):
2    total_beams = 0
3    last_count = 0
4    for row in bank:
5        current_count = row.count('1')
6        if current_count > 0:
7            total_beams += last_count * current_count
8            last_count = current_count
9    return total_beams

ℹ

Complexity note: The time complexity is O(n) because we only loop through the rows once, counting devices in each. The space complexity is O(1) since we only use a few variables for counting.

1Laser beams can only exist between rows that have security devices, with no devices in between.
2The number of beams between two rows is the product of the number of devices in each row.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.