Author: Aayush Agarwal
Tester: Aayush Agarwal
Editorialist: Aakash Jain
Form an NxN matrix following the given snaking pattern starting at the bottom left (example for 4x4):
7 13 14 16 6 8 12 15 2 5 9 11 1 3 4 10
Report the value at (X, Y).
Divide the matrix along the principal diagonal. First fill the bottom half along the diagonals, changing the limits appropriately for each diagonal. Use a flag variable to indicate the direction in which the diagonal is to be filled, and flip it after each diagonal. Repeat the process for the upper half of the matrix.
We can divide the problem into two loops, each filling one half of the NxN matrix. We divide a 4x4 matrix as follows:
x o o o x x o o x x x o x x x x
The halves will be filled diagonally. We will be needing the following variables for our task:
- A counter that tells us the value to be stored at each place in the matrix.
- A flag variable that we flip after filling each diagonal. Its value tells us the direction in which to fill the current diagonal.
- The top and bottom row numbers for the current diagonal.
- The leftmost and rightmost column numbers for the current diagonal.
First we will fill the lower half, starting at the bottom right. For this, we initialize our variables as follows:
value = 1 direction = 1 rowTop = rowBottom = N-1 colLeft = colRight = 0
For each successive diagonal, you will find that we have to decrement
rowTop and increment
colRight. We also have to flip
direction (this can be done by XORing it with 1). To fill each diagonal, we check the value of
direction. If it is 1, we fill the diagonal from bottom to top (equivalently, right to left). If it is 0, we fill from top to bottom (equivalently, left to right).
while rowTop >= 0 if direction == 0 i = rowTop j = colLeft while i <= rowBottom matrix[i][j] = value++ i++ j++ else i = rowBottom j = colRight while i >= rowTop matrix[i][j] = value++ i-- j-- rowTop-- colRight++ direction ^= 1
We have now filled the lower half of the matrix. Next, we will be starting with the lowest diagonal of the top half and moving to the top right. This is similar to what we did for the lower half, with some changes. Pseudo-code:
rowTop = 0 rowBottom = N-2 colLeft = 1 colRight = N-1 while rowBottom >= 0 if direction == 0 i = rowTop j = colLeft while i <= rowBottom matrix[i][j] = value++ i++ j++ else i = rowBottom j = colRight while i >= rowTop matrix[i][j] = value++ i-- j-- rowBottom-- colLeft++ direction ^= 1
We have now filled the matrix and simply have to return
matrix[X][Y]. Optionally, we could return our value as soon as the value at
matrix[X][Y] is filled, instead of filling the entire matrix first.
Author’s solution can be found here.