Number of Laser Beams in a Bank - Problem

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: r1 and r2, where r1 < r2.
For each row i where r1 < i < r2, 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.

Input & Output

Example 1 — Basic Bank Layout

$ Input: bank = ["011001","000000","010100","001000"]

› Output: 8

💡 Note: Row 0 has 3 devices, Row 2 has 2 devices, Row 3 has 1 device. Beams: 3×2=6 (Row 0 to Row 2), 2×1=2 (Row 2 to Row 3). Total: 6+2=8

Example 2 — Single Row

$ Input: bank = ["000","111","000"]

› Output: 0

💡 Note: Only one row has devices. No laser beams possible since beams require two different rows with devices.

Example 3 — Adjacent Active Rows

$ Input: bank = ["11","11"]

› Output: 4

💡 Note: Row 0 has 2 devices, Row 1 has 2 devices. Total beams: 2×2=4 between the adjacent rows.

Constraints

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

Visualization

Tap to expand

Asked in

a Amazon 15 M Microsoft 8

The key insight is that laser beams only form between consecutive non-empty rows. Count devices per row, then multiply counts of adjacent active rows. Optimal approach uses single pass counting with O(mn) time and O(m) space.

Common Approaches

✓ Brute Force - Check All Device Pairs

⏱️ Time: O(m²n²) Space: O(mn)

For each device in the bank, check if it can form a laser beam with every other device in a different row by ensuring no devices exist in between rows.

Count Devices Per Row

⏱️ Time: O(mn) Space: O(m)

First pass counts devices per row. Second pass finds consecutive non-empty rows and multiplies their device counts to get total laser beams between them.

Brute Force - Check All Device Pairs — Algorithm Steps

Find all device positions
Check each pair for valid laser beam
Count all valid beams

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Devices

Locate all security devices in the bank

Check Pairs

For each device pair, verify if laser beam is possible

Count Beams

Sum all valid laser beams

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char** bank, int bankSize) {
    int devices[1000];
    int deviceCount = 0;
    
    // Find all device positions
    for (int i = 0; i < bankSize; i++) {
        for (int j = 0; j < strlen(bank[i]); j++) {
            if (bank[i][j] == '1') {
                devices[deviceCount++] = i;
            }
        }
    }
    
    int totalBeams = 0;
    // Check each pair of devices
    for (int i = 0; i < deviceCount; i++) {
        for (int j = i + 1; j < deviceCount; j++) {
            int row1 = devices[i], row2 = devices[j];
            if (row1 != row2) {
                // Check if rows between are empty
                int valid = 1;
                for (int k = row1 + 1; k < row2; k++) {
                    if (strchr(bank[k], '1') != NULL) {
                        valid = 0;
                        break;
                    }
                }
                if (valid) {
                    totalBeams++;
                }
            }
        }
    }
    
    return totalBeams;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array of strings
    char* bank[100];
    int bankSize = 0;
    
    char* token = strtok(line, "[\"]");
    while (token != NULL && bankSize < 100) {
        if (strlen(token) > 0 && token[0] != ',' && token[0] != ' ') {
            bank[bankSize] = malloc(strlen(token) + 1);
            strcpy(bank[bankSize], token);
            bankSize++;
        }
        token = strtok(NULL, "[\"]");
    }
    
    int result = solution(bank, bankSize);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < bankSize; i++) {
        free(bank[i]);
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each device position, check against all other devices with row validation

⚠ Quadratic Growth

Space Complexity

O(mn)

Store all device positions in worst case

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Laser Beams in a Bank - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Device Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler