2D array practice solutions

Complete the 2D array practice exercises before reviewing the solutions.

Review solutions to the 2D array practice exercises with AP CS Tutor Brandon Horn.

Note: Your solutions do not need to resemble the solutions below to be correct.

rowSwap

  /**
   * Swaps all values in the specified 2 rows of mat.
   * @param mat the array
   * @param rowAIndex the index of a row to be swapped
   * @param rowBIndex the index of a row to be swapped
   */
  public static void rowSwap(int[][] mat, int rowAIndex, int rowBIndex)
  {
    int[] temp = mat[rowAIndex];
    mat[rowAIndex] = mat[rowBIndex];
    mat[rowBIndex] = temp;
  }

A 2D array is just a 1D array of 1D arrays. (Each row in a 2D array is a 1D array.) Rows in a 2D array can be swapped using the same technique as swapping elements in any 1D array. It is not necessary to traverse the elements within the rows to be swapped.

colSwap

  /**
   * Swaps all values in the specified 2 columns of mat.
   * @param mat the array
   * @param colAIndex the index of a column to be swapped
   * @param colBIndex the index of a column to be swapped
   */
  public static void colSwap(int[][] mat, int colAIndex, int colBIndex)
  {
    for(int r = 0; r < mat.length; r++)
    {
      int temp = mat[r][colAIndex];
      mat[r][colAIndex] = mat[r][colBIndex];
      mat[r][colBIndex] = temp;
    }
  }

Swapping the elements in 2 columns of a 2D array does require traversing the columns. Traversing a column in a 2D array requires varying the row index. Both columns to be swapped are traversed in the same loop. Each pair of elements is swapped using a standard swap algorithm.

fillRowMajor

  /**
   * Returns an array with the specified number of rows and columns
   * containing the characters from str in row-major order. If str.length()
   * is greater than rows * cols, extra characters are ignored. If
   * str.length() is less than rows * cols, the remaining elements in the
   * returned array contain null.
   * 
   * @param str the string to be placed in an array
   * @param rows the number of rows in the array to be returned
   * @param cols the number of columsn in the array to be returned
   * @return an array containing the characters from str in row-major order
   */
  public static String[][] fillRowMajor(String str, int rows, int cols)
  {
    String[][] mat = new String[rows][cols];
    
    int sIndex = 0;
    for(int r = 0; r < mat.length; r++)
    {
      for(int c = 0; c < mat[r].length; c++)
      {
        if(sIndex < str.length())
        {
          mat[r][c] = str.substring(sIndex, sIndex + 1);
          sIndex++;
        }
      }
    }
    
    return mat;
  }

Filling a 2D array from a 1D data structure (String, 1D array, List) is common on the AP CS A Exam. My preference is to use loops to traverse the 2D data structure and to maintain an index for the 1D data structure. I prefer this because a 2D data structure is more difficult to traverse than a 1D data structure and the loops make it easy.

sIndex must be checked for validity since the length of str is not guaranteed to be the same as rows * cols.

Writing this method using the opposite technique (a loop through the 1D data structure and indexes for the 2D data structure) is also a good exercise.

fillColumnMajor

  /**
   * Returns an array containing the elements of vals in column-major order.
   * 
   * Precondition: vals.length == rows * cols
   * 
   * @param vals the elements
   * @param rows the number of rows in the array to be returned
   * @param cols the number of columns in the array to be returned
   * @return an array containing the elements of vals in column-major order
   */
  public static int[][] fillColumnMajor(int[] vals, int rows, int cols)
  {
    int[][] mat = new int[rows][cols];
    
    int vIndex = 0;
    for(int c = 0; c < mat[0].length; c++)
    {
      for(int r = 0; r < mat.length; r++)
      {
        mat[r][c] = vals[vIndex];
        vIndex++;
      }
    }
    
    return mat;
  }

Filling a 2D array in column-major order is the same as filling it in row-major order except the loops are reversed.

The precondition means it isn’t necessary to check vIndex for validity.

fillDownUp

  /**
   * Returns an array with the specified number of rows and columns that
   * contains the elements of vals in the order specified below. Elements
   * from vals are placed in the array by moving down the first column,
   * up the second column and so on.
   * 
   * For example, if vals was:
   * {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
   * 
   * rows was 3 and cols was 4,
   * the returned array would be:
   * { {1, 6, 7, 12},
   *   {2, 5, 8, 11},
   *   {3, 4, 9, 10} }
   * 
   * Precondition: vals.length == rows * cols
   * 
   * @param vals the elements
   * @param rows the number of rows in the array to be returned
   * @param cols the number of columns in the array to be returned
   * @return an array containing the elements from vals in the specified order
   */
  public static int[][] fillDownUp(int[] vals, int rows, int cols)
  {
    int[][] mat = new int[rows][cols];
    
    int vIndex = 0;
    
    for(int c = 0; c < mat[0].length; c++)
    {
      for(int r = 0; r < mat.length; r++)
      {
        if(c % 2 == 0)
          mat[r][c] = vals[vIndex];
        else
          mat[mat.length - r - 1][c] = vals[vIndex];
        
        vIndex++;
      }
    }
    
    return mat;
  }

