Leetcode 2125: Number of Laser Beams in a Bank
You are given a 2D binary grid, where ‘1’ represents a security device and ‘0’ represents an empty cell. A laser beam can be formed between two devices if they are located on two different rows and no security device is in any row between them. The task is to find the total number of laser beams that can be formed.
Problem
Approach
Steps
Complexity
Input: You are given a grid of '1's and '0's where each string in the array represents a row in the grid.
Example: bank = ["10101", "00000", "10101"]
Constraints:
• 1 <= m, n <= 500
• Each element of bank is either '0' or '1'.
Output: Return the total number of laser beams that can be formed.
Example: Input: bank = ["10101", "00000", "10101"] Output: 4
Constraints:
• m == bank.length
• n == bank[i].length
• bank[i][j] is either '0' or '1'.
Goal: Count the number of laser beams that can be formed by finding pairs of security devices that are on different rows with no devices in between.
Steps:
• For each row in the grid, count the number of security devices.
• For each pair of rows with security devices, compute the number of beams as the product of the device counts in those rows.
Goal: The grid size can be as large as 500x500.
Steps:
• The number of rows and columns can be between 1 and 500.
• The grid consists only of '0's and '1's.
Assumptions:
• The grid may have rows or columns that are completely empty of security devices.
• Input: Input: bank = ["011001", "000000", "010100", "001000"]
• Explanation: The laser beams can be formed between devices on different rows, without any devices in between rows. The total number of beams is 8.
• Input: Input: bank = ["000", "111", "000"]
• Explanation: No beams can be formed because the devices are on the same row, and there are no devices on different rows.
Approach: To solve this problem, iterate through the grid row by row, counting the number of devices in each row. For every pair of rows with devices, compute the number of laser beams as the product of the number of devices in those rows.
Observations:
• Only rows with at least one device contribute to the beam count.
• We need to avoid counting beams between rows with no devices.
Steps:
• Initialize a variable to store the total beam count.
• Iterate through each row in the grid and count the number of devices in that row.
• For every pair of rows with devices, add the product of their device counts to the total beam count.
Empty Inputs:
• If the grid is empty or has no devices, the result will be 0.
Large Inputs:
• Ensure the solution handles grids with maximum dimensions (500x500) efficiently.
Special Values:
• If a row has no devices, it should be skipped in the computation of beam counts.
Constraints:
• The solution should be optimized to handle the grid's maximum size.
int numberOfBeams(vector<string> bank) {
int res = 0, m = bank.size(), n = bank[0].size();
int cnt = 0, prv = 0;
for (auto b : bank)
{
cnt = 0;
for(int i = 0; i < n; i++)
if (b[i] == '1') cnt++;
if(cnt > 0) {
res += prv * cnt;
prv = cnt;
}
}
return res;
}
1 : Function Definition
int numberOfBeams(vector<string> bank) {
This line defines the function 'numberOfBeams' which takes a vector of strings 'bank' as input. Each string represents a row in the bank, where '1' indicates the presence of a beam.
2 : Variable Initialization
int res = 0, m = bank.size(), n = bank[0].size();
This line initializes three variables: 'res' to store the result, 'm' to store the number of rows in the bank, and 'n' to store the number of columns (the length of the first row).
3 : Variable Initialization
int cnt = 0, prv = 0;
This line initializes 'cnt' (to count the number of '1's in the current row) and 'prv' (to store the previous row's count of '1's).
4 : Row Iteration
for (auto b : bank)
This line starts a loop that iterates over each row 'b' in the 'bank'.
5 : Row Processing
cnt = 0;
This line resets 'cnt' to 0 before counting the '1's in the current row.
6 : Column Iteration
for(int i = 0; i < n; i++)
This line starts a loop that iterates over each column 'i' in the current row.
7 : Column Processing
if (b[i] == '1') cnt++;
This line checks if the current column contains a '1' and, if so, increments the 'cnt' counter.
8 : Check for Valid Count
if(cnt > 0) {
This line checks if there are any '1's in the current row. If so, it proceeds with the calculation.
9 : Result Calculation
res += prv * cnt;
This line adds the product of the previous row's '1' count ('prv') and the current row's '1' count ('cnt') to the result ('res').
10 : Update Previous Count
prv = cnt;
This line updates 'prv' to the current row's '1' count ('cnt'), to be used in the next iteration.
11 : Return Result
return res;
This line returns the final result, which is the total number of beams calculated from all rows.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: We need to scan each row and count the devices, which takes O(n) time for each row. Thus, the time complexity is O(m * n), where m is the number of rows and n is the number of columns.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses a constant amount of extra space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus