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.

DFS ( recursion)

def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
	if image[sr][sc] == color:
		return image
	
	old = image[sr][sc]
	self.helper(image, sr, sc, old,color)
	return image
	
# helper makes managing the values during recursion easier
def helper(self, image, row, col, old, new):
	# if out of bounds return nothing, pops it from stack
	if row < 0 or len(image) <= row or col < 0 or len(image[row]) <= col:
		return 
	if image[row][col] != old:
		return
	else:
		image[row][col] = new
	
	# all neighbors in 4 directions
	self.helper(image, row + 1, col, old, new)
	self.helper(image, row, col + 1, old, new)
	self.helper(image, row - 1, col, old, new)
	self.helper(image, row, col - 1, old, new)        

BFS ( queue )

def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
	if image[sr][sc] == color:
		return image
	old = image[sr][sc]
	# Queue initialized with starting coordinates
	queue = deque([(sr, sc)])
	while queue:
		# pop and visit
		r, c = queue.popleft()
		# check out of bounds
		if r < 0 or len(image) <= r or c < 0 or len(image[r]) <= c:
			continue
		elif image[r][c] == old:
			image[r][c] = color
		else:
			continue
		queue.append((r + 1,c))
		queue.append((r,c + 1))
		queue.append((r - 1,c ))
		queue.append((r,c - 1))
 
	return image

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);
    }
}

Search a 2D Matrix

You’re given a matrix, 2D array, and a target integer and are asked to return a boolean if it exists in the matrix or not.
The matrix’s rows are sorted such that the first integer of a row is greater than the last of the previous row, meaning it’s Sorted.

The aim is to write a solution that runs in O(log(m * n)) time with m being the number of rows and n columns.
Instantly I thought of Binary Search.

Algorithm Breakdown:

1. Check if matrix is null, return False
2. Init start pointer at 0 and end pointer at m - 1
3. while start <= end:
   1. Init mid = start + (end - start) / 2
   2. check if target is greater than largest number in row of matrix[mid] and not in the row, set start = mid + 1
   3. check if target is less than largest number in row of matrix[mid] and not in the row, set end = mid - 1
   4. else return True
4. return False if reached end and not found

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:    
	if not matrix:
		return False
	
	r_start = 0
	r_end = len(matrix) - 1
	
	while r_start <= r_end:
		r_mid = r_start + (r_end - r_start) // 2
	
		if matrix[r_mid][-1] < target and target not in matrix[r_mid]:
			r_start = r_mid + 1
		elif target < matrix[r_mid][-1] and target not in matrix[r_mid]:
			r_end = r_mid - 1
		else:
			return True
	return False