Design a 3D Binary Matrix with Efficient Layer Tracking

Design a 3D Binary Matrix with Efficient Layer Tracking - Problem

Array Hash Table Design Heap (Priority Queue) Matrix Ordered Set Medium

You are given a n × n × n binary 3D array matrix. Implement the Matrix3D class:

Matrix3D(int n) Initializes the object with the 3D binary array matrix, where all elements are initially set to 0.

void setCell(int x, int y, int z) Sets the value at matrix[x][y][z] to 1.

void unsetCell(int x, int y, int z) Sets the value at matrix[x][y][z] to 0.

int largestMatrix() Returns the index x where matrix[x] contains the most number of 1's. If there are multiple such indices, return the largest x.

Input & Output

Example 1 — Basic Operations

$ Input: operations = [["Matrix3D", 2], ["setCell", 0, 0, 0], ["setCell", 1, 1, 1], ["largestMatrix"], ["setCell", 0, 1, 1], ["largestMatrix"]]

› Output: [null, null, null, 0, null, 0]

💡 Note: Initialize 2×2×2 matrix. Set (0,0,0) - layer 0 has 1 cell. Set (1,1,1) - layer 1 has 1 cell. Both layers tie with count 1, return larger index 1. Wait, that should return 1. Set (0,1,1) - layer 0 now has 2 cells. Layer 0 has most cells, return 0.

Example 2 — With Unset Operations

$ Input: operations = [["Matrix3D", 3], ["setCell", 1, 0, 0], ["setCell", 1, 0, 1], ["setCell", 2, 1, 1], ["largestMatrix"], ["unsetCell", 1, 0, 0], ["largestMatrix"]]

› Output: [null, null, null, null, 1, null, 2]

💡 Note: Initialize 3×3×3 matrix. Set cells in layers 1 (count=2) and 2 (count=1). Layer 1 has most, return 1. Unset one cell from layer 1 (count=1). Now layers 1 and 2 tie with count 1, return larger index 2.

Example 3 — All Layers Empty

$ Input: operations = [["Matrix3D", 2], ["largestMatrix"]]

› Output: [null, 1]

💡 Note: All layers have count 0, return the largest index which is 1 (n-1).

Constraints

1 ≤ n ≤ 100
0 ≤ x, y, z < n
At most 10⁴ calls will be made to setCell, unsetCell, and largestMatrix

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of Matrix3D operations (init, setCell, unsetCell, largestMatrix)

Process

Track layer counts and active cells for efficient queries

Output

Return results array with null for mutations and indices for queries

Key Takeaway

🎯 Key Insight: Track layer counts instead of storing the full 3D matrix for optimal space and time complexity

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to track counts per layer instead of storing the full 3D matrix. The optimal approach uses an array to count 1's in each layer plus a set to track active cells, enabling O(1) operations for set/unset and O(n) for queries. Time: O(1) per operation, Space: O(n + k) where k is active cells.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Full Matrix	O(n²)	O(n³)	Store the full 3D matrix and count 1's in each layer when needed
Layer Count Tracking	O(1)	O(n + k)	Track count of 1's per layer to avoid recounting

Brute Force with Full Matrix — Algorithm Steps

Initialize n×n×n 3D array
Set/unset cells directly in matrix
For largestMatrix: count 1's in each layer
Return layer with most 1's (largest index on ties)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create n×n×n matrix filled with zeros

Set/Unset

Direct modification of matrix cells

Query

Count all 1s in each layer to find maximum

Code -

solution.c — C

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

typedef struct {
    int n;
    int*** matrix;
} Matrix3D;

Matrix3D* createMatrix3D(int n) {
    Matrix3D* obj = (Matrix3D*)malloc(sizeof(Matrix3D));
    obj->n = n;
    obj->matrix = (int***)malloc(n * sizeof(int**));
    for (int i = 0; i < n; i++) {
        obj->matrix[i] = (int**)malloc(n * sizeof(int*));
        for (int j = 0; j < n; j++) {
            obj->matrix[i][j] = (int*)calloc(n, sizeof(int));
        }
    }
    return obj;
}

void setCell(Matrix3D* obj, int x, int y, int z) {
    obj->matrix[x][y][z] = 1;
}

void unsetCell(Matrix3D* obj, int x, int y, int z) {
    obj->matrix[x][y][z] = 0;
}

int largestMatrix(Matrix3D* obj) {
    int maxCount = -1;
    int result = 0;
    
    for (int x = 0; x < obj->n; x++) {
        int count = 0;
        for (int y = 0; y < obj->n; y++) {
            for (int z = 0; z < obj->n; z++) {
                count += obj->matrix[x][y][z];
            }
        }
        
        if (count >= maxCount) {
            maxCount = count;
            result = x;
        }
    }
    
    return result;
}

char* solution(char* operations_json) {
    cJSON *json = cJSON_Parse(operations_json);
    cJSON *results = cJSON_CreateArray();
    Matrix3D* matrix3d = NULL;
    
    int size = cJSON_GetArraySize(json);
    for (int i = 0; i < size; i++) {
        cJSON *op = cJSON_GetArrayItem(json, i);
        cJSON *method = cJSON_GetArrayItem(op, 0);
        
        if (strcmp(method->valuestring, "Matrix3D") == 0) {
            cJSON *n = cJSON_GetArrayItem(op, 1);
            matrix3d = createMatrix3D(n->valueint);
            cJSON_AddItemToArray(results, cJSON_CreateNull());
        } else if (strcmp(method->valuestring, "setCell") == 0) {
            cJSON *x = cJSON_GetArrayItem(op, 1);
            cJSON *y = cJSON_GetArrayItem(op, 2);
            cJSON *z = cJSON_GetArrayItem(op, 3);
            setCell(matrix3d, x->valueint, y->valueint, z->valueint);
            cJSON_AddItemToArray(results, cJSON_CreateNull());
        } else if (strcmp(method->valuestring, "unsetCell") == 0) {
            cJSON *x = cJSON_GetArrayItem(op, 1);
            cJSON *y = cJSON_GetArrayItem(op, 2);
            cJSON *z = cJSON_GetArrayItem(op, 3);
            unsetCell(matrix3d, x->valueint, y->valueint, z->valueint);
            cJSON_AddItemToArray(results, cJSON_CreateNull());
        } else if (strcmp(method->valuestring, "largestMatrix") == 0) {
            int result = largestMatrix(matrix3d);
            cJSON_AddItemToArray(results, cJSON_CreateNumber(result));
        }
    }
    
    char* result_string = cJSON_Print(results);
    cJSON_Delete(json);
    cJSON_Delete(results);
    return result_string;
}

int main() {
    char operations[10000];
    fgets(operations, sizeof(operations), stdin);
    operations[strcspn(operations, "\n")] = 0;
    
    char* result = solution(operations);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

largestMatrix requires counting all n² elements in each of n layers

⚠ Quadratic Growth

Space Complexity

O(n³)

Full 3D matrix storage requires n³ space

⚠ Quadratic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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 with Full Matrix — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler