Solving a HackerRank algorithm problem – Matrix Layer Rotation

Matrix Layer Rotation

I enjoy solving interesting HackerRank algorithm problems.  I came across one recently called Matrix Layer Rotation – appropriately labeled “hard” by the author.

I posted my solution as a playground on GitHub.

The problem is to print out a rotated representation of a m x n  matrix given the parameters:

m – number of rows
n – number of columns
r – number of rotations

Looking at the constraints

2 <= m, n <= 300
1 <= r <= 10^^9
min(m,n) % 2 = 0

I always like to take a close look at the constraints first when solving a problem such as this.   Doing so helps to guide me to the proper structure of a solution.

When I first started attempting some medium difficulty problems, I would sometimes run into timeouts – the HackerRank site limits the time allowed for an implementation to complete.   Accounting for constraints upfront can help to avoid this issue.

2 <= m, n <= 300

This constraint indicates that the matrix can be as large as 300 x 300 or 90,000 integers.   Since this is a fairly large structure, I’d like to minimize or eliminate any copying of the structure.

1 <= r <= 10^^9

A billion rotations is a strong hint that I should try to map this into a smaller number of rotations.

min(m,n) % 2 = 0

Why is this constraint here?   If the number of rows and columns are both odd, there will not be a center “chain” of numbers to rotate.

Breaking the problem into pieces

A difficult problem like this should be broken down into manageable pieces.   After studying this for a while, I came up with the following concepts:

Chains

Instead of attempting to rotate the entire matrix at once, I viewed the matrix as a series of nested “chains”.  Each chain has an associated chain length.  In a 4 x 4 matrix there would be two chains of length 12 and 4.

I index the chains starting at 0 for the outermost chain and increment as I move inward.   Determining the chain index for a given row and column is a simple operation:

 let nearestVertEdgeDist = min(col, numCols - col - 1)
 let nearestHorizEdgeDist = min(row, numRows - row - 1)
            
 let chainIndex = min(nearestVertEdgeDist, nearestHorizEdgeDist)

 

Element lookup

The problem stated that the output was to be printed to the console, not returned in a structure.  I decided to loop through all rows and columns, and for each element calculate which associated element along its chain would represent the new value of the element.  Using a lookup function avoids any additional storage usage.

To implement the lookup function I walk clockwise around the chain, decrementing the distance I need to cover and adjusting the coordinates of the temporary marker I am pushing around.   Once I’ve covered the necessary distance, I return the value of the matrix element at the marker.

Rotations

To get the number of rotations down to something reasonable, I recognized that rotating a chain r times was the same as rotating it r % chainLength, where chainLength is the length of the chain.

Cache

For each element, I need to determine the length of its associated chain and the distance of that chain from the outer edge of the matrix (the distance would be zero for the outermost chain).  This information allows me to perform the associated element lookup as I virtually rotate the chain in a function.

To avoid unnecessary calculations I cache this length and distance information using the chain index as a key.

First attempt

Once I had done some initial testing of my solution in a Swift playground, I submitted my code.

I had many test cases passing, but several others were failing.  Spending some HackerRank “Hackos”  on their site got me the input and expected data for the failing cases.

The test case input can be downloaded as a set of space separated numbers, where each row ends with a newline.   The first line provides the number of rows, columns and rotations.

To process this input, I added some code to my playground.  An example using a 4 x 4 matrix:

 
// To test any failing Test cases, replace the contains of variable data with test case input.
let data = """
4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
"""

let lines = data.split(separator: "\n")
var arr:[[Int]] = []

let testCaseInfo = lines[0].split(separator: " ") // [rows, cols, rotations]

for i in 1..<lines.count { 
    let row = lines[i].split(separator: " ")
    let rowInt = row.map({ (s) -> Int in
        Int(s)!
    })
    arr.append(rowInt)
}

matrixRotation(matrix: arr, r: Int(testCaseInfo[2])!)

 

I was able to spot the problem fairly quickly.  In my element lookup function, I move a marker around the four edges of the chain.  I do this with a for loop that operates in the range 0..<4    I return from the for loop once I’ve covered the needed distance for the rotation.    If I haven’t covered the distance after 4 loop iterations,  I assert and return.

The issue was that I could be starting in the middle of a chain edge (and not necessarily a corner) and thus might need to process 5 edges (i.e. the initial edge twice).   My for loop range needs to be 0..<5

Success

After fixing my only bug, I was able to pass all the test cases.

I just love seeing that banner!

I concluded by reading the discussions on the problem.   My idea for the solution appeared to be generally in line with what others submitted.   There may be some room for improvement in my solution, but I was happy to get it done.

https://github.com/scottcarter/HackerRank

 

Getting closer to my gold badge!

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s