Matrix Problems

Matrices are 2D arrays. Check out Matrices.

Zigzag Conversion - Med

Convert a string to be written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Example converting "PAYPALISHIRING" results in: P A H N A P L S I I G Y I R This here is my crude solution.

class Solution {
    public String convert(String input, int numRows) {        
        int len = input.length();
        if(numRows == 1 || numRows >= len) return input;
 
        Character[][] matrix = new Character[numRows][Math.ceilDiv(len, numRows) * numRows];
        int rowPos = 0, colPos = 0;
        boolean zig = false;
        String res = "";
 
        for (int i = 0; i < len; i++) { // iterate through the word
            // this loop inserts
            if (rowPos < numRows) {
                matrix[rowPos][colPos] = (input.charAt(i));
            }
            // Only advance to next column on the zig
            if (rowPos == numRows - 1) zig = true;
            if (rowPos == 0) zig = false;
 
            if (zig) {
                rowPos--;
                colPos++;
            } else{
                rowPos++;
            }
        }
        for (Character[] chrs : matrix) {
            for (int j = 0; j < chrs.length; j++) {
                if(chrs[j] != null){
                res = res.concat(String.valueOf(chrs[j]));
                }
            }
        }
        return res;
    }
}

Another more efficient solution that’s O(n * numRows) time complexity and O(n + numRows) space complexity is this one courtsey of Greg Hogg.

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
 
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++) {
            rows.add(new StringBuilder());
        }
 
        int i = 0;
        boolean goingDown = false;
 
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) goingDown = !goingDown;
            i += goingDown ? 1 : -1;
        }
 
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        return result.toString();
    }
}

Flood Fill - Easy

This problem involves a Matrix and is a great example of using DFS. This one sort of duped me, because it’s obviously a DFS problem yet the 2D array makes it a bit more complex and requires crude implementation of DFS.

1. Check if the starting cell is already colored by the new color
   1. Then return the image.
   2. Or call the helper function.
2. In the helper, check for bounds, and if the current cell doesn’t match the original color of the starting cell.
   1. return nothing to backtrack.
3. otherwise call the helper recursively on all four directions. Code:

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // visit starter
        if (image[sr][sc] == color) {
            return image;
        }
        helper(image, sr, sc, image[sr][sc], color);
        return image;
    }
 
    public void helper(int[][] image, int r, int c, int old, int color) {
        if (r < 0 || c < 0 ||
                image.length <= r ||
                image[0].length <= c) {
            return;
        }
        if (image[r][c] != old) {
            return;
        } else {
            image[r][c] = color;
        }
        helper(image, r + 1, c, old, color);
        helper(image, r - 1, c, old, color);
        helper(image, r, c + 1, old, color);
        helper(image, r, c - 1, old, color);
    }
}