Rotate Image - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Rotate Image" Problem in Go

Difficulty: Medium | Tags: Array, Math, Matrix

Introduction

The "Rotate Image" problem requires rotating an n x n 2D matrix by 90 degrees clockwise in-place. This is a common problem that tests understanding of matrix manipulations and in-place algorithms.

Problem Analysis

Given an n x n matrix, rotating it 90 degrees clockwise involves transforming the matrix such that the first column becomes the last row in reverse order. For example, rotating [[1,2,3],[4,5,6],[7,8,9]] results in [[7,4,1],[8,5,2],[9,6,3]]. The challenge is to achieve this without allocating additional memory for another matrix.

Solution Approach

The solution involves two main steps: transposing the matrix and then reversing each row. Transposing swaps elements across the diagonal, and reversing each row completes the 90-degree rotation. This approach ensures the rotation is done in-place with O(1) space complexity.

Go Implementation


func rotate(matrix [][]int) {
    n := len(matrix)
    // Transpose the matrix
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    // Reverse each row
    for i := 0; i < n; i++ {
        for j := 0; j < n/2; j++ {
            matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
        }
    }
}

Complexity Analysis

The time complexity is O(n²) because we process each element of the matrix twice (once for transposing and once for reversing rows). The space complexity is O(1) since no additional data structures are used.

Testing and Examples

Test cases include:
1. Input: [[1,2,3],[4,5,6],[7,8,9]] → Output: [[7,4,1],[8,5,2],[9,6,3]]
2. Input: [[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]]
Edge cases include a 1x1 matrix (no change) and a 2x2 matrix (simple swap).

Best Practices and Tips

Key takeaways include understanding matrix transposition and row reversal as building blocks for rotation. Always verify edge cases, and ensure in-place modifications to meet problem constraints. Practice similar matrix problems to build intuition for spatial transformations.

Read more