Problem

Example 1:

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

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])
 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
42

import java.util.*;
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);
        }
    }
}

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.