Coding Challenge: Interview - > Rotate Image

 You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

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:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

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

 

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Solutions:

fun rotate(matrix: Array<IntArray>) {
    val n = matrix.size
    
    // Transpose the matrix
    for (i in 0 until n) {
        for (j in i until n) {
            val temp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = temp
        }
    }
    
    // Reverse each row
    for (i in 0 until n) {
        var left = 0
        var right = n - 1
        while (left < right) {
            val temp = matrix[i][left]
            matrix[i][left] = matrix[i][right]
            matrix[i][right] = temp
            left++
            right--
        }
    }
}


Here is the more details of each details

Certainly! Let's break down the solution step by step:

  1. Transpose the matrix:

    • To transpose the matrix means to swap its rows and columns. We iterate over the upper triangle of the matrix (i.e., i from 0 to n-1, j from i to n-1) and swap each element with its corresponding element across the diagonal.
    • For example, if we have a matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]], transposing it will give us [[1, 4, 7], [2, 5, 8], [3, 6, 9]].
  2. Reverse each row:

    • After transposing the matrix, we iterate over each row, and for each row, we reverse its elements.
    • This reversal effectively rotates each row by 180 degrees.
    • For example, if we have a transposed matrix [[1, 4, 7], [2, 5, 8], [3, 6, 9]], reversing each row will give us [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

By performing these two operations, we achieve the desired result of rotating the matrix by 90 degrees clockwise. The key insight is that transposing the matrix swaps rows and columns, effectively rotating it by 90 degrees counterclockwise. Then, reversing each row completes the rotation to 90 degrees clockwise. This solution modifies the input matrix in-place without using any extra space.


Happy Coding ✌!

0 comments:

Post a Comment