matrices

03 Jul 2026 · Stone Liu

Spiral Matrix

Problem goes like this. We have the following matrix

1 2 3
4 5 6
7 8 9

We want to iterate over the matrix in the following fashion: . Conceptually, it means that I want to be able to go through the values of my matrix in the following order, first row, then last column, then last row, then first column, then second row, etc. So literally iterate over the matrix in this “spiral” order. What I am first thinking is lets set up two pointers, one pointer for the current row that we are in and one pointer for the current column that we are in. Let’s traverse step by step and view the iterations at each step.

--- Start
row_ptr = 0, col_ptr = 0, order = []
1 2 3
4 5 6
7 8 9
--- 1st Iteration
row_ptr = 0, col_ptr = 0, order = [1]
x 2 3
4 5 6
7 8 9
--- 2nd Iteration
row_ptr = 0, col_ptr = 1, order = [1,2]
1 x 3
4 5 6
7 8 9
--- 3rd Iteration
row_ptr = 0, col_ptr = 2, order = [1,2,3]
1 2 x
4 5 6
7 8 9
--- 4th Iteration
# Once the col_ptr < m = 2 condition fails we start iterating on the row_ptr
row_ptr = 1, col_ptr = 2, order = [1,2,3,6]
1 2 3
4 5 x
7 8 9
--- 5th Iteration
row_ptr = 2, col_ptr = 2, order = [1,2,3,6,9]
1 2 3
4 5 6
7 8 x
--- 5th Iteration
# Same thing here, once we have row_ptr, col_ptr < n, m = 2 we start iterating backwards from col
row_ptr = 2, col_ptr = 1, order = [1,2,3,6,9,8]
1 2 3
4 5 6
7 x 9
--- 6th Iteration
row_ptr = 2, col_ptr = 0, order = [1,2,3,6,9,8,7]
1 2 3
4 5 6
x 8 9
--- 7th Iteration
# When col_ptr = 0 we want to move back up again
row_ptr = 1, col_ptr = 0, order = [1,2,3,6,9,8,7,4]
1 2 3
x 5 6
7 8 9
--- 7th Iteration
# We already visited row_ptr = 0 and col_ptr = 0 which means we start iterating on the col_ptr now. (Flipping as we go)
row_ptr = 1, col_ptr = 1, order = [1,2,3,6,9,8,7,4,5]
1 2 3
4 x 6
7 8 9

Okay nice, so just walking through this one example uncovered a few edge cases. For one, we don’t want to go back to positions we have already done before. So maybe keeping a hashset of lookups for positions might be useful. One full spiral iteration involves things:

  1. Go right as much as you can.
  2. Go down as much as you can.
  3. Go left as much as you can.
  4. Go up as much as you can.
  5. Repeat.

How to know when to stop? There are probably alot of cases but we can stop when our final output array matches the length of where are the rows and columns or dimensions of our matrix. We want the hashset for lookups since it becomes especially prevalent on larger and larger matricies such as:

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

We will have to run our spiral loop to completion twice to obtain all the elements.

The working solution below keeps track of the upper, lower, left, and right bounds. Shrinking them at every single iteration.

class Solution {
  public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
      int m = matrix.size();
      int n = matrix[0].size();
      vector<int> order = {};
      int upper = 0;
      int lower = m - 1;
      int right = n - 1;
      int left = 0;

      while (order.size() < m * n) {
        // Go right as much as you can
        for (int i = left; i <= right && order.size() < m * n; i++) {
          order.push_back(matrix.at(upper).at(i));
        }
        upper += 1;

        // Go down as much as you can
        for (int i = upper; i <= lower && order.size() < m * n; i++) {
          order.push_back(matrix.at(i).at(right));
        }
        right -= 1;

        // Go left as much as you can
        for (int i = right; i >= left && order.size() < m * n; i--) {
          order.push_back(matrix.at(lower).at(i));
        }
        lower -= 1;

        // Go up as much as you can
        for (int i = lower; i >= upper && order.size() < m * n; i--) {
          order.push_back(matrix.at(i).at(left));
        }

        left += 1;
      }

      return order;
    };
};

Update · July 5th 2026

Continuing with the matrix problems…

Shortest Path in Binary Matrix

Problem goes like this:

  1. We are given an matrix with binary entries. We want to return the length of the shortest clear path in the matrix.

  2. A Clear Path must satisfy

    • It must go from the top left corner to the bottom right corner .

    • All the visited cells are .

    • Adjacent cells are directionally connected.

