Wave Traversal

Problem Statement

Write a Java program that implements a method to traverse a 2D array (matrix) in a wave pattern, where even-indexed columns (0-based) are traversed top-to-bottom and odd-indexed columns are traversed bottom-to-top. The program should return a 1D array containing the elements in the order of traversal and test the implementation with matrices of different sizes, including edge cases like single-row or single-column matrices. You can visualize this as navigating a grid like a wave, moving down even columns and up odd columns, collecting numbers like a surfer riding along a zigzag path.

Input: A 2D array (matrix) of integers with dimensions m × n (e.g., matrix = [[1, 2, 3], [4, 5, 6]]). Output: A 1D array containing the elements in wave traversal order (e.g., [1, 4, 6, 5, 3, 2]). Constraints:

• 1 ≤ m, n ≤ 100 (where m is the number of rows and n is the number of columns).
• Elements are integers between -10^9 and 10^9.
• The matrix is guaranteed to be non-empty and rectangular (all rows have the same number of columns). Example:
• Input: matrix = [[1, 2, 3], [4, 5, 6]]
• Output: [1, 4, 6, 5, 3, 2]
• Explanation: Column 0 (even): top-to-bottom [1, 4]; Column 1 (odd): bottom-to-top [6, 5]; Column 2 (even): top-to-bottom [3, 2].
• Input: matrix = [[1, 2], [3, 4], [5, 6]]
• Output: [1, 3, 5, 6, 4, 2]
• Explanation: Column 0 (even): top-to-bottom [1, 3, 5]; Column 1 (odd): bottom-to-top [6, 4, 2].

Pseudocode

FUNCTION waveTraversal(matrix)
    IF matrix is null OR matrix is empty OR matrix[0] is empty THEN
        RETURN null
    ENDIF
    SET rows to number of rows in matrix
    SET cols to number of columns in matrix
    CREATE result array of size rows * cols
    SET index to 0
    FOR j from 0 to cols - 1
        IF j is even THEN
            FOR i from 0 to rows - 1
                SET result[index] to matrix[i][j]
                INCREMENT index
            ENDFOR
        ELSE
            FOR i from rows - 1 to 0
                SET result[index] to matrix[i][j]
                INCREMENT index
            ENDFOR
        ENDIF
    ENDFOR
    RETURN result
ENDFUNCTION

FUNCTION main()
    SET testMatrices to 2D arrays
    FOR each matrix in testMatrices
        CALL waveTraversal(matrix)
        PRINT result
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input matrix is null, empty, or has empty rows. If so, return null.
2. Get the dimensions: rows (m) and columns (n).
3. Create a 1D result array of size m * n to store the wave traversal elements.
4. Initialize an index to track the position in the result array.
5. Iterate through each column j from 0 to n-1: a. If j is even, traverse top-to-bottom (i from 0 to rows-1), adding matrix[i][j] to result. b. If j is odd, traverse bottom-to-top (i from rows-1 to 0), adding matrix[i][j] to result. c. Increment the index after each element is added.
6. Return the result array.
7. In the main method, create test matrices of different sizes and call waveTraversal to verify correctness.

Java Implementation

public class WaveTraversal {
    // Traverses matrix in wave pattern and returns 1D array
    public int[] waveTraversal(int[][] matrix) {
        // Check for null or empty matrix
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return null;
        }
        // Get dimensions
        int rows = matrix.length;
        int cols = matrix[0].length;
        // Create result array
        int[] result = new int[rows * cols];
        int index = 0;
        // Traverse each column
        for (int j = 0; j < cols; j++) {
            // Even column: top-to-bottom
            if (j % 2 == 0) {
                for (int i = 0; i < rows; i++) {
                    result[index++] = matrix[i][j];
                }
            }
            // Odd column: bottom-to-top
            else {
                for (int i = rows - 1; i >= 0; i--) {
                    result[index++] = matrix[i][j];
                }
            }
        }
        return result;
    }

    // Main method to test waveTraversal with various inputs
    public static void main(String[] args) {
        WaveTraversal traverser = new WaveTraversal();

        // Test case 1: 2x3 matrix
        int[][] matrix1 = {{1, 2, 3}, {4, 5, 6}};
        System.out.println("Test case 1:");
        System.out.println("Matrix:");
        printMatrix(matrix1);
        System.out.print("Wave traversal: ");
        printArray(traverser.waveTraversal(matrix1));

        // Test case 2: 3x2 matrix
        int[][] matrix2 = {{1, 2}, {3, 4}, {5, 6}};
        System.out.println("Test case 2:");
        System.out.println("Matrix:");
        printMatrix(matrix2);
        System.out.print("Wave traversal: ");
        printArray(traverser.waveTraversal(matrix2));

        // Test case 3: 1x3 single-row matrix
        int[][] matrix3 = {{1, 2, 3}};
        System.out.println("Test case 3:");
        System.out.println("Matrix:");
        printMatrix(matrix3);
        System.out.print("Wave traversal: ");
        printArray(traverser.waveTraversal(matrix3));

        // Test case 4: 3x1 single-column matrix
        int[][] matrix4 = {{1}, {2}, {3}};
        System.out.println("Test case 4:");
        System.out.println("Matrix:");
        printMatrix(matrix4);
        System.out.print("Wave traversal: ");
        printArray(traverser.waveTraversal(matrix4));

        // Test case 5: 2x2 matrix with negative numbers
        int[][] matrix5 = {{-1, -2}, {-3, -4}};
        System.out.println("Test case 5:");
        System.out.println("Matrix:");
        printMatrix(matrix5);
        System.out.print("Wave traversal: ");
        printArray(traverser.waveTraversal(matrix5));

        // Test case 6: Null matrix
        int[][] matrix6 = null;
        System.out.println("Test case 6:");
        System.out.println("Matrix:");
        printMatrix(matrix6);
        System.out.print("Wave traversal: ");
        printArray(traverser.waveTraversal(matrix6));
    }

    // Helper method to print matrix
    private static void printMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            System.out.println("null");
            return;
        }
        System.out.println("[");
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("  [");
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j]);
                if (j < matrix[i].length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
        System.out.println("]");
    }

    // Helper method to print 1D array
    private static void printArray(int[] arr) {
        if (arr == null) {
            System.out.println("null");
            return;
        }
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

Output

Running the main method produces:

Test case 1:
Matrix:
[
  [1, 2, 3]
  [4, 5, 6]
]
Wave traversal: [1, 4, 6, 5, 3, 2]
Test case 2:
Matrix:
[
  [1, 2]
  [3, 4]
  [5, 6]
]
Wave traversal: [1, 3, 5, 6, 4, 2]
Test case 3:
Matrix:
[
  [1, 2, 3]
]
Wave traversal: [1, 3, 2]
Test case 4:
Matrix:
[
  [1]
  [2]
  [3]
]
Wave traversal: [1, 2, 3]
Test case 5:
Matrix:
[
  [-1, -2]
  [-3, -4]
]
Wave traversal: [-1, -3, -4, -2]
Test case 6:
Matrix:
null
Wave traversal: null

Explanation:

• Test case 1: Traverses 2×3 matrix: Col 0 (even): [1, 4]; Col 1 (odd): [6, 5]; Col 2 (even): [3, 2].
• Test case 2: Traverses 3×2 matrix: Col 0 (even): [1, 3, 5]; Col 1 (odd): [6, 4, 2].
• Test case 3: Traverses 1×3 matrix: Col 0 (even): [1]; Col 1 (odd): [3]; Col 2 (even): [2].
• Test case 4: Traverses 3×1 matrix: Col 0 (even): [1, 2, 3].
• Test case 5: Traverses 2×2 matrix with negatives: Col 0 (even): [-1, -3]; Col 1 (odd): [-4, -2].
• Test case 6: Returns null for a null matrix.

How It Works

• Step 1: The waveTraversal method checks for null or empty matrices. For [[1, 2, 3], [4, 5, 6]], it proceeds.
• Step 2: Get dimensions: rows = 2, cols = 3.
• Step 3: Create a result array of size 2 * 3 = 6.
• Step 4: Iterate through columns:
  • Col 0 (even): i = 0 to 1 → result[0] = matrix[0][0] = 1, result[1] = matrix[1][0] = 4.
  • Col 1 (odd): i = 1 to 0 → result[2] = matrix[1][1] = 6, result[3] = matrix[0][1] = 5.
  • Col 2 (even): i = 0 to 1 → result[4] = matrix[0][2] = 3, result[5] = matrix[1][2] = 2.
• Example Trace: For test case 1, builds [1, 4, 6, 5, 3, 2] by alternating directions.
• Main Method: Tests with different sizes (2×3, 3×2, 1×3, 3×1, 2×2) and a null matrix, printing inputs and results.
• Wave Property: Alternates top-to-bottom and bottom-to-top traversal based on column index parity.

Complexity Analysis Table

Note:

• m is the number of rows, n is the number of columns.
• Time complexity: O(m*n), as the algorithm visits each element once.
• Space complexity: O(m*n), for the result array. Temporary variables use O(1) space.
• Best, average, and worst cases are O(m*n).

✅ Tip: Use a single index to track the result array position for simplicity. Test with single-row, single-column, and negative number matrices to ensure the wave pattern is correct.

⚠ Warning: Ensure the input matrix is not null and is rectangular to avoid NullPointerException or ArrayIndexOutOfBoundsException. Verify consistent row lengths for a well-formed matrix.