🔗 Rotating Matrix Borders

There is a matrix of size rows x columns. The matrix has the numbers 1 through rows x columns written in it, one row at a time in order. In this matrix, you want to select rectangular ranges multiple times and rotate the numbers along the border clockwise. Each rotation is represented by 4 integers (x1, y1, x2, y2), meaning the following.

• Rotate the numbers on the border of the rectangle from row x1, column y1 to row x2, column y2 by one cell clockwise.

Below is an example of a 6 x 6 matrix.

If you apply a (2, 2, 5, 4) rotation to this matrix, the border of the area from row 2, column 2 to row 5, column 4 rotates clockwise as shown below. Note that the region containing 15 and 21 in the center does not rotate.

Given the vertical length (number of rows) rows, the horizontal length (number of columns) columns of the matrix, and a list of rotations queries, complete the solution function to apply each rotation to the array and return the smallest of the numbers whose positions changed from each rotation, in order, as an array.

• rows is a natural number between 2 and 100, inclusive.
• columns is a natural number between 2 and 100, inclusive.
• Initially, the numbers in the matrix increase by one horizontally, starting from 1.
  • That is, before any rotation, the number at row i, column j is ((i-1) x columns + j).
• The number of rows in queries (the number of rotations) is between 1 and 10,000, inclusive.
• Each row of queries consists of 4 integers [x1, y1, x2, y2].
  • This means rotating the border of the area from row x1, column y1 to row x2, column y2 clockwise.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns.
  • All rotations are performed in order.
  • For example, the answer for the second rotation should be computed by finding the minimum among the numbers moved when performing the second rotation on the state resulting after the first rotation has been executed.

Input/Output Example #1

The rotation process is shown in the diagram below.

Input/Output Example #2

The rotation process is shown in the diagram below.

Input/Output Example #3

In this example, every cell on the border of the matrix moves. Therefore, the smallest number on the matrix border, 1, is exactly the answer.

You need to write the matrix border rotation algorithm carefully.

Since it's a rectangular rotation, the rotation algorithm needs to be built with a for loop for each side. Fortunately, the rotation direction is fixed as clockwise.

To rotate the data correctly, you need to proceed in the direction opposite to the rotation direction, so that the data is fully preserved while rotating.

Rotate the data in the order left -> bottom -> right -> top. The method is as follows.

• minPos: $(x_{min}, y_{min})$
• maxPos: $(x_{max}, y_{max})$

1. Left rotation

Perform the left rotation.

JAVA
for (int j = minPos[0]; j < maxPos[0]; j++)
{
	board[j][minPos[1]] = board[j + 1][minPos[1]];
}

Proceed in the order (2, 2), (3, 2), (4, 2).

The y-coordinate stays the same at $y_{min}$, while only the x-coordinate changes.

As we proceed, assign each cell's value below it (relative to the diagram) to itself.

The value 8 at the smallest coordinate (2, 2) is saved separately.

2. Bottom rotation

Perform the bottom rotation.

JAVA
for (int j = minPos[1]; j < maxPos[1]; j++)
{
	board[maxPos[0]][j] = board[maxPos[0]][j + 1];
}

Proceed in the order (5, 2), (5, 3).

The x-coordinate stays the same at $x_{max}$, while only the y-coordinate changes.

As we proceed, assign each cell's value to its right (relative to the diagram) to itself.

3. Right rotation

JAVA
for (int j = maxPos[0]; j > minPos[0]; j--)
{
	board[j][maxPos[1]] = board[j - 1][maxPos[1]];
}

Proceed in the order (5, 4), (4, 4), (3, 4).

The y-coordinate stays the same at $y_{max}$, while only the x-coordinate changes.

As we proceed, assign each cell's value above it (relative to the diagram) to itself.

4. Top rotation

JAVA
for (int j = maxPos[1]; j > minPos[1]; j--)
{
	board[minPos[0]][j] = board[minPos[0]][j - 1];
}

Proceed in the order (2, 4), (2, 3).

The x-coordinate stays the same at $x_{min}$, while only the y-coordinate changes.

As we proceed, assign each cell's value to its left (relative to the diagram) to itself.

After this rotation, the data at (2, 3) gets lost, so at this point we assign the minimum coordinate value we saved separately during the left rotation.

In other words, we save $(x_{min}, y_{min})$ separately, and then assign it to $(x_{min}, y_{min} + 1)$.

The key is implementing the algorithm to proceed in the direction opposite to the rotation, assigning each cell the value in front of it (relative to the direction of travel) to itself.

If there were multiple rotation directions, you'd need to build a separate algorithm for each direction, but since this problem fixes the direction as clockwise, there's no need to worry about that.

Since every element is accessed during the rotation process, you can compare values for each element and separately store the minimum value.

JAVA
/**
 * Intact Rectangle class
 *
 * @author RWB
 * @since 2021.12.28 Tue 22:51:28
 */
class Solution
{
	/**
	 * Answer return method
	 *
	 * @param rows: [int] Columns
	 * @param columns: [int] Rows
	 * @param queries: [int[][]] Rotation targets
	 *
	 * @return [int] Answer
	 */
	public int[] solution(int rows, int columns, int[][] queries)
	{
		int[] answer = new int[queries.length];
		
		int[][] board = new int[rows][columns];
		
		for (int i = 0; i < rows; i++)
		{
			for (int j = 0; j < columns; j++)
			{
				board[i][j] = i * columns + j + 1;
			}
		}
		
		for (int i = 0; i < queries.length; i++)
		{
			int[] minPos = { queries[i][0] - 1, queries[i][1] - 1 };
			int[] maxPos = { queries[i][2] - 1, queries[i][3] - 1 };
			
			int start = board[minPos[0]][minPos[1]];
			
			int min = Integer.MAX_VALUE;
			
			// Rotate left line
			for (int j = minPos[0]; j < maxPos[0]; j++)
			{
				min = Math.min(min, board[j][minPos[1]]);
				
				board[j][minPos[1]] = board[j + 1][minPos[1]];
			}
			
			// Rotate bottom line
			for (int j = minPos[1]; j < maxPos[1]; j++)
			{
				min = Math.min(min, board[maxPos[0]][j]);
				
				board[maxPos[0]][j] = board[maxPos[0]][j + 1];
			}
			
			// Rotate right line
			for (int j = maxPos[0]; j > minPos[0]; j--)
			{
				min = Math.min(min, board[j][maxPos[1]]);
				
				board[j][maxPos[1]] = board[j - 1][maxPos[1]];
			}
			
			// Rotate top line
			for (int j = maxPos[1]; j > minPos[1]; j--)
			{
				min = Math.min(min, board[minPos[0]][j]);
				
				board[minPos[0]][j] = board[minPos[0]][j - 1];
			}
			
			board[minPos[0]][minPos[1] + 1] = start;
			
			answer[i] = min;
		}
		
		return answer;
	}
}