Okay so the first thing that we can check is that if the top left corner or the bottom right corner are either 1s we can immediately return since clearly there is no clear path.

Is this DP (Dynamic Programming)? I feel like I could solve this with a dimensional dynamic programming approach. As in, I can compute the shortest clear path from to each entry in my matrix. Take for example the following

The left side matrix represents the actual matrix and the right side represents my 2-dimensional dynamic programming table. The update rule should be as follows (in a nut-shell):

What is ? Really since we can move in possible directions that just means we can just diagonally. We never really want to backtrack on our answer since that would mean that we would add an additional step which is never optimal. Meaning the previous optimal jump that we were at. So if we follow the DP algorithm as follows we can get:

Our base case for our matrix will be that the top left corner must be since that counts as a single path in our matrix.

Okay after working through a few more examples and admittingly coding up the wrong solution, the dynamic programming approach will not work here. Which leads me to believe that we should just simply build a graph from our matrix and then run dijkstra’s from the top left to the bottom right cells. For reference here is my wrong solution

class Solution {
public:
  int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> dp(n, vector<int>(n,numeric_limits<int>::max() / 2));
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) {
      return - 1;
    }
    dp[0][0] = 1; // base case
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] != 0 || (i == 0 && j == 0)) {
          continue; // skip if its a 1 since there is clearly no clear path here.
        }
        if (i - 1 >= 0) {
          // Check top
          dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j]);
        }
        if (j - 1 >= 0) {
          // Check left
          dp[i][j] = min(dp[i][j], 1 + dp[i][j - 1]);
        }
        if (i - 1 >= 0 && j - 1 >= 0) {
          // Check left diagonal
          dp[i][j] = min(dp[i][j], 1 + dp[i-1][j-1]);
        }
      }
    }
    if (dp[n-1][n-1] == numeric_limits<int>::max() / 2) {
      return -1;
    } else {
      return dp[n-1][n-1];
    }
  }
};

A better solution would be to build a graph and perform a breadth first search since all the edge weights are equal. We will use level order traversal of the graph to get this done. Every time we finish a level we will increase our distance by .

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
  unordered_map<long long, vector<pair<int,int>>> graph = this->buildGraph(grid);
  // We can just run a bfs since we all the edge weights are going to be 1.
  queue<pair<int,int>> grid_queue;
  int n = grid.size();
  grid_queue.push({0,0}); // Push the root node in our graph
  unordered_set<long long> visited;
  int dist = 1;
  if (grid[0][0] == 1 || grid[n - 1][n -1] == 1) {
    return -1;
  }

  while (grid_queue.size() > 0) {
    queue<pair<int,int>> level;
    int level_size = grid_queue.size();
    for (int i = 0; i < level_size; i ++) {
      pair<int,int> curr = grid_queue.front();
      grid_queue.pop();
      if (visited.find(key(curr.first, curr.second)) != visited.end()) {
        continue;
      }
      visited.insert(key(curr.first, curr.second));
      if (curr.first == n - 1 && curr.second == n - 1) {
        return dist;
      }
      const auto &neighbors = graph[key(curr.first, curr.second)];
      for (const auto& neighbor: neighbors) {
        if (visited.find(key(neighbor.first, neighbor.second)) != visited.end()) {
          continue;
        }
        grid_queue.push(neighbor);
      }
    }
    dist += 1;
  }
  return -1;
}

Update · July 7th 2026

Rotate Image

Problem goes like this:

We have a square image represented as a dimensional matrix. We want to rotate the image clockwise. The twist comes in the fact that we have to rotate the image in-place. So lets step through some examples:

When we rotate the image clockwise, i’m going to literally pick up my computer screen and turn it clockwise. That means that the row vector becomes a column vector . And so on, and so forth for the other row vectors.

Now obviously, the reason why they don’t want us to allocate a new matrix is because this problem becomes trivially easy when that happens. We just take the transpose of each row vector and append it onto our matrix. But there is another thing that I notice here. Let’s take a look at the corners of our matrix.

It kinda seems like the corners of our matrix are swapping corners. Same with the middle pieces as well. But a matrix looks really convienient, lets try with a .

Same thing happens here! It looks like the number at . Lets look at where the rest goes. . Hmm… a little confusing now.

