Number of Laser Beams in a Bank - Practice Coding Problems

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

Understanding the Visualization

Input Bank

2D grid with '1' for devices, '0' for empty cells

Find Connections

Devices connect only across consecutive non-empty rows

Count Beams

Multiply device counts between adjacent active rows

Key Takeaway

🎯 Key Insight: Laser beams connect all devices between consecutive non-empty rows - multiply device counts for total beams

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

Approach	Time	Space	Notes
✓ Brute Force - Check All Device Pairs	O(m²n²)	O(mn)	Check every possible pair of devices across different rows
Count Devices Per Row	O(mn)	O(m)	Count devices in each row, then multiply counts of consecutive non-empty rows

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Device Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler