2D array practice solutions

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

Review the solutions with AP CS Tutor Brandon Horn.

rowSwap method

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 an array of 1D arrays. Each row in a 2D array is a (reference to a) 1D array. Rows in a 2D array can be swapped using the same technique as swapping elements in a 1D array. It is not necessary to traverse the elements within the rows to be swapped.

colSwap method

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 method

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, ArrayList) 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 method

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 method

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 - 1 - r][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.

mat.length - 1 - r calculates the index r rows from the bottom of mat. On the AP CS A Exam, this is usually written as mat.length - r - 1 (which annoys me).

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 method

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 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 a single while loop.

crop method

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 method

public static int[][] invert(int[][] mat)
{
    int[][] newMat = new int[mat[0].length][mat.length];
    
    for(int r = 0; r < mat.length; r++)
        for(int c = 0; c < mat[0].length; c++)
            newMat[c][r] = mat[r][c];
    
    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.

consolidate method

public static void consolidate(String[][] mat)
{
	int newR = 0, newC = 0;
	
	for(int oldR = 0; oldR < mat.length; oldR++)
	{
		for(int oldC = 0; oldC < mat[0].length; oldC++)
		{
			if(mat[oldR][oldC] != null)
			{
				mat[newR][newC] = mat[oldR][oldC];
				
				if(newR != oldR || newC != oldC)
					mat[oldR][oldC] = null;
				
				newC++;
				if(newC == mat[0].length)
				{
					newR++;
					newC = 0;
				}
			}
		}
	}
}

This is a variation on the standard algorithm to consolidate an array structure by removing undesired elements. The algorithm keeps track of where the next element to be kept would go ([newR][newC]). Each time an element is kept, the position is updated. See Algorithm to consolidate an array for additional discussion.

There are a few ways to ensure that the empty spots are null. This approach explicitly checks if an element has been moved. If an element has been moved, it sets the position from which it was moved to null. The alternate solution below uses a different approach.

consolidate method (alternate solution)

public static void consolidate(String[][] mat)
{
	int newR = 0, newC = 0;
	
	for(int oldR = 0; oldR < mat.length; oldR++)
	{
		for(int oldC = 0; oldC < mat[0].length; oldC++)
		{
			if(mat[oldR][oldC] != null)
			{
				mat[newR][newC] = mat[oldR][oldC];
				
				newC++;
				if(newC == mat[0].length)
				{
					newR++;
					newC = 0;
				}
			}
		}
	}
	
	while(newR < mat.length)
	{
		mat[newR][newC] = null;
		
		newC++;
		if(newC == mat[0].length)
		{
			newR++;
			newC = 0;
		}
	}
}

This is the same solution as the original except with respect to handling null. This solution uses an extra loop to set all remaining spots (after the last desired element has been kept) to null.

It is also possible to construct a new array to address this issue. Since the consolidate method is void, the elements would have to be copied back into the original array.

Additional 2D array resources

Comments

Comment on 2D array practice exercises