The state of Wakanda - 1

faq

1) Why we are travelling through the columns in outer loop ?
Answer) We are travelling throught the columns first because if we analyse the problem, then it is clear that the columns are increasing countinuously, while rows are alternating.
_________________________________________________________________

2) Why we are checking if column is odd or even ?
Answer) We are doing so because, after analysing the pattern, we can figure this relation that for every even value of column, we are going downwards through rows and vice versa.
_________________________________________________________________

3) Can we do this with recursion ?
Answer) Yes, it can be done as follows :
// call function from main passing array, row as 0, column as 0. (three arguments)
// function
//  if(row > last row of array) {
      // recursive call with array, row = row - 1, col = col + 1
      // return here
//  } else if(col > last column of array) {
      // return here
//  } else if(row < first row of array (row < 0) ) {
      // recursive call with array, row = row + 1, col = col + 1
      // return here
//  }
    
//  print array element at current row, column
    
//  if(col % 2 == 0) {
      // recursive call with array, row = row + 1, col = col
//  } else {
      // recursive call with array, row = row - 1, col = col
//  }
// function ends
(can you think of any more approaches ??)
_________________________________________________________________

hints

• Try to understand the maths behind it on a paper before trying to code it.

• Take the direction towards your right as east and then think about the constraints.

• The movements are as follows -> down till last row, one move right, up till the first row, one move right.(traverse the whole array in this manner)

• Use the outer loop for traversing through the columns, and use two different loops for odd and even values of columns to traverse rows.(downwards in even columns and vice versa)

mcq

1) For what the outer loop should traverse ?
a• For the rows
b• For the columns
c• Does not matter

ans) b• For the columns

2) What is the time complexity for this solution ?
a• O(1)
b• O(n)
c• O(n^2)
d• O(log n)

ans) c• O(n^2)

3) What is the space complexity for this solution ?
a• O(1)
b• O(n^2)
c• O(n*log(n))
d• O(n)

ans) a• O(1)

4) Can this problem be solved with recursion ?
a• Yes
b• No

ans) a• Yes