Problem

You are given a n x n x 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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Input:
["Matrix3D", "setCell", "largestMatrix", "setCell", "largestMatrix", "setCell", "largestMatrix"]
[[3], [0, 0, 0], [], [1, 1, 2], [], [0, 0, 1], []]

Output:
[null, null, 0, null, 1, null, 0]

Explanation

Matrix3D matrix3D = new Matrix3D(3); // Initializes a 3 x 3 x 3 3D array matrix, filled with all 0's.
matrix3D.setCell(0, 0, 0); // Sets matrix[0][0][0] to 1.
matrix3D.largestMatrix(); // Returns 0. matrix[0] has the most number of 1's.
matrix3D.setCell(1, 1, 2); // Sets matrix[1][1][2] to 1.
matrix3D.largestMatrix(); // Returns 1. matrix[0] and matrix[1] tie with the most number of 1's, but index 1 is bigger.
matrix3D.setCell(0, 0, 1); // Sets matrix[0][0][1] to 1.
matrix3D.largestMatrix(); // Returns 0. matrix[0] has the most number of 1's.

Solution

Method 1 – Hash Set and 3D Array for Efficient Layer Tracking

Intuition

To efficiently support set, unset, and query operations in a 3D binary matrix, we can use a 3D array for the matrix and maintain a set for each layer to track which cells are set. This allows for fast updates and queries for each layer.

Approach

  1. Use a 3D array (or a dictionary of sets) to represent the matrix.
  2. For each layer, maintain a set of (row, col) pairs that are set to 1.
  3. set(x, y, z): Set the cell (x, y, z) to 1 and add (x, y) to the set for layer z.
  4. unset(x, y, z): Set the cell (x, y, z) to 0 and remove (x, y) from the set for layer z.
  5. isSet(x, y, z): Return True if (x, y) is in the set for layer z.
  6. getLayer(z): Return a list of all (x, y) pairs set in layer z.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class BinaryMatrix3D {
    private int n, m, l;
    private Set<Pair<Integer, Integer>>[] layers;
    public BinaryMatrix3D(int n, int m, int l) {
        this.n = n; this.m = m; this.l = l;
        layers = new HashSet[l];
        for (int i = 0; i < l; i++) layers[i] = new HashSet<>();
    }
    public void set(int x, int y, int z) {
        layers[z].add(new Pair<>(x, y));
    }
    public void unset(int x, int y, int z) {
        layers[z].remove(new Pair<>(x, y));
    }
    public boolean isSet(int x, int y, int z) {
        return layers[z].contains(new Pair<>(x, y));
    }
    public List<int[]> getLayer(int z) {
        List<int[]> ans = new ArrayList<>();
        for (Pair<Integer, Integer> p : layers[z]) {
            ans.add(new int[]{p.getKey(), p.getValue()});
        }
        return ans;
    }
    private static class Pair<K, V> {
        private final K key;
        private final V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return Objects.equals(key, pair.key) && Objects.equals(value, pair.value);
        }
        @Override public int hashCode() {
            return Objects.hash(key, value);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class BinaryMatrix3D:
    def __init__(self, n: int, m: int, l: int):
        self.n = n
        self.m = m
        self.l = l
        self.layers = [set() for _ in range(l)]
    def set(self, x: int, y: int, z: int) -> None:
        self.layers[z].add((x, y))
    def unset(self, x: int, y: int, z: int) -> None:
        self.layers[z].discard((x, y))
    def isSet(self, x: int, y: int, z: int) -> bool:
        return (x, y) in self.layers[z]
    def getLayer(self, z: int) -> list[tuple[int, int]]:
        return list(self.layers[z])

Complexity

  • ⏰ Time complexity: O(1) for set, unset, isSet; O(k) for getLayer, where k is the number of set cells in the layer.
  • 🧺 Space complexity: O(n * m * l) in the worst case, if all cells are set.