<p>Given two <code>n x n</code> binary matrices <code>mat</code> and <code>target</code>, return <code>true</code><em> if it is possible to make </em><code>mat</code><em> equal to </em><code>target</code><em> by <strong>rotating</strong> </em><code>mat</code><em> in <strong>90-degree increments</strong>, or </em><code>false</code><em> otherwise.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/20/grid3.png" style="width: 301px; height: 121px;" />
<pre>
<strong>Input:</strong> mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
<strong>Output:</strong> true
<strong>Explanation: </strong>We can rotate mat 90 degrees clockwise to make mat equal target.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/20/grid4.png" style="width: 301px; height: 121px;" />
<pre>
<strong>Input:</strong> mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to make mat equal to target by rotating mat.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/26/grid4.png" style="width: 661px; height: 184px;" />
<pre>
<strong>Input:</strong> mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
<strong>Output:</strong> true
<strong>Explanation: </strong>We can rotate mat 90 degrees clockwise two times to make mat equal target.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == mat.length == target.length</code></li>
	<li><code>n == mat[i].length == target[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 10</code></li>
	<li><code>mat[i][j]</code> and <code>target[i][j]</code> are either <code>0</code> or <code>1</code>.</li>
</ul>

from typing import List

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        """
            We know the rotation rule for square matrix using 2 steps.
                1. transpose
                2. reverse each row
            Hack: if we rotate a matrix repeteadly then after 90 rotation, then again 90 rotation which is in total
            180 rotation, again 90 rotation means 270 rotation, and if we again rotate it 4rth times then we
            get back the original matrix.
            
            So, we have to basically check up to `3 times` clockwise rotation.
        """
        if mat == target: return True
        
        n = len(mat)
        deg = 3
        
        while deg:

            #s1 transpose
            for i in range(n):
                for j in range(i, n):
                    temp = mat[i][j]
                    mat[i][j] = mat[j][i]
                    mat[j][i] = temp
            #s2 reverse
            for i in range(n):
                for j in range(n//2):
                    temp = mat[i][j]
                    mat[i][j] = mat[i][n-j-1]
                    mat[i][n-j-1] = temp
                # lj, rj = 0, n-1
                # while lj <= rj: # here, we have to use 2 pointers / go to the mid index in for loop
                #     temp = mat[i][lj]
                #     mat[i][lj] = mat[i][rj]
                #     mat[i][rj] = temp
                #     lj += 1
                #     rj -= 1
            
            if mat == target: return True

            deg -= 1
        
        return False

41