1
\$\begingroup\$

This code is a mix of the same question one time rotating to the right and one time to the left. I tried to simplify the code since I'm struggling with all of the indexing here.

https://leetcode.com/problems/rotate-image/

https://www.geeksforgeeks.org/rotate-matrix-90-degree-without-using-extra-space-set-2/

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ],

rotate the input matrix in-place such that it becomes: [ [7,4,1],
[8,5,2], [9,6,3] ] Example 2:

Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ],

rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]

Please review this code as I am trying to simplify it in order to be able to have a good short solution for a coding interview. I can't memorize this logic of course I just want to have a solid simple solution in mind.

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    /// https://www.geeksforgeeks.org/inplace-rotate-square-matrix-by-90-degrees/
    /// </summary>
    [TestClass]
    public class RotateMatrix90
    {
        [TestMethod]
        public void RotateClockWise2x2Test()
        {
            int[][] mat =
            {
                new[]{0,1},
                new[]{2,3},
            };
            int[][] expected =
            {
                new[]{2,0},
                new[]{3,1}
            };
            RotateClockWise(mat);
            int size = mat.GetLength(0);
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    Assert.AreEqual(expected[r][c], mat[r][c]);
                }
            }
        }


        [TestMethod]
        public void RotateClockWise3x3Test()
        {
            int[][] mat =
            {
                new[]{1, 2, 3},
                new[]{4, 5, 6},
                new[]{7, 8, 9}
            };
            //tranpose then flip horizotally
            //1,4,7
            //2,5,8
            //3,6,9
            int[][] expected =
            {
                new[]{7, 4, 1},
                new[]{8, 5, 2},
                new[]{9, 6, 3}
            };
            RotateClockWise(mat);
            int size = mat.Length;
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    Assert.AreEqual(expected[r][c], mat[r][c]);
                }
            }
        }
        [TestMethod]
        public void RotateCounterClockWise2x2Test()
        {
            int[][] mat =
            {
                new[]{0,1},
                new[]{2,3},
            };

            //0,2
            //1 3
            int[][] expected =
            {
                new[]{1,3},
                new[]{0,2}
            };
            RotateCounterClockWise(mat);
            int size = mat.GetLength(0);
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    Assert.AreEqual(expected[r][c], mat[r][c]);
                }
            }
        }

        [TestMethod]
        public void RotateCounterClockWise3x3Test()
        {
            int[][] mat =
            {
                new[]{1, 2, 3},
                new[]{4, 5, 6},
                new[]{7, 8, 9}
            };
            //tranpose then flip horizotally
            //1,4,7
            //2,5,8
            //3,6,9
            int[][] expected =
            {
                new[]{3, 6, 9},
                new[]{2, 5, 8},
                new[]{1, 4, 7}
            };
            RotateCounterClockWise(mat);
            int size = mat.Length;
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    Assert.AreEqual(expected[r][c], mat[r][c]);
                }
            }
        }
        //moving elements clockwise (90 degrees to the right)
        public void RotateClockWise(int[][] matrix)
        {
            Transpose(matrix);
            ReverseRows(matrix);
        }
        //moving elements counter clockwise
        public void RotateCounterClockWise(int[][] matrix)
        {
            Transpose(matrix);
            ReverseCols(matrix);
        }
        private void Transpose(int[][] matrix)
        {
            int size = matrix.Length;
            for (int i = 0; i < size; i++)
            {
                for (int j = i; j < size; j++)
                {
                    Swap(ref matrix[i][j], ref matrix[j][i]);
                }
            }
        }

        private void ReverseRows(int[][] matrix)
        {
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0, k = matrix.Length - 1; j < k; j++, k--)
                {
                    Swap(ref matrix[i][j], ref matrix[i][k]);
                }
            }
        }
        private void ReverseCols(int[][] matrix)
        {
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0, k = matrix.Length - 1; j < k; j++, k--)
                {
                    Swap(ref matrix[k][i], ref matrix[j][i]);
                }
            }
        }

        void Swap(ref int i, ref int j)
        {
            int temp = i;
            i = j;
            j = temp;
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You are mixing your code in with the unit tests. I suggest to make seperate classes for tests and code. \$\endgroup\$ – dfhwze Jun 16 at 11:45
  • 1
    \$\begingroup\$ I had to visit the link to find the spec of nxn. You could make our task helping you easier if you include crucial information in the question :) \$\endgroup\$ – dfhwze Jun 16 at 12:19
  • 1
    \$\begingroup\$ You have solved this one time before, just for a normal array - with a O(n^2) complexity. You can easily change that solution for a jagged array and to handle clock wise rotation. \$\endgroup\$ – Henrik Hansen Jun 16 at 13:30
  • 1
    \$\begingroup\$ @henrik I hate this solution. The indexing there is too complex. \$\endgroup\$ – Gilad Jun 16 at 18:52
1
\$\begingroup\$

Performance

Time complexity for your algorithm is \$O(N²+N²/2)\$. If you find a way to combine Transpose \$O(N²)\$ and ReverseCols \$O(N²/2)\$ in a single run, you could get \$O(N²)\$ in worst case.

Edit: given Henrik's good eye, you have already come up with a solution before that adheres to the optimized complexity. So, apply it here.

\$\endgroup\$

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.