Maybe the pattern is, if you can see the last digit representing the column of the coordinate, that becomes the new row! But what about the row? Wait a minute, we should probably think about this as peeling an orange. We rotate the first layer then go into the second layer and so on. How many layers are there? Actually I am not too sure. But I do notice, , , . And so on. Isn’t that just half a diagonal across the square? Which means we just perform integer division and round up. So the number of layers we have is

Edit

Actually since the middle layer is always just a we can ditch the .

Essentially we want to create a function that takes a position

Edit

This isn’t right, since it does not send

Granted that we are operating on a layer by layer basis. One more thing I want to figure out is the number of rotations per layer.

Okay after looking at some of my faulty logic again, it appears that the rule is a lot more simple than I have thought. I did observe that the column dictates the row of the swap. Consider any point . Then a rotation clockwise sends where and . Essentially we are just subtracting the length of the side of the matrix (off by one) by the relative position of the current index we are rotating it against, that will determine where its target column will hit.

void rotate(vector<vector<int>>& mat) {
  int n = mat.size();
  int layers = (n / 2);

  for (int i = 0; i < layers; i++) {
    for (int j = i; j < n - 1 - i; j++) {
      int temp = mat[i][j];
      mat[i][j] = mat[n - 1 - j][(n - 1) - (n - 1 - i)];
      mat[n - 1 - j][(n - 1) - (n - 1 - i)] = mat[n - 1 - i][n - 1 - j];
      mat[n - 1 - i][n - 1 - j] = mat[j][n - 1 - i];
      mat[j][n - 1 - i] = temp;
    }
  }
}

Number of Black Boxes

Problem goes like this: We have a 2D integer matrix coordinates where the coordinates[i] = [x, y] which indicates that coordinate box is colored black everything else is white.

A block is defined to be a submatrix of the grid and we want to be able to return a indexed array such that it is the number of blocks that contains exactly black cells.

Okay so this looks to be pretty simple, we perform a matrix scan and then just log the number of black squares that appear in said matrix. This is my first approach:

vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
  unordered_set<uint64_t> coords;
  vector<long long> counts(5);

  for (vector<int> &coord : coordinates) {
    uint64_t x = (uint64_t) coord[0];
    int y = coord[1];
    coords.insert((x << 32) | y);
  }

  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < m - 1; j++) {
      int count = 0;
      uint64_t x = (uint64_t) j;
      int y = i;

      // Top left corner
      if (coords.find((x << 32) | y) != coords.end()) {
        count += 1;
      }

      // Bottom left corner
      if (coords.find((x << 32) | y + 1) != coords.end()) {
        count += 1;
      }

      // Top right corner
      if (coords.find((x + 1 << 32) | y) != coords.end()) {
        count += 1;
      }

      // bottom right corner
      if (coords.find((x + 1 << 32) | y + 1) != coords.end()) {
        count += 1;
      }

      counts[count] += 1;
    }
  }
  return counts;
}

However this would be which is pretty large. If we think about it, we can just iterate over the black coordinates and use each coordinate as a pivot and see if there are any boxes in that range. Lets take some example matrix which we have labeled “B” for black and “W” for white.

The coordinate contains squares of dimension . If we label each of the squares by their top left corners we have the list . Meaning that our output array is precisely .

Lets try another example, one with black coordinates.

We still label our squares with the top left corners . We can keep them in a hashmap. We map each left corner block to the number of black coordinates it contains.

uint64_t key(int x, int y) {
  return ((uint64_t) x << 32) | y;
}

vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) { 
  vector<long long> counts(5);
  unordered_map<uint64_t, int> blocks;

  for (vector<int> &coord : coordinates) {
    int x = coord[0];
    int y = coord[1];
    if (x - 1 >= 0 && y - 1 >= 0) {
      blocks[key(x - 1, y - 1)] += 1;
    }
    if (x - 1 >= 0 && y + 1 < n) {
      blocks[key(x - 1, y)] += 1;
    }
    if (y - 1 >= 0 && x + 1 < m) {
      blocks[key(x, y - 1)] += 1;
    }
    if (x + 1 < m && y + 1 < n) {
      blocks[key(x, y)] += 1;
    }
  }
  for (const auto& [k,v] : blocks) {
    counts[v] += 1;
  }
  // Go through each coord again and check which boxes have those within them.
  long long empty_blocks = ((long long)n - 1) * (m - 1) - (counts[1] + counts[2] + counts[3] + counts[4]);
  counts[0] = empty_blocks;
  return counts;
}