-1

Following is a java solution of the classic question of rotating a nxn matrix in place clockwise by 90 degrees.

public void rotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; ++layer) {
int first = layer;
int last = n - 1 - layer;
for(int i = first; i < last; ++i) {
int offset = i - first;
// save top
 int top = matrix[first][i];

// left -> top
 matrix[first][i] = matrix[last-offset][first];

 // bottom -> left
 matrix[last-offset][first] = matrix[last][last - offset];

 // right -> bottom
 matrix[last][last - offset] = matrix[i][last];

 // top -> right
 matrix[i][last] = top;
 }
 }
}

Below is the approach I am try to use: 1. Understand the problem statement, assumptions. 2. Break problem in smallest sub-tasks and try to write/explain the solution as plain english. 3. Write pseudo code 4. Write actual code.

I am getting stuck between #3 and #4. I have the approach and know the logic, but am having a hard time in writing a part of the solution. Let me show what:

Approach: Given this nxn matrix:

[00 01 02 03
 10 11 12 13
 20 21 22 23
 30 31 32 33]

This matrix can be rotated by rotating the the highlighted inner and outer rings (not actually circular). The outer ring has *.

[00* 01* 02* 03*
 10* 11  12  13*
 20* 21  22  23*
 30* 31* 32* 33*]

Now, to rotate the rows and columns, each element of the rows and corresponding column can be moved. For example, first take 00 in a temporary variable. Move 30 in place of 00. Move 33 in place of 30. Move 03 in place of 33 and finally assign temp to 03. Similarly, move the others.

Now, the above approach can be implemented by taking an outer counter between 0 and less than len/2. This is called as layer in the solution. Inner counter will be between layer and last. Simple!

But, I am having a hard time in coding the part in bold. i.e. writing below to work for all indexes.

// save top
// left -> top
// bottom -> left
// right -> bottom
// top -> right

i.e the things between []: Gave the question a break, but kept making mistakes in any one of these dynamic indexes. I am usually comfortable in nested/normal loops.

matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last - offset];
matrix[last][last - offset] = matrix[i][last];
matrix[i][last] = top;

I know what needs to be done but cannot write the logic of dynamic indexes. Any help on this will be appreciated. The solution is there, but this question is more of a helpful advice. What do/did you do when stuck like this?

The above answer has been explained by the author, but she also skipped to the already written program after explaining the approach.

https://www.youtube.com/watch?v=aClxtDcdpsQ

  • 1
    Here's one general suggestion. Use better variable names. What does first mean? A name along the lines of upperLeftPointX would probably be a lot clearer. – Tanner Swett Oct 9 '16 at 4:49
1

What do/did you do when stuck like this?

Use a pencil and paper and draw some pictures to help visualize the problem.

If you have an IDE with a debugger (and if not, why not?) then using the debugger to "single step" through the problem may help as well.

Ultimately, this boils down to making an accurate mental model of how the code works. That's not something that someone can teach you to do. You just have to practice doing it until you get the hang of it. Start with simpler problems / programs first, then move on to more complicated ones.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.