Hadron DaVinci

Rotate Array 270 Degrees

23 Jan 2021 - Hadron DaVinci

Problem

Given an array, rotate it 270 degrees.

Example

given

A = [
     [1, 2, 3],
     [4, 5, 6]
    ]

rot270(A)

produces the following:

[
    [3, 6],
    [2, 5],
    [1, 4]
]

Steps

Observations

1. Rotating 270 degrees is the same as rotating forward 90 degrees three times (or backwards 90 degree once)
   • This is useful since we can express rot270(A) in terms of rot90(A)
     
     
2. The transpose(A) is the same as rot90(A) but with the rows reversed

Implications

1. There is a relationship between rot90(A) and A
   • this can probably be described by some mapping function

Methods

Method 1

Method 1 Summary
This approach is based on Observation 2.

• Create Method of rotating array 90 degrees
  1. Determine the transpose of arr
  2. Reverse each row in transpose
  3. Return result

• Rotate 90 three times

Complexity
TC: N
SC: N

Method 1 Solution

def rot90(arr: list) -> list:
    transpose = zip(*arr)
    transpose_with_reversed_rows = [
        row[::-1] for row in transpose
    ]
    return transpose_with_reversed_rows

# Try Code
if __name__ == "__main__":
    A = [
        [1, 2, 3],
        [4, 5, 6],
    ]

    for _ in range(3):
        A = rot90(A)

    print(A)

Method 2

Method 2 Summary
This approach is based on Implication1.
The relationship between rot90(A) and A can be described by the following:

Given

• let j represent the row index in rot90(A)
• let i represent the column index in rot90(A)
• let r represent the row count in the A
• let c represent the column count in the A
• let rj = r - 1
  • this is the largest row index possible in A

Then

• A_rotated90[j][i] = A[rj - i][j]
  • for 0 < j < c
  • for 0 < i < r

Exact Steps

• Create Method of rotating array 90 degrees
  1. Double loop through columns and rows in A
  2. Populate rotated array with relationship:
     A_rotated90[j][i] = A[rj - i][j]
  3. Return result

• Rotate 90 three times

Complexity
TC: N
SC: N

Method 2 Solution

def rot90(arr: list):
    r = len(arr)
    c = len(arr[0])
    rj = r - 1
    output = [[0] * r for _ in range(c)]

    for j in range(c):
        for i in range(r):
            output[j][i] = arr[rj - i][j]
    return output

# Try Code
if __name__ == "__main__":
    A = [
        [1, 2, 3],
        [4, 5, 6],
    ]

    for _ in range(3):
        A = rot90(A)

    print(A)

Files

method1.py
method2.py