The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

Given a matrix of 2D array of n rows and m columns, print this matrix in ZIG-ZAG fashion as shown in the following figure:

Example 1: 
Input: mat[][] = {{1, 2, 3}
                  {4, 5, 6}
                  {7, 8, 9}}

Output : 1, 2, 4, 7, 5, 3, 6, 8, 9

Example 2: 
Input: mat[][] = {{1,  2,  3,  4,  5}, 
                  {6,  7,  8,  9,  10},
                  {11, 12, 13, 14, 15},
                  {16, 17, 18, 19, 20}};

Output : 1, 2, 6, 11, 7, 3, 4, 8, 12, 16, 17, 13, 9, 5, 10, 14, 18, 19, 15, 20

Solution in O(n x m) Time

The algorithm is as follows:

- Visit the top-left element first. Visit the next element on the right.
- Continue visiting the current minor diagonal elements in the left-downwards direction until meeting the left edge or bottom edge of the matrix.
- If the left edge of the matrix is met and not the bottom edge, visit the next element below.
- Continue visiting the current minor diagonal elements in the right-upwards direction until meeting the top edge or right edge of the matrix.
- If the bottom edge of the matrix was met, and not the left edge, then visit the next element on the right at the bottom edge.
- Continue visiting the current minor diagonal elements in the right-upwards direction until meeting the top edge or right edge of the matrix.
- If the top edge of the matrix is met and not the right edge, visit the next element on the right.
- Continue visiting the current minor diagonal elements in the left-downwards direction until meeting the left edge or bottom edge of the matrix.
- If the right edge of the matrix was met, and not the top edge, then visit the next element below.
- Continue visiting the current minor diagonal elements in the left-downwards direction until meeting the left edge or bottom edge of the matrix.
- Continue repeating the above steps accordingly, until the element at the bottom-right corner of the matrix is met, which will always be met, either from the left or from above.
- Do not forget to consider the cases, where the visit is at the four corners.

There are eight cases to consider: when the visit is at the four corners and when the visit is at the four edges. The case of what happens after the visit of the bottom-right element, does not have to be addressed. This gives rise to seven code segments in a major while-loop.

Indexes

The top most row of the matrix is identified by i=0.
The leftmost column of the matrix is identified by j=0.
The bottommost row of the matrix is identified by i=n-1.
The rightmost column of the matrix is identified by j=m-1.

The program

The program is (read through the code and comments):

zigZagMatrix <- function(mat) {
  # Determine dimensions automatically
  n <- nrow(mat)
  m <- ncol(mat)
  
  i <- 0
  j <- 0
  
  while (i < n && j < m) {
    if (i == 0 && j == 0) { # top-left corner
      cat(mat[i + 1, j + 1], ", ", sep = "")
      j <- j + 1 # go right once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (j > 0 && i < n - 1) { # end at left or bottom edge
        i <- i + 1
        j <- j - 1 # go down and left
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
    }
    
    if (j == 0 && i > 0 && i < n - 1) { # left edge and not top or bottom ends
      i <- i + 1 # go down once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (i > 0 && j < m - 1) { # end at top or right edge
        i <- i - 1
        j <- j + 1 # go right and up
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
    }
    
    if (i == 0 && j > 0 && j < m - 1) { # top edge and not left or right ends
      j <- j + 1 # go right once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (j > 0 && i < n - 1) { # end at left or bottom edge
        i <- i + 1
        j <- j - 1 # go down and left
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
    }
    
    if (i == n - 1 && j == 0) { # left-bottom corner
      j <- j + 1 # go right once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (i > 0 && j < m - 1) { # end at top or right edge
        i <- i - 1
        j <- j + 1 # go right and up
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
    }
    
    if (i == 0 && j == m - 1) { # top-right corner
      i <- i + 1 # go down once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (j > 0 && i < n - 1) { # end at left or bottom edge
        i <- i + 1
        j <- j - 1 # go down and left
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
    }
    
    if (i > 0 && i < n - 1 && j == m - 1) { # right edge and not top or bottom ends
      i <- i + 1 # go down once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (j > 0 && i < n - 1) { # end at left or bottom edge
        i <- i + 1
        j <- j - 1 # go down and left
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
      # bottom-right end of matrix
      if (i == n - 1 && j == m - 1) {
        i <- i + 1
        j <- j + 1 # increase i and j to stop the big while-loop
      }
    }
    
    if (j > 0 && j < m - 1 && i == n - 1) { # bottom edge and not left or right ends
      j <- j + 1 # go right once
      cat(mat[i + 1, j + 1], ", ", sep = "")
      while (i > 0 && j < m - 1) { # end at top or right edge
        i <- i - 1
        j <- j + 1 # go right and up
        cat(mat[i + 1, j + 1], ", ", sep = "")
      }
      # bottom-right end of matrix
      if (i == n - 1 && j == m - 1) {
        i <- i + 1
        j <- j + 1 # increase i and j to stop the big while-loop
      }
    }
  }
  cat("\n")
}

# Main area execution
# mat <- matrix(c(1, 2, 3, 
#                 4, 5, 6, 
#                 7, 8, 9), nrow = 3, byrow = TRUE)

# zigZagMatrix(mat)

# mat2 = matrix(c(1,  2,  3,  4,  5, 
#                 6,  7,  8,  9,  10,
#                 11, 12, 13, 14, 15,
#                 16, 17, 18, 19, 20), nrow = 4, ncol = 5, byrow = TRUE)
      
# zigZagMatrix(mat2);

Remove the first pair of the block comment markers (/* */). Make the first argument of the called function, "int mat[][3]". Run the program and the output should be:

    1, 2, 4, 7, 5, 3, 6, 8, 9, 

Put back the first pair of the block comment markers (/* */). Remove the second pair of the block comment markers (/* */). Make the first argument of the called function, "int mat[][5]". Run the program and the output should be:

1, 2, 6, 11, 7, 3, 4, 8, 12, 16, 17, 13, 9, 5, 10, 14, 18, 19, 15, 20,

The time complexity is actually O(2 n x m), with the first O(n x m) for populating the input matrix with all the elements, and the second O(n x m) for iterating over all the elements in the matrix in the called function. Since the coefficient (multiplicand of 2) is usually omitted, the time complexity is quoted as O(n x m).

The space complexity is O(n x m), for the input matrix, which is the same as the matrix in the called function (same reference).

Thanks for reading.