Filling a 2D array in an unusual order has been featured on the AP CS A Exam. This solution uses the same loops as a standard column-major traversal but checks if the column index is even. Even indexed columns are filled from top to bottom. Odd indexed columns are filled from bottom to top.

An alternative approach, which might be easier to code under pressure, is to check if the column index is even befor the inner loop. Different loops can then be used depending on the desired traversal order.

grow

  /**
   * Returns a larger array containing the same elements as the
   * mat. The elements from mat are read in row-major order and
   * appear in the new array in row-major order.
   * 
   * For example, if mat was:
   * { {10, 9, 8, 7},
   *   {6, 5, 4, 3},
   *   {2, 1, -1, 0} }
   * 
   * newRows was 4 and newCols was 5
   * the returned array would be:
   * { {10, 9, 8, 7, 6},
   *   {5, 4, 3, 2, 1},
   *   {-1, 0, 0, 0, 0},
   *   {0, 0, 0, 0, 0} }
   * 
   * Precondition: newRows > mat.length && newCols > mat[0].length
   * 
   * @param mat the 2D array containing the original elements
   * @param newRows the number of rows in the new array
   * @param newCols the number of columns in the new array
   * @return a larger array containing the elements from mat in row-major order
   */
  public static int[][] grow(int[][] mat, int newRows, int newCols)
  {
    int[][] newMat = new int[newRows][newCols];
    
    // since we're only visiting the elements in mat, use the loops to traverse mat
    int newMatRow = 0, newMatCol = 0;
    for(int matRow = 0; matRow < mat.length; matRow++)
    {
      for(int matCol = 0; matCol < mat[matRow].length; matCol++)
      {
        newMat[newMatRow][newMatCol] = mat[matRow][matCol];
        
        newMatCol++;
        if(newMatCol == newMat[newMatRow].length)
        {
          newMatRow++;
          newMatCol = 0;
        }
      }
    }
    
    return newMat;
  }

Both the new and old data structures are 2D arrays, so the choice of which one to loop through is less obvious. My solution uses loops to traverse the old array because I want the assignment statement to run once for each element in the old array. Indexes are then maintained for the new array.

Using maintained indexes to traverse a 2D array (often as part of a while loop) is a fair question on the AP CS A Exam. This is easily practiced by printing the elements of a 2D array using only a single while loop.

crop

  /**
   * Returns a smaller array containing the elements in the specified
   * range of the mat.
   * 
   * For example,
   * 
   * mat:
   * { {10, 9, 8, 7},
   *   {6, 5, 4, 3},
   *   {2, 1, -1, 0} }
   * 
   * startRow: 0, startCol: 1, endRow: 1, endCol: 2
   * 
   * would yield:
   * { {9, 8},
   *   {5, 4} }
   * 
   * @param mat the 2D array containing the original elements
   * @param startRow the first row to be kept
   * @param startCol the first column to be kept
   * @param endRow the last row to be kept
   * @param endCol the last column to be kept
   * @return a smaller array containing the specified elements
   */
  public static int[][] crop(int[][] mat,
      int startRow, int startCol,
      int endRow, int endCol)
  {
    int newRows = endRow - startRow + 1;
    int newCols = endCol - startCol + 1;
    int[][] cropped = new int[newRows][newCols];
    
    for(int newR = 0; newR < cropped.length; newR++)
      for(int newC = 0; newC < cropped[0].length; newC++)
        cropped[newR][newC] = mat[startRow + newR][startCol + newC];
    
    return cropped;
  }

This solution uses loops to traverse the new array because the assignment statement inside is intended to run once for each position in the new array. The position in the old array can be easily computed from the position in the new array.

Alternatively, indexes for the old array can be maintained using the same technique as in grow.

invert

  /**
   * Returns an array containing the same elements as
   * mat but with the rows and columns reversed.
   * 
   * For example:
   * 
   * mat:
   * { {10, 9, 8, 7},
   *   {6, 5, 4, 3},
   *   {2, 1, -1, 0} }
   *   
   * would yield:
   * { {10, 6, 2},
   *   {9, 5, 1},
   *   {8, 4, -1},
   *   {7, 3, 0} }
   * 
   * @param mat the array
   * @return an array containing elements as described
   */
  public static int[][] invert(int[][] mat)
  {
    int[][] newMat = new int[mat[0].length][mat.length];
    
    int oldR = 0, oldC = 0;
    for(int newC = 0; newC < newMat[0].length; newC++)
    {
      for(int newR = 0; newR < newMat.length; newR++)
      {
        newMat[newR][newC] = mat[oldR][oldC];
        
        oldC++;
        if(oldC == mat[0].length)
        {
          oldR++;
          oldC = 0;
        }
      }
    }
    
    return newMat;
  }
}

Both the old and new arrays must be traversed here and both have the same number of elements. Loops should be used to traverse one array and indexes should be maintained for the other. It doesn’t matter which array is traversed with loops.

Leave a Reply