Facebook Pixel

3391. Design a 3D Binary Matrix with Efficient Layer Tracking 🔒

MediumDesignArrayHash TableMatrixOrdered SetHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an n x n x n binary 3D array matrix. Your task is to implement the Matrix3D class that supports the following operations:

  • Matrix3D(int n): Initializes the 3D binary array matrix with all elements 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 index x.

Intuition

The problem revolves around efficiently managing a 3D binary matrix while performing updates and queries. The key challenge is to keep track of the number of 1's in each layer (2D slice) of the 3D matrix to quickly determine which layer has the most 1's and, in case of ties, the layer with the largest index.

To address this, we use the following data structures:

  1. A 3D list g to represent the binary matrix, where g[x][y][z] denotes the value at that position.
  2. A list cnt, where cnt[x] records the number of 1's in the x-th 2D layer (matrix[x]).
  3. An ordered collection sl, which efficiently keeps track of pairs (cnt[x], x) to allow quick retrieval of the layer with the maximum number of 1's.

The method setCell(x, y, z) checks if the cell is already set to 1 to avoid redundant updates. If not, it sets the cell to 1, updates cnt[x], and manages the ordered collection sl to keep track of changes.

Similarly, unsetCell(x, y, z) checks if the cell is already 0 to skip unnecessary operations. If it needs to be unset, the appropriate updates to cnt[x] and sl are made.

Finally, largestMatrix() retrieves the layer with the most 1's by leveraging the structure of sl, which dynamically maintains order by the count of 1's and, when equal, by the largest layer index.

By organizing our updates and queries this way, we achieve efficient operations for managing and querying the matrix.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution employs a combination of a 3D array, a counting array, and an ordered collection to efficiently manage and query the matrix. Here's how each component operates:

  1. 3D Array g:
    We use a three-dimensional list g of size n x n x n initialized to zero to represent the matrix. This array allows us to manipulate individual cells within the matrix using indices x, y, and z.

  2. Counting Array cnt:
    A one-dimensional list cnt is used, where cnt[x] holds the count of 1's in the layer x of the matrix. This array is crucial for quickly calculating the number of 1's per 2D slice and helps facilitate efficient updates and queries.

  3. Ordered Collection sl:
    We utilize an ordered collection, sl, to maintain pairs (cnt[x], x). This structure allows easy retrieval of the layer with the highest number of 1's, sorted first by the count and then by the index in case of ties. This helps achieve an efficient largestMatrix() function.

Algorithm Details:

  • Initialization (__init__):
    The 3D list g is initialized to zero, cnt is initialized to track the number of 1's in each layer, and sl is sorted in descending order of 1's count and layer index.

  • Setting a Cell (setCell):

    1. Check if g[x][y][z] is already 1 to skip redundant operations.
    2. If not, update g[x][y][z] to 1.
    3. Update the count: remove (cnt[x], x) from sl, increment cnt[x], and re-add (cnt[x], x) to maintain order.

  • Unsetting a Cell (unsetCell):

    1. Confirm if g[x][y][z] is already 0 to avoid unnecessary alterations.
    2. If it's set, change g[x][y][z] to 0.
    3. Adjust the count: remove (cnt[x], x) from sl, decrement cnt[x], and re-add (cnt[x], x) only if cnt[x] remains positive.

  • Finding Largest Matrix (largestMatrix):
    Access the topmost element of sl to get the layer index with the maximum number of 1's. If sl is empty, return the default last layer n - 1, which acts as a safe fallback.

This structured approach ensures that set and unset operations, as well as queries for the largest matrix, are handled in a manner that balances memory usage and processing time effectively.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a 3x3x3 matrix and operations performed on it. We will walk through initializing the matrix, setting and unsetting cells, and finding the layer with the most 1's.

