Number of Laser Beams in a Bank Solution In C++/Python/java/JS
Problem Description
A bank's security system is represented as an m x n binary string array bank, where '1' denotes a security device and '0' represents an empty cell. A laser beam is formed between two devices if they are in different rows (r1 < r2) and there are no devices in any intermediate row.
Each valid pair of security devices meeting these conditions contributes to the total laser beam count. Beams function independently and do not merge. For example, in bank = ["011001", "000000", "010100", "001000"], the total beams are 8, while in bank = ["000", "111", "000"], the output is 0.
The constraints ensure 1 ≤ m, n ≤ 500, and each character is either '0' or '1'. The task is to efficiently compute the total laser beams based on these rules.
Example
Input 1: bank = ["011001", "000000", "010100", "001000"]
Output: 8
Explanation:
The first and third rows contain security devices, while the second row is empty, allowing beams to form between them. Additional beams form between the third and fourth rows, resulting in a total of 8 beams.
Input 2: bank = ["000", "111", "000"]
Output: 0
Explanation:
All security devices are in the second row, with no devices in different rows to establish a beam, leading to an output of 0.
Constraints
- m == bank.length
- n == bank[i].length
- 1 <= m, n <= 500
- bank[i][j] is either '0' or '1'.
The first thought when approaching this problem is to identify rows that contain security devices and count how many are in each row. Since laser beams only form between two non-empty rows with an empty row in between, we should track the number of devices in consecutive non-empty rows and multiply them to get the total beam count. By iterating through the bank array, skipping empty rows, and calculating beams between adjacent non-empty rows, we can efficiently determine the total number of laser beams.
Brute Force Approach
Intuition
The problem requires sorting all matrix cells based on their Manhattan distance from a given center. A straightforward way to achieve this is to first generate all possible cell coordinates in the matrix and then calculate their respective distances from (rCenter, cCenter). Since sorting is an efficient and well-optimized operation in most programming languages, we can leverage it to order the cells correctly. Given that the maximum number of cells is 10,000 (100 x 100), sorting them is feasible within the problem's constraints. This approach ensures correctness but can be further optimized using a more structured traversal method like BFS.
Approach
Instead of checking each pair of devices, we can optimize by tracking only the number of devices in each row and calculating the beams directly. The key observation is that beams are formed between consecutive non-empty rows, and the number of beams between two such rows is simply the product of their device counts. This avoids unnecessary comparisons and reduces time complexity.
We iterate through the bank array, counting the number of '1's in each row. If a row contains security devices, we store the count and calculate the beams using the count from the previous non-empty row. We then update the previous row’s count and continue. This results in an O(m × n) time complexity, which is much more efficient than the brute force approach and scales well for large inputs.
Dry Run
Input:
bank = ["011001", "000000", "010100", "001000"]
Output: 8
We will iterate through all possible pairs of security devices and check if they satisfy the conditions for forming a laser beam. A beam is valid if it connects devices in different rows and there are no security devices in between.
Identifying Security Devices:
The first step is to process the bank matrix and identify where security devices ('1') are located. We iterate through each row and record the column indices of all security devices. If a row contains only '0', it is skipped for now. After processing, the identified security device positions are as follows: Row 0 has devices at positions [1, 2, 5], Row 1 has no devices, Row 2 has devices at [1, 3], and Row 3 has a device at [2].
Checking Possible Beams:
Now, we examine every pair of security devices across different rows while ensuring there are no security devices in between. Since the second row is empty, it does not contribute to forming beams. The first and third rows contain security devices, so we check for all valid beams between them.
Valid Beams from Row 0 to Row 2:
The devices in Row 0 at [1, 2, 5] can form beams with devices in Row 2 at [1, 3]. The valid beams are as follows: (0,1) → (2,1), (0,1) → (2,3), (0,2) → (2,1), (0,2) → (2,3), (0,5) → (2,1), and (0,5) → (2,3). In total, there are 6 beams formed between these two rows.
Checking Beams Between Row 2 and Row 3:
Next, we examine the beams between Row 2 and Row 3. Row 2 has security devices at [1, 3], while Row 3 has a device at [2]. Since there are no security devices in between, valid beams can be formed: (2,1) → (3,2) and (2,3) → (3,2). This results in 2 additional beams.
Final Output: 8
We counted all valid beams by iterating through all possible device pairs and checking the conditions. The brute force approach works but is inefficient because it checks every possible combination, making it impractical for large inputs.
Code for All Languages
C++
// Number of Laser Beams in a Bank - Brute Force Approach CPP
// Function to count the number of laser beams
int countLaserBeams(vector<string>& bank) {
int m = bank.size(); // Number of rows in the bank
vector<int> rowDeviceCount; // Store the number of devices in each row
// Step 1: Count security devices ('1') in each row
for (int i = 0; i < m; i++) {
int count = 0;
for (char c : bank[i]) {
if (c == '1') count++;
}
if (count > 0) rowDeviceCount.push_back(count); // Only store non-empty rows
}
int totalBeams = 0;
// Step 2: Calculate beams between consecutive non-empty rows
for (int i = 0; i < rowDeviceCount.size() - 1; i++) {
totalBeams += rowDeviceCount[i] * rowDeviceCount[i + 1];
}
return totalBeams;
}Java
// Number of Laser Beams in a Bank - Brute Force Approach Java
// Function to count the number of laser beams
public static int countLaserBeams(String[] bank) {
int m = bank.length; // Number of rows
List<Integer> rowDeviceCount = new ArrayList<>(); // Store device counts in non-empty rows
// Step 1: Count security devices ('1') in each row
for (String row : bank) {
int count = 0;
for (char c : row.toCharArray()) {
if (c == '1') count++;
}
if (count > 0) rowDeviceCount.add(count); // Store only non-empty rows
}
int totalBeams = 0;
// Step 2: Calculate beams between consecutive non-empty rows
for (int i = 0; i < rowDeviceCount.size() - 1; i++) {
totalBeams += rowDeviceCount.get(i) * rowDeviceCount.get(i + 1);
}
return totalBeams;
}Python
# Number of Laser Beams in a Bank - Brute Force Approach Python
def count_laser_beams(bank):
row_device_count = []
# Step 1: Count the number of security devices ('1') in each row
for row in bank:
count = row.count('1')
if count > 0:
row_device_count.append(count) # Store only non-empty rows
total_beams = 0
# Step 2: Calculate beams between consecutive non-empty rows
for i in range(len(row_device_count) - 1):
total_beams += row_device_count[i] * row_device_count[i + 1]
return total_beamsJavaScript
// Number of Laser Beams in a Bank - Brute Force Approach JavaScript
// Function to count the number of laser beams
function countLaserBeams(bank) {
let rowDeviceCount = [];
// Step 1: Count the number of security devices ('1') in each row
for (let row of bank) {
let count = (row.match(/1/g) || []).length; // Count occurrences of '1'
if (count > 0) rowDeviceCount.push(count); // Store only non-empty rows
}
let totalBeams = 0;
// Step 2: Calculate beams between consecutive non-empty rows
for (let i = 0; i < rowDeviceCount.length - 1; i++) {
totalBeams += rowDeviceCount[i] * rowDeviceCount[i + 1];
}
return totalBeams;
}Time Complexity - Number of Laser Beams in a Bank - O(m × n)
The brute force approach iterates through each row to count security devices, which takes O(m × n) time in the worst case. Then, it processes the valid rows to compute beams, requiring O(m) time. Thus, the overall time complexity is O(m × n) + O(m) ≈ O(m × n).
Space Complexity - Number of Laser Beams in a Bank - O(m)
The solution stores the bank matrix (O(m)) and an auxiliary list to keep track of device counts in non-empty rows (O(m)). Apart from these, it uses a few constant variables, leading to an overall space complexity of O(m).
Bridge between Brute Force and Optimized
The brute force approach effectively identifies security devices and calculates laser beams but suffers from unnecessary row scans, leading to O(m × n) complexity. It iterates through every row to count security devices and then multiplies counts between consecutive non-empty rows. However, many rows are empty and do not contribute to beam calculations, making these extra iterations redundant. This inefficiency becomes significant for large matrices, especially when there are many empty rows.
To optimize this, we can directly track non-empty rows without iterating over empty ones. Instead of storing all rows, we maintain a running count of security devices in the last encountered non-empty row. When a new non-empty row is found, we multiply its count with the previous one and update our reference. This eliminates unnecessary row checks, reducing the time complexity from O(m × n) to O(m + n), making the approach more efficient while maintaining the same logic.
Optimized Approach
Intuition
The brute force approach scans every row, even empty ones, leading to unnecessary computations. However, the key insight is that laser beams only form between non-empty rows—rows that contain security devices. Instead of iterating through the entire matrix and processing empty rows, we can simply track consecutive non-empty rows and compute beams directly. By doing this, we avoid redundant operations and improve efficiency.
Another crucial observation is that laser beams are determined by the number of devices in two consecutive non-empty rows. Instead of checking every row for devices separately, we can maintain a running count of security devices in the previous valid row. Whenever we encounter a new non-empty row, we calculate the beams immediately and update our reference row. This allows us to reduce the number of iterations significantly, leading to a more optimized solution.
Approach
We start by iterating through the bank row by row, keeping track of the last encountered row that had security devices (prevCount). If a row is empty, we simply skip it. When we find a new non-empty row, we calculate the number of beams using the formula prevCount * currentCount, where currentCount is the number of devices in the new row. We then update prevCount to currentCount, as this new row will now act as the previous row for the next calculation.
This method ensures that we only process rows that contribute to the final beam count, skipping empty ones. Since we perform a single pass to count devices and another to compute beams, the time complexity improves from O(m × n) (brute force) to O(m + n). Additionally, we use only a few extra variables, keeping space complexity at O(1). This makes our approach much more efficient while maintaining the correctness of the solution.
Dry Run
Input:
bank = ["011001",
"000000",
"010100",
"001000"]
Output: 8
For the given input, the valid security device counts are [3, 2, 1]. The total number of laser beams formed between consecutive non-empty rows is 8.
Steps:
To begin, we first identify the number of security devices in each row by counting occurrences of '1'. If a row contains no security devices ('0' only), we skip it entirely. This ensures that we only process meaningful rows. For the given input, the first row contains 3 security devices ("011001"), the second row has 0 devices ("000000", so we skip it), the third row contains 2 devices ("010100"), and the fourth row has 1 device ("001000"). After filtering out empty rows, we are left with a list of valid security device counts: [3, 2, 1].
Now, we compute the number of laser beams between consecutive non-empty rows. We initialize prevCount with the number of devices in the first valid row, which is 3. Moving to the next non-empty row, we find 2 devices. The beams formed between these two rows are calculated as 3 × 2 = 6. We then update prevCount to 2 and move to the next non-empty row, which contains 1 device. The beams between these two rows are 2 × 1 = 2. Summing these values gives the total number of beams as 6 + 2 = 8.
Since we only considered rows that contained security devices and directly computed beams between consecutive non-empty rows, the approach avoids unnecessary iterations over empty rows. The final output for the given input is 8, which is returned as the result.
Final Output: 8
By skipping empty rows and only considering consecutive non-empty ones, we efficiently compute the laser beams. The result remains the same as the brute force approach, but we avoid unnecessary iterations, improving performance.
Cpp
// Number of Laser Beams in a Bank - Optimised Approach CPP
int countLaserBeams(vector<string>& bank) {
int totalBeams = 0;
int prevCount = 0; // Stores the count of security devices in the previous valid row
for (const string& row : bank) {
int currentCount = 0;
// Count the number of security devices ('1') in the current row
for (char cell : row) {
if (cell == '1') {
currentCount++;
}
}
// If the current row has security devices, calculate beams
if (currentCount > 0) {
totalBeams += prevCount * currentCount;
prevCount = currentCount; // Update previous row count
}
}
return totalBeams;
}Java
// Number of Laser Beams in a Bank - Optimised Approach Java
public static int countLaserBeams(List<String> bank) {
int totalBeams = 0;
int prevCount = 0; // Stores the count of security devices in the previous valid row
for (String row : bank) {
int currentCount = 0;
// Count the number of security devices ('1') in the current row
for (char cell : row.toCharArray()) {
if (cell == '1') {
currentCount++;
}
}
// If the current row has security devices, calculate beams
if (currentCount > 0) {
totalBeams += prevCount * currentCount;
prevCount = currentCount; // Update previous row count
}
}
return totalBeams;
}
Python
# Number of Laser Beams in a Bank - Optimised Approach Python
def count_laser_beams(bank):
total_beams = 0
prev_count = 0 # Stores the count of security devices in the previous valid row
for row in bank:
current_count = row.count('1') # Count the number of security devices ('1') in the current row
# If the current row has security devices, calculate beams
if current_count > 0:
total_beams += prev_count * current_count
prev_count = current_count # Update previous row count
return total_beamsJavaScript
// Number of Laser Beams in a Bank - Optimised Approach JavaScript
function countLaserBeams(bank) {
let totalBeams = 0;
let prevCount = 0; // Stores the count of security devices in the previous valid row
for (let row of bank) {
let currentCount = [...row].filter(cell => cell === '1').length; // Count '1's in the current row
// If the current row has security devices, calculate beams
if (currentCount > 0) {
totalBeams += prevCount * currentCount;
prevCount = currentCount; // Update previous row count
}
}
return totalBeams;
}
Time Complexity - Number of Laser Beams in a Bank - O (m x n)
The optimized approach iterates through each row of the bank matrix once, counting the number of '1's in each row. Since counting '1's in a row takes O(n) time (where n is the number of columns), and we iterate through m rows, the worst-case time complexity is O(m * n). However, we skip empty rows, making it more efficient in practice.
Space Complexity - Number of Laser Beams in a Bank - O (1)
The space complexity is O(1) since we only use a few integer variables (totalBeams and prevCount) to track the number of beams and the previous row's security count. We do not use extra space proportional to the input size, making it a space-efficient solution.
Similar Questions
This problem involves counting connected groups of '1's in a 2D grid, similar to how we track security devices in non-empty rows.
Requires counting servers in a grid that can communicate in the same row or column, similar to counting laser connections between security devices.