Number of Laser Beams in a Bank

Medium

Asked by:

14 views

Topics:

ArraysStrings

Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the i^th row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.

There is one laser beam between any two security devices if both conditions are met:

The two devices are located on two different rows: r₁ and r₂, where r₁ < r₂.
For each row i where r₁ < i < r₂, there are no security devices in the i^th row.

Laser beams are independent, i.e., one beam does not interfere nor join with another.

Return the total number of laser beams in the bank.

Example 1:

Input: bank = ["011001","000000","010100","001000"]
Output: 8
Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams:
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
Note that there is no beam between any device on the 0^th row with any on the 3^rd row.
This is because the 2^nd row contains security devices, which breaks the second condition.

Example 2:

Input: bank = ["000","111","000"]
Output: 0
Explanation: There does not exist two devices located on two different rows.

Constraints:

m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] is either '0' or '1'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions and maximum possible sizes of the bank represented by the input string array?
Can a row in the input string array be empty or contain characters other than '0' and '1'?
If there are no two security devices on different rows, or if there are no rows with security devices, what value should I return?
Does the order of the rows in the input matter, or only the number of security devices on each row?
Are rows with only '0's treated as empty rows, and therefore should not be counted in the calculation of beams?

Brute Force Solution

Approach

We want to figure out how many laser beams there are between rows in a bank, based on some arrangement of security devices. The basic approach is to look at every single row and compare it to every other row to see if there's a valid laser beam connection.

Here's how the algorithm would work step-by-step:

Start by looking at the very first row.
Check if it has any security devices.
Then, go through all the rows below it, one by one.
For each of those lower rows, also check if they have any security devices.
If both the first row and a lower row have security devices, see if all the rows in between are empty (no devices).
If all rows between the two considered rows have no devices, then you have one laser beam. Count it.
Repeat this process by starting with the second row, then the third row, and so on until you've checked every possible pair of rows.

Code Implementation

def number_of_laser_beams_brute_force(bank):
    total_laser_beams = 0
    number_of_rows = len(bank)

    for first_row_index in range(number_of_rows):
        # Check each row to see if it has devices.
        number_of_devices_first_row = bank[first_row_index].count('1')

        if number_of_devices_first_row > 0:
            for second_row_index in range(first_row_index + 1, number_of_rows):
                # Check if the second row also has devices
                number_of_devices_second_row = bank[second_row_index].count('1')

                if number_of_devices_second_row > 0:
                    rows_are_separated_by_empty_rows = True

                    #Verify that the rows in between are all empty
                    for intermediate_row_index in range(first_row_index + 1, second_row_index):
                        if bank[intermediate_row_index].count('1') > 0:
                            rows_are_separated_by_empty_rows = False
                            break

                    if rows_are_separated_by_empty_rows:
                        #If the rows in between are empty, increment.
                        total_laser_beams += number_of_devices_first_row * number_of_devices_second_row

    return total_laser_beams

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each row of the bank, which we can represent as 'n' rows. For each row, it then iterates through all the subsequent rows to check for valid laser beam connections. This nested iteration means that for each of the 'n' rows, we potentially perform operations on approximately 'n' other rows. Checking if the intermediate rows are empty also takes O(n) in the worst case, but since it is inside the nested loops it does not change the O(n²) complexity. Therefore, the total number of operations scales with n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the input array of strings to count laser beams. It primarily uses a few integer variables to keep track of row indices and counts of security devices. No auxiliary data structures like lists, hash maps, or significant recursion are employed. Therefore, the space used remains constant, irrespective of the number of rows in the input. The auxiliary space complexity is O(1).

Optimal Solution

Approach

The key idea is to focus on the rows that actually contain devices and skip the empty ones. We want to count how many device combinations exist between each pair of non-empty rows. Multiplying the number of devices in each consecutive pair of rows gives us the total number of laser beams.

Here's how the algorithm would work step-by-step:

Go through each row in the bank.
Count the number of devices in each row.
Ignore any row that has zero devices.
Keep track of the number of devices in the previous non-empty row.
For each non-empty row, multiply its device count by the device count of the previous non-empty row and add the result to the total beam count.
Update the previous non-empty row's device count with the current row's device count for the next calculation.
After checking all rows, the total beam count represents the number of laser beams in the bank.

Code Implementation

def number_of_laser_beams_in_a_bank(bank):
    total_beams = 0
    previous_devices = 0

    for row in bank:
        device_count = row.count('1')

        # Skip rows without any devices.
        if device_count == 0:
            continue

        # Calculate beams based on previous row
        if previous_devices > 0:
            total_beams += device_count * previous_devices

        # Store current row's device count
        previous_devices = device_count

    return total_beams

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each row of the bank, where m represents the number of rows. Inside the loop, it counts the number of devices in each row, which takes O(n) time, where n is the number of columns (or the length of each row). Since we iterate through all rows, the total time complexity is proportional to m * n. The skipping of empty rows doesn't change the overall complexity because in the worst case we have to go through all rows.

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. Specifically, it uses a variable to store the device count of the previous non-empty row and another variable to accumulate the total beam count. These variables occupy a fixed amount of memory, irrespective of the number of rows in the input bank (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty bank array	Return 0 if the input bank array is null or empty.
Bank array contains only empty rows (all zeros)	The algorithm should correctly handle all zero rows, skipping them in the calculation without causing errors.
Bank array contains only one row	Return 0 since laser beams need at least two rows.
Very large bank array dimensions (potential integer overflow)	Use a data type that can accommodate large numbers of beams to avoid integer overflow, such as long.
Rows with a very large number of devices (1s), close to the maximum integer limit	Ensure the counting mechanism for devices in a row doesn't cause integer overflow; use long if necessary.
The input bank array consists of rows that alternate between having zero and non-zero devices.	The algorithm should still correctly compute beams between these sparse layers.
Input array contains non-binary digits other than '0' or '1'	Filter out non-binary digits or throw an error to indicate invalid input.
Extremely long rows with all 1s	Efficiently count 1s in the row to avoid performance bottlenecks.

Null or empty bank array

How to Handle:

Return 0 if the input bank array is null or empty.

Bank array contains only empty rows (all zeros)

How to Handle:

The algorithm should correctly handle all zero rows, skipping them in the calculation without causing errors.

Bank array contains only one row

How to Handle:

Return 0 since laser beams need at least two rows.

Very large bank array dimensions (potential integer overflow)

How to Handle:

Use a data type that can accommodate large numbers of beams to avoid integer overflow, such as long.

Rows with a very large number of devices (1s), close to the maximum integer limit

How to Handle:

Ensure the counting mechanism for devices in a row doesn't cause integer overflow; use long if necessary.

The input bank array consists of rows that alternate between having zero and non-zero devices.

How to Handle:

The algorithm should still correctly compute beams between these sparse layers.

Input array contains non-binary digits other than '0' or '1'

How to Handle:

Filter out non-binary digits or throw an error to indicate invalid input.

Extremely long rows with all 1s

How to Handle:

Efficiently count 1s in the row to avoid performance bottlenecks.