Step-by-Step Operations:

  1. Initialization: Matrix3D(3)

    • Create a 3D binary matrix g of size 3x3x3, all initialized to 0: 
      g = [
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
]
    • Initialize cnt array to track the number of 1's in each layer: 
      cnt = [0, 0, 0]
    • Use an ordered collection sl to keep pairs (cnt[x], x): 
      sl = [(0, 0), (0, 1), (0, 2)]

  2. Operation: setCell(0, 0, 0)

    • Check if g[0][0][0] is already 1 (it's not), so set it to 1.
    • Update g: 
      g = [
  [[1, 0, 0], [0, 0, 0], [0, 0, 0]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
]
    • Update cnt[0] from 0 to 1.
    • Modify sl, remove (0, 0), and add (1, 0): 
      sl = [(1, 0), (0, 1), (0, 2)]

  3. Operation: setCell(1, 2, 2)

    • Check if g[1][2][2] is already 1 (it's not), so set it to 1.
    • Update g: 
      g = [
  [[1, 0, 0], [0, 0, 0], [0, 0, 0]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 1]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
]
    • Update cnt[1] from 0 to 1.
    • Modify sl, remove (0, 1), and add (1, 1): 
      sl = [(1, 0), (1, 1), (0, 2)]

  4. Operation: unsetCell(0, 0, 0)

    • Confirm g[0][0][0] is 1, so change it to 0.
    • Update g: 
      g = [
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 1]],
  [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
]
    • Update cnt[0] from 1 to 0.
    • Modify sl, remove (1, 0) and add (0, 0): 
      sl = [(1, 1), (0, 0), (0, 2)]

  5. Operation: largestMatrix()

    • Retrieve the topmost element of sl, which is (1, 1), thus returning layer index 1 as it has the maximum number of 1's.

This method ensures efficient querying and updating, maintaining the matrix's integrity and functionality, while prioritizing quick access and manipulation of data.

Solution Implementation

1from sortedcontainers import SortedList
2
3class Matrix3D:
4    def __init__(self, n: int):
5        # Initializing a 3D matrix of dimensions n x n x n with all elements set to 0
6        self.g = [[[0] * n for _ in range(n)] for _ in range(n)]
7        # Array to count the number of 1s in each x-layer of the 3D matrix
8        self.cnt = [0] * n
9        # Sorted list to keep track of layers sorted by count, with a key to prioritize by descending count
10        self.sl = SortedList(key=lambda x: (-x[0], -x[1]))
11
12    def setCell(self, x: int, y: int, z: int) -> None:
13        # Check if the cell is already set to 1
14        if self.g[x][y][z]:
15            return
16        # Set the cell to 1
17        self.g[x][y][z] = 1
18        # Remove the previous count of x from sorted list, if it exists
19        self.sl.discard((self.cnt[x], x))
20        # Increment the count of set cells in layer x
21        self.cnt[x] += 1
22        # Add the updated count back to the sorted list
23        self.sl.add((self.cnt[x], x))
24
25    def unsetCell(self, x: int, y: int, z: int) -> None:
26        # If the cell is already unset, return
27        if self.g[x][y][z] == 0:
28            return
29        # Set the cell to 0
30        self.g[x][y][z] = 0
31        # Remove the previous count of x from sorted list
32        self.sl.discard((self.cnt[x], x))
33        # Decrement the count of set cells in layer x
34        self.cnt[x] -= 1
35        # If count is not zero, add it back to the sorted list
36        if self.cnt[x]:
37            self.sl.add((self.cnt[x], x))
38
39    def largestMatrix(self) -> int:
40        # Return the index of the x-layer with the maximum number of set cells; n-1 if all layers are empty
41        return self.sl[0][1] if self.sl else len(self.g) - 1
42
43# Your Matrix3D object will be instantiated and called as such:
44# obj = Matrix3D(n)
45# obj.setCell(x,y,z)
46# obj.unsetCell(x,y,z)
47# param_3 = obj.largestMatrix()
48
1import java.util.TreeSet;
2
3class Matrix3D {
4    private final int[][][] g; // 3D matrix representing the grid
5    private final int[] cnt; // Array to count the number of '1's in each 2D plane
6    private final TreeSet<int[]> sl = new TreeSet<>((a, b) -> 
7        a[0] == b[0] ? b[1] - a[1] : b[0] - a[0]
8    ); // TreeSet to track planes by their count of '1's
9
10    public Matrix3D(int n) {
11        g = new int[n][n][n]; // Initialize a n x n x n 3D matrix
12        cnt = new int[n]; // Initialize the count array with length n
13    }
14
15    // Sets the cell (x, y, z) to 1
16    public void setCell(int x, int y, int z) {
17        if (g[x][y][z] == 1) {
18            return; // If the cell is already set, do nothing
19        }
20        g[x][y][z] = 1; // Set the cell to 1
21        sl.remove(new int[] {cnt[x], x}); // Remove the old count of '1's for plane x
22        cnt[x]++; // Increment the count of '1's for plane x
23        sl.add(new int[] {cnt[x], x}); // Add the updated count back to the TreeSet
24    }
25
26    // Unsets the cell (x, y, z) to 0
27    public void unsetCell(int x, int y, int z) {
28        if (g[x][y][z] == 0) {
29            return; // If the cell is already unset, do nothing
30        }
31        g[x][y][z] = 0; // Unset the cell to 0
32        sl.remove(new int[] {cnt[x], x}); // Remove the old count of '1's for plane x
33        cnt[x]--; // Decrement the count of '1's for plane x
34        if (cnt[x] > 0) {
35            sl.add(new int[] {cnt[x], x}); // Add the updated count back to the TreeSet if greater than zero
36        }
37    }
38
39    // Returns the index of the 2D plane with the largest number of 1s
40    public int largestMatrix() {
41        return sl.isEmpty() ? g.length - 1 : sl.first()[1]; // If TreeSet is empty, return last index, otherwise return the smallest index with max '1's
42    }
43}
44
45/**
46 * Your Matrix3D object will be instantiated and called as such:
47 * Matrix3D obj = new Matrix3D(n);
48 * obj.setCell(x,y,z);
49 * obj.unsetCell(x,y,z);
50 * int param_3 = obj.largestMatrix();
51 */
52
1#include <vector>
2#include <set>
3
4using namespace std;
5
6class Matrix3D {
7private:
8    // 3D matrix representation
9    vector<vector<vector<int>>> grid;
10    // Count of 1s in each x-plane
11    vector<int> count;
12    // Set to maintain sorted pairs of (-count[x], -x) for quick retrieval of largest matrix
13    set<pair<int, int>> sortedLayers;
14
15public:
16    // Constructor to initialize the 3D matrix and count. 'n' defines the dimension.
17    Matrix3D(int n) {
18        // Initialize a 3D vector (n x n x n) with all elements set to 0
19        grid.resize(n, vector<vector<int>>(n, vector<int>(n, 0)));
20        // Initialize count vector to keep track of the number of 1s in each x-plane
21        count.resize(n, 0);
22    }
23
24    // Set the cell (x, y, z) to 1 if it isn't already set
25    void setCell(int x, int y, int z) {
26        // If the cell is already set, do nothing
27        if (grid[x][y][z] == 1) {
28            return;
29        }
30        // Set the cell (x, y, z) to 1
31        grid[x][y][z] = 1;
32      
33        // Remove the old count entry for this x-plane
34        sortedLayers.erase({-count[x], -x});
35      
36        // Increment the count of 1s for this x-plane
37        count[x]++;
38      
39        // Insert the updated count entry
40        sortedLayers.insert({-count[x], -x});
41    }
42
43    // Unset the cell (x, y, z) to 0 if it isn't already unset
44    void unsetCell(int x, int y, int z) {
45        // If the cell is already unset, do nothing
46        if (grid[x][y][z] == 0) {
47            return;
48        }
49        // Unset the cell (x, y, z)
50        grid[x][y][z] = 0;
51      
52        // Remove the old count entry for this x-plane
53        sortedLayers.erase({-count[x], -x});
54      
55        // Decrement the count of 1s for this x-plane
56        count[x]--;
57      
58        // Insert the updated count entry only if there are any 1s left in this x-plane
59        if (count[x] > 0) {
60            sortedLayers.insert({-count[x], -x});
61        }
62    }
63
64    // Retrieve the index of the x-plane with the largest number of 1s
65    int largestMatrix() {
66        // If there are no planes with any 1s, return the highest valid x index, n-1
67        // Otherwise, return the index of the x-plane with the largest count of 1s
68        return sortedLayers.empty() ? grid.size() - 1 : -sortedLayers.begin()->second;
69    }
70};
71
72/**
73 * Your Matrix3D object can be instantiated and used as follows:
74 * Matrix3D* obj = new Matrix3D(n);
75 * obj->setCell(x, y, z);
76 * obj->unsetCell(x, y, z);
77 * int param_3 = obj->largestMatrix();
78 */
79
1// 3D matrix representation
2let grid: number[][][] = [];
3// Count of 1s in each x-plane
4let count: number[] = [];
5// Set to maintain sorted pairs of (-count[x], -x) for quick retrieval of largest matrix
6let sortedLayers: Set<[number, number]> = new Set();
7
8// Initialize the 3D matrix and count. 'n' defines the dimension.
9function initializeMatrix3D(n: number): void {
10    // Initialize a 3D array (n x n x n) with all elements set to 0
11    grid = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(n).fill(0)));
12    // Initialize count array to keep track of the number of 1s in each x-plane
13    count = Array(n).fill(0);
14    // Reset the sortedLayers set
15    sortedLayers = new Set();
16}
17
18// Set the cell (x, y, z) to 1 if it isn't already set
19function setCell(x: number, y: number, z: number): void {
20    // If the cell is already set, do nothing
21    if (grid[x][y][z] === 1) {
22        return;
23    }
24    // Set the cell (x, y, z) to 1
25    grid[x][y][z] = 1;
26
27    // Remove the old count entry for this x-plane
28    sortedLayers.delete([-count[x], -x]);
29
30    // Increment the count of 1s for this x-plane
31    count[x]++;
32
33    // Insert the updated count entry
34    sortedLayers.add([-count[x], -x]);
35}
36
37// Unset the cell (x, y, z) to 0 if it isn't already unset
38function unsetCell(x: number, y: number, z: number): void {
39    // If the cell is already unset, do nothing
40    if (grid[x][y][z] === 0) {
41        return;
42    }
43    // Unset the cell (x, y, z)
44    grid[x][y][z] = 0;
45
46    // Remove the old count entry for this x-plane
47    sortedLayers.delete([-count[x], -x]);
48
49    // Decrement the count of 1s for this x-plane
50    count[x]--;
51
52    // Insert the updated count entry only if there are any 1s left in this x-plane
53    if (count[x] > 0) {
54        sortedLayers.add([-count[x], -x]);
55    }
56}
57
58// Retrieve the index of the x-plane with the largest number of 1s
59function largestMatrix(): number {
60    // If there are no planes with any 1s, return the highest valid x index, n-1
61    // Otherwise, return the index of the x-plane with the largest count of 1s
62    return sortedLayers.size === 0 ? grid.length - 1 : -Array.from(sortedLayers)[0][1];
63}
64

Time and Space Complexity

The time complexity of the setCell and unsetCell methods is O(log n), which comes from the operations on the SortedList. The largestMatrix method has a time complexity of O(1) as it directly accesses the first element of the sorted list. As for space complexity, the structure holds a 3D list and additional lists, yielding a space complexity of O(n^3).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the relationship between a tree and a graph?

Recommended Readings

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More