Matrix - Matrices algorithms

AAA_Matrix_Utils.txt

Matrix - Matrices algorithms 

AreMatrixEqualsJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class AreMatrixEqualsJTests {

    int[][] a, b;

    @Test
    public void nullEmpty() {
        a = null;
        assertTrue("same reference", MatrixUtils.areMatrixEquals(a, a));

        a = null;
        b = null;
        assertTrue("null", MatrixUtils.areMatrixEquals(a, b));

        a = null;
        b = new int[][]{};
        assertFalse("one null", MatrixUtils.areMatrixEquals(a, b));

        a = new int[][]{};
        b = new int[][]{};
        assertTrue("empty", MatrixUtils.areMatrixEquals(a, b));
    }

    @Test
    public void array() {
        a = new int[][]{{1}};
        b = new int[][]{{1}};
        assertTrue("same array", MatrixUtils.areMatrixEquals(a, b));

        a = new int[][]{{1}};
        b = new int[][]{{0}};
        assertFalse("different array", MatrixUtils.areMatrixEquals(a, b));
    }

    @Test
    public void square() {
        a = new int[][]{
                {1,1},
                {1,1}};
        b = new int[][]{
                {1,1},
                {1,1}};
        assertTrue("2x2 same", MatrixUtils.areMatrixEquals(a, b));

        a = new int[][]{
                {1,1},
                {1,0}};
        b = new int[][]{
                {1,1},
                {1,1}};
        assertFalse("2x2 different", MatrixUtils.areMatrixEquals(a, b));
        
        a = new int[][]{
                {1,1,1},
                {1,1,1},
                {1,1,1}};
        b = new int[][]{
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}};
        assertFalse("different sizes square", MatrixUtils.areMatrixEquals(a, b));
    }

    @Test
    public void rectangle() {
        a = new int[][]{
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}};
        b = new int[][]{
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}};
        assertTrue("same rectangle", MatrixUtils.areMatrixEquals(a, b));

        a = new int[][]{
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}};
        b = new int[][]{
                {1,1},
                {1,1},
                {1,1}};
        assertFalse("different size rectangle", MatrixUtils.areMatrixEquals(a, b));
    }
}

BiggestSquareJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class BiggestSquareJTests {

    int[][] matrix;
    int val;


    @Test(expected = IllegalArgumentException.class)
    public void nullMatrix() {
        matrix = null;
        MatrixUtils.getBiggestSquare(matrix);
    }

    @Test
    /*
    full matrix. Initialize matrix all to 1, result is 0
    111
    111
    111
    */
    public void fullMatrix() {

        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x3 full 1 matrix is value 0", 0, val);

        matrix = new int[4][6];
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 6; j++){
                matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("4x6 full 1 matrix is value 0", 0, val);
    }

    @Test
    /*
    empty matrix. Initialize matrix all to 0, result is MxN
    000
    000
    000
    */
    public void emptyMatrix() {

        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                matrix[i][j] = 0;
            }
        }

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x3 full 0 matrix is value 9", 9, val);

        matrix = new int[4][6];
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 6; j++){
                matrix[i][j] = 0;
            }
        }

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("4x6 full 0 matrix is value 16", 16, val);
    }

    @Test
    /*
    symmetric matrix. Initialize matrix to same value both halves, result is 1
    101
    101
    101

    111
    000
    111
    */
    public void symmetricMatrix() {

        //column symmetric
        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(j == 1) matrix[i][j] = 0;
                else matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x3 column symmetric matrix is value 1", 1, val);

        //row symmetric
        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(i == 1) matrix[i][j] = 0;
                else matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x3 row symmetric matrix is value 1", 1, val);
    }

    @Test
    /*
    random matrix
    square in middle (4)
    001001
    011001
    100100

    square from top-left (9)
    000001
    000001
    000100

    square from bottom-right (4)
    000000
    111100
    111100
    */
    public void randomMatrix() {

        //square in middle (4)
        matrix = new int[][]{
                {0,0,1,0,0,1}
                ,{0,1,1,0,0,1}
                ,{1,0,0,1,0,0}
        };

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x6 square in middle matrix is value 4", 4, val);

        //square from top-left (9)
        matrix = new int[][]{
                {0,0,0,0,0,1}
                ,{0,0,0,0,0,1}
                ,{0,0,0,1,0,0}
        };

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x6 square from top-left matrix is value 9", 9, val);

        //square from bottom-right (4)
        matrix = new int[][]{
                {0,0,0,0,0,0}
                ,{1,1,1,1,0,0}
                ,{1,1,1,1,0,0}
        };

        val = MatrixUtils.getBiggestSquare(matrix);

        assertEquals("3x6 square from bottom-right matrix is value 4", 4, val);
    }
}

ClosestPairSumUpToKJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import com.blogspot.groglogs.structures.Pair;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class ClosestPairSumUpToKJTests {

    int[] a, b;
    int target;
    Pair<Integer, Integer> expected;

    @Test
    public void nullEmpty() {
        a = null;
        b = null;
        target = 1;
        expected = new Pair<>();
        assertEquals("null input", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{};
        b = new int[]{};
        target = 1;
        expected = new Pair<>();
        assertEquals("empty input", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));
    }

    @Test
    public void singleValue() {
        a = new int[]{1};
        b = new int[]{1};
        target = 2;
        expected = new Pair<>(1, 1);
        assertEquals("1,1 target 2", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{1};
        b = new int[]{1};
        target = 0;
        expected = new Pair<>(1, 1);
        assertEquals("1,1 target 0", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{1};
        b = new int[]{1};
        target = 3;
        expected = new Pair<>(1, 1);
        assertEquals("1,1 target 3", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));
    }

    @Test
    public void sample() {
        a = new int[]{4, 1, 7, 10};
        b = new int[]{20, 2, 5, 6};
        target = 11;
        expected = new Pair<>(10, 2);
        assertEquals("(4, 1, 7, 10),(20, 2, 5, 6) target 11", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{4, 1, 7, 10};
        b = new int[]{20, 2, 5, 6};
        target = 24;
        expected = new Pair<>(4, 20);
        assertEquals("(4, 1, 7, 10),(20, 2, 5, 6) target 24", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{4, 1, 7, 10};
        b = new int[]{20, 2, 5, 6};
        target = 31;
        expected = new Pair<>(10, 20);
        assertEquals("(4, 1, 7, 10),(20, 2, 5, 6) target 31", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{4, 1, 7, 10};
        b = new int[]{20, 2};
        target = 11;
        expected = new Pair<>(10, 2);
        assertEquals("(4, 1, 7, 10),(20, 2) target 11", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{4, 1, 7, 10};
        b = new int[]{20, 2};
        target = 9;
        expected = new Pair<>(7, 2);
        assertEquals("(4, 1, 7, 10),(20, 2) target 9", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));

        a = new int[]{4, 1, 7, 10};
        b = new int[]{20, 2};
        target = 31;
        expected = new Pair<>(10, 20);
        assertEquals("(4, 1, 7, 10),(20, 2) target 31", expected, MatrixUtils.findClosestPairSumUpToK(a, b, target));
    }
}

DeleteIslandsJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertTrue;

public class DeleteIslandsJTests {

    int[][] matrix, expected;

    @Test
    public void nullEmpty() {
        matrix = null;
        expected = null;
        MatrixUtils.deleteIslands(matrix);
        assertTrue("null matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{};
        expected = new int[][]{};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("empty matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{{1}};
        expected = new int[][]{{1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("array matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }

    @Test
    public void tooSmallMatrix() {
        matrix = new int[][]{
                {1,1},
                {1,1}};
        expected = new int[][]{
                {1,1},
                {1,1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("2x2 matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{
                {1,1},
                {1,1},
                {1,1}};
        expected = new int[][]{
                {1,1},
                {1,1},
                {1,1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("3x2 matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }

    @Test
    public void allOnes() {
        matrix = new int[][]{
                {1,1,1},
                {1,1,1},
                {1,1,1}};
        expected = new int[][]{
                {1,1,1},
                {1,1,1},
                {1,1,1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("all ones 3x3 matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}};
        expected = new int[][]{
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("all ones 3x4 matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }

    @Test
    public void allZeros() {
        matrix = new int[][]{
                {0,0,0},
                {0,0,0},
                {0,0,0}};
        expected = new int[][]{
                {0,0,0},
                {0,0,0},
                {0,0,0}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("all zeros 3x3 matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0}};
        expected = new int[][]{
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("all zeros 3x4 matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }

    @Test
    public void onlyBorders() {
        matrix = new int[][]{
                {1,1,1},
                {1,0,1},
                {1,1,1}};
        expected = new int[][]{
                {1,1,1},
                {1,0,1},
                {1,1,1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("only borders 3x3 matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{
                {1,1,1,1},
                {1,0,0,1},
                {1,1,1,1}};
        expected = new int[][]{
                {1,1,1,1},
                {1,0,0,1},
                {1,1,1,1}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("only borders 3x4 matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }

    @Test
    public void noBorders() {
        matrix = new int[][]{
                {0,0,0},
                {0,1,0},
                {0,0,0}};
        expected = new int[][]{
                {0,0,0},
                {0,0,0},
                {0,0,0}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("no borders 3x3 matrix", MatrixUtils.areMatrixEquals(matrix, expected));

        matrix = new int[][]{
                {0,0,0,0},
                {0,1,1,0},
                {0,0,0,0}};
        expected = new int[][]{
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0}};
        MatrixUtils.deleteIslands(matrix);
        assertTrue("no borders 3x4 matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }

    @Test
    public void sample() {
        matrix = new int[][]{
                {1,0,0,0,0,0},
                {0,1,0,1,1,1},
                {0,0,1,0,1,0},
                {1,1,0,0,1,0},
                {1,0,1,1,0,0},
                {1,0,0,0,0,1},
        };
        expected = new int[][]{
                {1,0,0,0,0,0},
                {0,0,0,1,1,1},
                {0,0,0,0,1,0},
                {1,1,0,0,1,0},
                {1,0,0,0,0,0},
                {1,0,0,0,0,1},
        };
        MatrixUtils.deleteIslands(matrix);
        assertTrue("sample matrix", MatrixUtils.areMatrixEquals(matrix, expected));
    }
}

FindValueInSortedMatrixJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class FindValueInSortedMatrixJTests {

    int[][] matrix;
    int val;


    @Test
    public void nullEmpty() {
        matrix = null;
        val = 1;
        assertFalse("null matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        matrix = new int[][]{};
        val = 1;
        assertFalse("empty matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));
    }

    @Test
    public void arrayMatrix(){
        matrix = new int[][]{{1, 2, 3, 4}};
        val = 3;
        assertTrue("array matrix val in matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        matrix = new int[][]{{1, 2, 3, 4}};
        val = 6;
        assertFalse("array matrix val not in matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));
    }

    @Test
    public void sameValue(){
        matrix = new int[][]{
                {0, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 0, 0}
        };
        val = 3;
        assertFalse("val not in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 0;
        assertTrue("val in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        matrix = new int[][]{
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
        };
        val = 3;
        assertFalse("val not in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 0;
        assertTrue("val in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));
    }

    @Test
    public void sample(){
        matrix = new int[][]{
                {10, 20, 30, 40},
                {15, 25, 35, 45},
                {27, 29, 37, 48},
                {32, 33, 39, 50}
        };
        val = 3;
        assertFalse("val not in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 32;
        assertTrue("bottom left corner in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 10;
        assertTrue("top left corner in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 40;
        assertTrue("top right corner in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 50;
        assertTrue("bottom right corner in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 25;
        assertTrue("val in square matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        matrix = new int[][]{
                {10, 20, 30, 40, 42},
                {15, 25, 35, 45, 47},
                {27, 29, 37, 48, 49},
                {32, 33, 39, 50, 90}
        };
        val = 3;
        assertFalse("val not in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 32;
        assertTrue("bottom left corner in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 10;
        assertTrue("top left corner in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 42;
        assertTrue("top right corner in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 90;
        assertTrue("bottom right corner in rectangle matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));

        val = 25;
        assertTrue("val in matrix", MatrixUtils.findValueInSortedMatrix(matrix, val));
    }
}

MatrixJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MatrixJTests {

    int[][] matrix;
    int val;


    @Test
    //null or empty input, return 0
    public void nullEmpty() {
        matrix = null;

        val = MatrixUtils.getBiggestGroupValue(matrix, 0, 0);

        assertEquals("null matrix is value 0", 0, val);

        //empty, throw IllegalArgumentException
        matrix = new int[1][1];

        try{
            val = MatrixUtils.getBiggestGroupValue(matrix, -1, 0);
        }catch(IllegalArgumentException e){
            System.out.println("Got expected exception for x = -1: " + e.getMessage());
        }

        try{
            val = MatrixUtils.getBiggestGroupValue(matrix, 0, -1);
        }catch(IllegalArgumentException e){
            System.out.println("Got expected exception for y = -1: " + e.getMessage());
        }
    }

    @Test
    /*
    full matrix. Initialize 3x3 matrix all to 1, result is sum of all cells -> 9
    111
    111
    111
    */
    public void fullMatrix() {

        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 3);

        assertEquals("3x3 full 1 matrix is value 9", 9, val);
    }

    @Test
    /*
    empty matrix. Initialize 3x3 matrix all to 0, result is sum of all cells -> 0
    000
    000
    000
    */
    public void emptyMatrix() {

        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                matrix[i][j] = 0;
            }
        }

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 3);

        assertEquals("3x3 full 0 matrix is value 0", 0, val);
    }

    @Test
    /*
    symmetric matrix. Initialize 3x3 matrix to same value both halves, result is sum of one half -> 3
    101
    101
    101

    111
    000
    111
    */
    public void symmetricMatrix() {

        //column symmetric
        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(j == 1) matrix[i][j] = 0;
                else matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 3);

        assertEquals("3x3 column symmetric matrix is value 3", 3, val);

        //row symmetric
        matrix = new int[3][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(i == 1) matrix[i][j] = 0;
                else matrix[i][j] = 1;
            }
        }

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 3);

        assertEquals("3x3 row symmetric matrix is value 3", 3, val);
    }

    @Test
    /*
    random matrix. Initialize 3x3 matrix to some values, result is biggest sum
    single biggest value (8)
    001003
    023004
    100800

    small group (7)
    001003
    023004
    100600

    biggest group (6)
    001003
    023002
    100500
    */
    public void randomMatrix() {

        //8 - single biggest value
        matrix = new int[][]{
                {0,0,1,0,0,3}
                ,{0,2,3,0,0,4}
                ,{1,0,0,8,0,0}
        };

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 6);

        assertEquals("3x6 single biggest value matrix is value 8", 8, val);

        //7 - small group value
        matrix = new int[][]{
                {0,0,1,0,0,3}
                ,{0,2,3,0,0,4}
                ,{1,0,0,6,0,0}
        };

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 6);

        assertEquals("3x6 small group value matrix is value 7", 7, val);

        //6 - biggest group value
        matrix = new int[][]{
                {0,0,1,0,0,3}
                ,{0,2,3,0,0,2}
                ,{1,0,0,5,0,0}
        };

        val = MatrixUtils.getBiggestGroupValue(matrix, 3, 6);

        assertEquals("3x6 biggest group value matrix is value 6", 6, val);
    }
}

MatrixUtils.java

package com.blogspot.groglogs.matrixutils;

import com.blogspot.groglogs.structures.Pair;
import com.blogspot.groglogs.structures.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MatrixUtils {

    /*
     * Input is a matrix with non empty or negative values
     * The groupings are all positive values surrounded by zeroes eg:
     * ________
     * |001003|
     * |002304|
     * --------
     *
     * 1,2,3 and 3,4 are groupings. Full matrix is a single grouping, empty matrix has value 0
     *
     * We walk the full matrix and every time we encounter a value > 0 we start searching for all adjacent values
     * and keep summing the values up and marking the positions as visited. When we cannot move anymore, we update the
     * current max result if needed and keep walking the matrix.
     *
     * We use a Point aux structure so that we can store the current data while updating the matrix and process the data later
     *
     * Since we do not do any more work on a visited node, total complexity is O(MxN)
     */
    private static int findGroupValue(int[][] matrix, int x, int y, Queue q){
        int res = 0;
        //keep adding points to the queue until we have no more options
        while(!q.isEmpty()){
            Point p = (Point)q.remove();
            //add us to the total, we are for sure not a visited or 0 point because of the enqueuing logic
            res += p.val;

            /*
            only consider unvisited and non zero neighbors
            must mark the added ones immediately as visited because of the search pattern.
            We might consider the same point twice otherwise, but the value changes in between!
            */
            //left
            if(p.x - 1 >= 0 && matrix[p.x - 1][p.y] > 0){
                q.add(new Point(p.x - 1, p.y, matrix[p.x - 1][p.y]));
                matrix[p.x - 1][p.y] = -1;
            }
            //up
            if(p.y - 1 >= 0 && matrix[p.x][p.y - 1] > 0){
                q.add(new Point(p.x, p.y - 1, matrix[p.x][p.y - 1]));
                matrix[p.x][p.y - 1] = -1;
            }
            //right
            if(p.x + 1 < x && matrix[p.x + 1][p.y] > 0){
                q.add(new Point(p.x + 1, p.y, matrix[p.x + 1][p.y]));
                matrix[p.x + 1][p.y] = -1;
            }
            //down
            if(p.y + 1 < y && matrix[p.x][p.y + 1] > 0){
                q.add(new Point(p.x, p.y + 1, matrix[p.x][p.y + 1]));
                matrix[p.x][p.y + 1] = -1;
            }
        }

        return res;
    }

    public static int getBiggestGroupValue(int[][] matrix, int x, int y){
        int res = 0, curr;

        if(matrix == null) return res;

        if(x < 0 || y < 0) throw new IllegalArgumentException("Invalid size: x = " + x + ",y = " + y);

        //scan the whole matrix
        for(int i = 0; i < x; i++){
            for(int j = 0; j < y; j++){

                //if it is a value point
                if(matrix[i][j] > 0){
                    //add it to the queue to visit as starting point
                    Queue<Point> q = new LinkedList<>();
                    q.add(new Point(i, j, matrix[i][j]));
                    //mark as visited
                    matrix[i][j] = -1;
                    //find its neighbors and evaluate the group value
                    curr = findGroupValue(matrix, x, y, q);

                    if(curr > res) res = curr;
                }
                else matrix[i][j] = -1; //otherwise just mark as visited
            }
        }

        return res;
    }

    //given an input matrix of only 0s and 1s, find the biggest square of only 0s
    //the square must be parallel to the matrix edges
    public static int getBiggestSquare(int[][] matrix){
        if(matrix == null) throw new IllegalArgumentException("Matrix cannot be null!");

        //track here the partial values with DP so we bring the runtime down to O(MxN)
        int[][] groupings = new int[matrix.length][matrix[0].length];

        /*starting from TOP-LEFT corner, we consider this:
        a 0 alone is a valid 1x1 square. Then, starting from the NEXT row (otherwise we CANNOT create a valid square),
        if matrix[i][j] == 0, it might contribute to an already existing square
        therefore, compare it against VALID neighbours (left, up, up-left) and consider us as part of an existing square
        or as the new TOP-LEFT corner of a new square
        and store in the BOTTOM-RIGHT of the current square the best size we got so far while also updating the current maximum
        otherwise, we broke a square, so move on to the next cell without changes and continue the logic
        */

        int max = 0;

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                //initialize the values while walking on the matrix
                groupings[i][j] = (matrix[i][j] == 0) ? 1 : 0;
                //extension to a valid square can only occur from the NEXT row and column!
                if(i > 0 && j > 0 && groupings[i][j] == 1){
                    //if we could be extending a square, find where are we contributing and add us
                    //Min because we are always the TOP-LEFT of the valid square starting from us!
                    //so if we are SURROUNDED by 0s, we are extending that valid square as BOTTOM-RIGHT corner
                    //otherwise, we are starting a NEW one from TOP-LEFT
                    groupings[i][j] = Math.min(Math.min(groupings[i - 1][j - 1], groupings[i - 1][j]), groupings[i][j - 1]) + 1;
                    if (groupings[i][j] > max) max = groupings[i][j];
                }
            }
        }

        //the actual biggest square size is the number of extensions we did to a valid square, squared
        return max * max;
    }

    /**
     * Given a matrix where all rows and columns are sorted, check if a given element is present in it.
     * @param matrix the matrix.
     * @param val the value to search for.
     * @return true if the value is found in the matrix.
     */
    public static boolean findValueInSortedMatrix(int[][] matrix, int val){
        if(matrix == null || matrix.length == 0){
            return false;
        }

        /*
        Matrix has rows and columns sorted, eg:

        10, 20, 30, 40
        15, 25, 35, 45
        27, 29, 37, 48
        32, 33, 39, 50

        so for rows: matrix[row][0] <= element <= matrix[row][row.length - 1]
        and for columns: matrix[0][column] <= element <= matrix[column.length - 1][column]

        We can therefore pick a corner and test the boundaries for our value, discarding rows and columns that cannot
        contain the result as necessary
         */

        //start from top right corner
        int row = 0;
        int col = matrix[row].length - 1;

        while(row < matrix.length && col >= 0){
            if(matrix[row][col] == val){
                return true;
            }

            if(matrix[row][col] > val){
                col--;
            }
            else{
                row++;
            }
        }

        return false;
    }

    /**
     * Given two arrays not necessarily of same length and a target value, find a pair of values from both arrays
     * whose sum is closest to the target.
     * @param a the first array of values.
     * @param b the second array of values.
     * @param target the target value.
     * @return a pair of values from both arrays whose sum is closest to the given target. Returns a pair of nulls if
     * either array is null or empty.
     */
    public static Pair<Integer, Integer> findClosestPairSumUpToK(int[] a, int[] b, int target){
        Pair<Integer, Integer> pair = new Pair<>();

        if(a == null || b == null || a.length == 0 || b.length == 0){
            return pair;
        }

        /*
        If we sort the arrays and create a matrix out of them we can apply our path finding methods like in findValueInSortedMatrix.

        Example:
        a = 4, 1, 7, 10
        b = 20, 2, 5, 6

        sort them and create a matrix of sums
            1    4    7    10
        2   3    6    9    12
        5   6    9   12    15
        6   7   10   13    16
        20  21  24   27    30

        given a target 11, we start from top right and move towards value 11, keeping track of the pair that summed up
        gave the closest delta to our target.
        Example initially we have 10+2 which is 12, a delta of 1 from target 11

        To avoid wasting O(NM) time creating the matrix, we just work with indices
         */

        //sort both arrays ascending
        Arrays.sort(a); //this will be columns
        Arrays.sort(b); //this will be rows

        int row = 0;
        int col = a.length - 1;

        pair.setFirst(a[col]);
        pair.setSecond(b[row]);
        int bestDelta = Math.abs(target - (a[col] + b[row]));

        while(row < b.length && col >= 0){
            int currDelta = Math.abs(target - (a[col] + b[row]));

            if(currDelta < bestDelta){
                pair.setFirst(a[col]);
                pair.setSecond(b[row]);
                bestDelta = currDelta;
            }

            if(bestDelta == 0){
                return pair;
            }

            if(a[col] + b[row] > target){
                col--;
            }
            else{
                row++;
            }
        }

        return pair;
    }

    /**
     * Given two matrices, check if they are equal, must have same dimensions and content.
     * @param a first matrix.
     * @param b second matrix.
     * @return true if both matrices have same dimensions and content.
     */
    public static boolean areMatrixEquals(int[][] a, int[][] b){
        //same reference or both nulls
        if(a == b){
            return true;
        }

        //only one null
        if((a != null && b == null) || (a == null && b != null)){
            return false;
        }

        //different row count
        if(a.length != b.length){
            return false;
        }
        //same length, but no rows
        if(a.length == 0){
            return true;
        }
        //different column count
        if(a[0].length != b[0].length){
            return false;
        }
        //same length, but no columns, check as arrays
        if(a[0].length == 0){
            for(int i = 0; i < a.length; i++){
                if(a[i] != b[i]){
                    return false;
                }
            }
            return true;
        }
        //otherwise check the content
        for(int i = 0; i < a.length; i++){
            for(int j = 0; j < a[0].length; j++){
                if(a[i][j] != b[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Given a matrix of zeros and ones, where groupings of one represent land, delete all islands.
     * An island is a group of 1 or more ones which are NOT horizontally or vertically connected to a border.
     *
     * Example:
     * 0001
     * 1010
     * 1000
     *
     * should return:
     * 0001
     * 1000
     * 1000
     *
     * where only the lone 1 in the middle is deleted
     * @param matrix the input matrix.
     */
    public static void deleteIslands(int[][] matrix){
        //unless we have a 3x3 matrix, there is no possibility to place a lonely 1 NOT connected to a border
        if(matrix == null || matrix.length < 3 || matrix[0].length < 3){
            return;
        }

        /*
        For each point in the borders that is a one, we start a DFS search for all horizontally or vertically
        connected ones, flipping all of them to -1.
        We flag each point we add to the stack as soon as we add it to avoid putting duplicates in.
        At the end of this search, we scan the whole matrix and restore the flipped ones while deleting the non flipped ones.
         */
        Stack<Point> points = new Stack<>();

        //matrix is not necessarily square, so we don't have same boundaries for rows and columns!

        //add all borders from first and last column
        for(int i = 0; i < matrix.length; i++){
            //all rows, first column
            if(matrix[i][0] == 1){
                matrix[i][0] = -1;
                points.push(new Point(i, 0));
            }
            //all rows, last column
            if(matrix[i][matrix[0].length - 1] == 1){
                matrix[i][matrix[0].length - 1] = -1;
                points.push(new Point(i, matrix[0].length - 1));
            }
        }

        //add all borders from first and last row
        for(int j = 0; j < matrix[0].length; j++){
            //all columns, first row
            if(matrix[0][j] == 1){
                matrix[0][j] = -1;
                points.push(new Point(0, j));
            }
            //all columns, last row
            if(matrix[matrix.length - 1][j] == 1){
                matrix[matrix.length - 1][j] = -1;
                points.push(new Point(matrix.length - 1, j));
            }
        }

        //for each point in the stack, we do a DFS and keep adding neighboring ones we have not seen yet
        while(!points.isEmpty()){
            Point p = points.pop();

            //above
            if(p.x > 0 && matrix[p.x - 1][p.y] == 1){
                points.push(new Point(p.x - 1, p.y));
                matrix[p.x - 1][p.y] = -1;
            }

            //below
            if(p.x < matrix.length - 1 && matrix[p.x + 1][p.y] == 1){
                points.push(new Point(p.x + 1, p.y));
                matrix[p.x + 1][p.y] = -1;
            }

            //left
            if(p.y > 0 && matrix[p.x][p.y - 1] == 1){
                points.push(new Point(p.x, p.y - 1));
                matrix[p.x][p.y - 1] = -1;
            }

            //right
            if(p.y < matrix[0].length - 1 && matrix[p.x][p.y + 1] == 1){
                points.push(new Point(p.x, p.y + 1));
                matrix[p.x][p.y + 1] = -1;
            }
        }

        //walk the whole matrix and restore flipped ones while deleting the islands
        //all other remaining ones must be an island otherwise we would have visited them during the search
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == 1){
                    matrix[i][j] = 0;
                }
                if(matrix[i][j] == -1){
                    matrix[i][j] = 1;
                }
            }
        }
    }

    /**
     * Given a matrix, not necessarily square, and a threshold value, find the number of square submatrices
     * where the sum of all elements is equal to or bigger than target.
     * @param matrix the input matrix.
     * @param threshold the threshold value.
     * @return the number of square submatrices where the sum of all elements is equal to or bigger than target.
     */
    public static int numSquaresOfSumK(int[][] matrix, int threshold){
        int tot = 0;

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return tot;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                //sx,sy is top left corner of square matrix of size x size
                //ex,ey is bottom right corner of that matrix
                int sx = i, sy = j, ex = sx + 1, ey = sy + 1, size = 1;
                //we keep expanding size until allowed and calculate the sum of each bigger square matrix
                //with same top left corner
                //initially matrix is size 0x0 which is single element
                int curr = matrix[sx][sy];
                //single element is also valid submatrix
                if(curr >= threshold){
                    tot++;
                }
                //check for all bigger submatrices from here
                //we do not need to recalculate everytime the whole submatrix sum, we only need to add the sum
                //of new subrow and subcolumn to the previous result
                //careful we add the bottom right corner twice, so we subtract it once
                /*
                Example:
                123
                456
                789

                1 is a 1x1 square
                12,45 is a 2x2 square
                the whole matrix is a 3x3 square

                When we expand the current submatrix, we only include the next row and col up to current size

                example:
                12#
                45#
                ###

                we only need to calculate the cells marked with #, notice that summing all of them up will include
                the bottom right corner twice, so we need to subtract it once to have the correct result
                 */
                while(ex < rows && ey < cols){
                    //add new subrow values
                    for(int x = sx; x <= ex; x++){
                        curr += matrix[x][ey];
                    }

                    //add new subcol values
                    for(int y = sy; y <= ey; y++){
                        curr += matrix[ex][y];
                    }
                    //we add the bottom right twice, so subtract it
                    curr -= matrix[ex][ey];
                    //check sum and threshold
                    if(curr >= threshold){
                        tot++;
                    }
                    //increase to size+1 x size+1 matrix
                    size++;
                    ex = sx + size;
                    ey = sy + size;
                }
            }
        }

        return tot;
    }

    /**
     * Given a matrix, compute its prefix sum, that is for each cell, the sum of all elements before and above it
     * including itself.
     * @param matrix the input matrix.
     * @return the prefix sum matrix for the given input.
     */
    public static int[][] prefixSum(int matrix[][]) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return matrix;
        }

        int[][] prefix = new int[matrix.length][matrix[0].length];

        //top left never changes
        prefix[0][0] = matrix[0][0];

        //first row is sum as array
        for(int j = 1; j < matrix[0].length; j++) {
            prefix[0][j] = matrix[0][j] + prefix[0][j - 1];
        }

        //first col is sum as array
        for(int i = 1; i < matrix.length; i++) {
            prefix[i][0] = matrix[i][0] + prefix[i - 1][0];
        }

        //rest of matrix is sum of all elements above us + all elements left os us - sum in previous diagonal
        //since we would count that element twice (it appears in both all left and all above us)
        //as it is bottom right of smaller submatrix
        /*
        example matrix of all ones
        1 1
        1 1

        prefix is
        1 2
        2 4

        the bottom right adds himself = 1 + all above = 2 + all before = 2. This would give 5 as the previous diagonal
        element was already counted in both "all above" and "all before", we need therefore to remove it once
         */
        for(int i = 1; i < matrix.length; i++) {
            for(int j = 1; j < matrix[0].length; j++) {
                prefix[i][j] = matrix[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }

        return prefix;
    }

    /**
     * Given a matrix, compute its prefix sum, that is for each cell, the sum of all elements before and above it
     * including itself. Start from bottom right cell.
     * @param matrix the input matrix.
     * @return the prefix sum matrix for the given input.
     */
    public static int[][] prefixSumBottomRight(int matrix[][]) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return matrix;
        }

        int[][] prefix = new int[matrix.length][matrix[0].length];

        //bottom right never changes
        prefix[matrix.length - 1][matrix[0].length - 1] = matrix[matrix.length - 1][matrix[0].length - 1];

        //last row is sum as array
        for(int j = matrix[0].length - 2; j >= 0; j--) {
            prefix[matrix.length - 1][j] = matrix[matrix.length - 1][j] + prefix[matrix.length - 1][j + 1];
        }

        //last col is sum as array
        for(int i = matrix.length - 2; i >= 0; i--) {
            prefix[i][matrix[0].length - 1] = matrix[i][matrix[0].length - 1] + prefix[i + 1][matrix[0].length - 1];
        }

        for(int i = matrix.length - 2; i >= 0; i--) {
            for(int j = matrix[0].length - 2; j >= 0; j--) {
                prefix[i][j] = matrix[i][j] + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i + 1][j + 1];
            }
        }

        return prefix;
    }

    /**
     * Given a matrix, not necessarily square, and a threshold value, find the number of square submatrices
     * where the sum of all elements is equal to or bigger than target.
     * @param matrix the input matrix.
     * @param threshold the threshold value.
     * @return the number of square submatrices where the sum of all elements is equal to or bigger than target.
     */
    public static int numSquaresOfSumKDP(int[][] matrix, int threshold){
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }

        //calculate prefix sum matrix
        int[][] prefix = prefixSum(matrix);

        /*
        debug print prefix matrix
        for(int i = 0; i < prefix.length; i++){
            for(int j = 0; j < prefix[0].length; j++){
                System.out.print(prefix[i][j] + ", ");
            }
            System.out.println();
        }
        */

        int tot = 0;

        //for each cell, consider us as bottom right corner of a square of size K
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                //single element is 1x1 square
                if(matrix[i][j] >= threshold){
                    tot++;
                }
                //explore always bigger squares with us as bottom right corner
                //start at 1 which is 2x2 square
                int k = 1;
                //we stop as soon as the next square won't fit within bounds of this matrix
                while(i - k >= 0 && j - k >= 0){
                    /*
                    to calculate sum of submatrix of size K from its bottom right corner
                    we can use the prefix matrix values
                    however we need to perform some operations to find the sub-submatrix

                    Example:
                    123
                    456
                    789

                    9 is a 1x1 square
                    56,89 is a 2x2 square
                    the whole matrix is a 3x3 square

                    Therefore the prefix sum for cell 9 will be correct for the 3x3 matrix, but not the 2x2 one.
                    We can however reuse already computed data to retrieve the 2x2 sum from the 3x3 one.
                    We need to:
                    - subtract the sum of all elements outside of K bounds, for both rows and columns
                    that is row and column up to k - 1, so element 7 and 3
                    - if we subtracted both a row and column, include element in diagonal as we remember that
                    element in diagonal is counted twice in the prefix matrix and removed once. We are now doing the
                    inverse operation
                    that is add cell (k - 1,k - 1), so element 1

                    example:

                    ###
                    #56
                    #89

                    we need to get rid of all cells marked with #, however top left cell would be removed twice (once
                    when we remove its row and once when we remove its column), so we need to add it back one time to
                    have correct result

                    Since it's a square and we start looping on rows, we use rows as driver for the size adjustments
                     */
                    int prevRow = i - k - 1; //sum of all elements in this row OUT of size K from our origin (bottom right)
                    int prevCol = i - k - 1; //sum of all elements in this column OUT of size K from our origin (bottom right)

                    //prefix sum until current cell is in the prefix matrix
                    int submatrixKxKsum = prefix[i][j];
                    //remove if necessary the row values out of bound for size K
                    if(prevRow >= 0){
                        submatrixKxKsum -= prefix[prevRow][j];
                    }
                    //remove if necessary the column values out of bound for size K
                    if(prevCol >= 0){
                        submatrixKxKsum -= prefix[i][prevCol];
                    }
                    //if we can, add diagonal element on top left of square of size K + 1
                    if(prevRow >= 0 && prevCol >= 0){
                        submatrixKxKsum += prefix[prevRow][prevCol];
                    }
                    //sum of values in K+1 x K+1 square where we are bottom right
                    if (submatrixKxKsum >= threshold) {
                        tot++;
                    }
                    //increase size for next exploration
                    k++;
                }
            }
        }

        return tot;
    }

    /**
     * Given a matrix of characters and a word, find if the word appears in the matrix. The word can be constructed
     * ONLY by choosing left to right or top to bottom characters but NOT mixing the two.
     * @param matrix the available characters.
     * @param word the word to search for.
     * @return true if word appears in the matrix.
     */
    public static boolean wordSearchLRTB(char[][] matrix, String word){
        if(word == null || matrix == null ||
                word.length() == 0 ||
                matrix.length == 0 || matrix[0].length == 0 ||
                (word.length() > matrix.length && word.length() > matrix[0].length)){
            return false;
        }

        /*
        For each position in the matrix, if the character in that position matches the start of our string, we start
        two searches:
        - rest of the row
        - rest of the column
        to see whether the string appears in the matrix
         */
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                //if first character does not match, skip
                if(word.charAt(0) == matrix[i][j]){
                    //if string is one character, we just found it
                    if(word.length() == 1){
                        return true;
                    }
                    //if word is not too long for rest of row
                    if(word.length() <= matrix[0].length - j){
                        //walk rest of row and see if there's a match
                        int k = 1;
                        while(k <= word.length() && j + k < matrix[0].length){
                            if(word.charAt(k) == matrix[i][j + k]){
                                //initial character was matched at the beginning, must count that too!
                                if(k + 1 == word.length()){
                                    return true;
                                }
                                k++;
                            }
                            //no need to continue on mismatch
                            else{
                                break;
                            }
                        }
                    }
                    //if word is not too long for rest of column
                    if(word.length() <= matrix.length - i){
                        //walk rest of column and see if there's a match
                        int k = 1;
                        while(k <= word.length() && i + k < matrix.length){
                            if(word.charAt(k) == matrix[i + k][j]){
                                //initial character was matched at the beginning, must count that too!
                                if(k + 1 == word.length()){
                                    return true;
                                }
                                k++;
                            }
                            //no need to continue on mismatch
                            else{
                                break;
                            }
                        }
                    }
                }
            }
        }

        return false;
    }

    /**
     * Given two integers representing the rows and columns of a matrix, find in how many ways we can reach the bottom right
     * corner starting from top left and moving only right or down.
     * @param n number of rows.
     * @param m number of columns.
     * @return how many ways we can reach the bottom right corner starting from top left and moving only right or down.
     */
    public static int waysToTraverseGrid(int n, int m){
        if(n == 0 || m == 0){
            return 0;
        }

        int[][] waysForPoint = new int[n][m];
        //first cell (1x1) cannot be reached by moving as we're already there
        waysForPoint[0][0] = 0;
        //on the first column we can only go down, each cell can only be reached in one way
        for(int i = 1; i < n; i++){
            waysForPoint[i][0] = 1;
        }
        //on the first row we can only go right, each cell can only be reached in one way
        for(int j = 1; j < m; j++){
            waysForPoint[0][j] = 1;
        }
        //each other cell can be reached by the sum of ways the previous top and left cells can be reached
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                waysForPoint[i][j] = waysForPoint[i - 1][j] + waysForPoint[i][j - 1];
            }
        }

        return waysForPoint[n - 1][m - 1];
    }

    //helper for waysToTraverseGridCombinations calculates n!
    private static int factorial(int n){
        int res = 1;

        for(int i = 1; i <= n; i ++){
            res *= i;
        }

        return res;
    }

    /**
     * Given two integers representing the rows and columns of a matrix, find in how many ways we can reach the bottom right
     * corner starting from top left and moving only right or down.
     * @param n number of rows.
     * @param m number of columns.
     * @return how many ways we can reach the bottom right corner starting from top left and moving only right or down.
     */
    public static int waysToTraverseGridCombinations(int n, int m){
        //1x1 grid we cannot move any direction
        if(n < 2 || m < 2){
            return 0;
        }

        //(M+N)!/(M! * N!)
        //as in previous case, going all the way right or down is only one way
        //calculate the result for a smaller matrix which is the remainder after taking out top and left boundaries
        /*
        0111
        1###
        1###
        1###

        we only need to calculate values for # cells
         */
        int i = n - 1;
        int j = m - 1;

        return factorial(i + j) / (factorial(i) * factorial(j));
    }

    /**
     * Given a matrix, return an array which is the clockwise spiral visit starting from top left corner.
     * @param matrix the input matrix.
     * @return the clockwise spiral visit from top left corner.
     */
    public static int[] spiralVisit(int[][] matrix){
        if(matrix == null || matrix.length == 0){
            return new int[]{};
        }
        if(matrix[0].length == 0){
            return matrix[0];
        }

        //output is NxM array
        int[] spiral = new int[matrix.length * matrix[0].length];

        /*
        We walk the matrix in a spiral and always add the bounds working our way inside:
        - all of top: start row (left right) but start from NEXT column since we already added the first row
        element before (is first of column we just processed)
        at the very beginning we already are on the correct position for this row so we only update the column
        AFTER all other boundaries have been processed
        - add all of right: end column (top down) but start from NEXT row since we already added the first column
        element before (is last of row we just processed)
        - add all of bottom: end row (right left) but start from PREVIOUS column since we already added the last row
        element before (is last of column we just processed)
        - add all of left: start column (bottom up) but start from PREVIOUS row since we already added the last column
        element before (is first of row we just processed)

        we repeat this until all elements in the matrix have been processed
         */

        //startRow,endRow represent boundaries for ROWS inclusive for element we should add
        //so they are ALL elements in the current COLUMN we want to add
        //likewise for startCol,endCol
        int startRow = 0;
        int endRow = matrix.length - 1;
        int startCol = 0;
        int endCol = matrix[0].length - 1;
        //position in output array for next element we should add
        int pos = 0;

        //continue until we processed all element in input matrix
        while(pos < spiral.length){
            //top row left to right
            for(int i = startCol; i <= endCol; i++, pos++){
                spiral[pos] = matrix[startRow][i];
            }
            //right col top down
            //for this col, start from next element as we have already added first element of col (last of previous row)
            startRow++;
            for(int i = startRow; i <= endRow; i++, pos++){
                spiral[pos] = matrix[i][endCol];
            }
            //bottom row right left
            //for this row, start from previous element as we have already added last element of row (last of previous col)
            endCol--;
            for(int i = endCol; i >= startCol; i--, pos++){
                spiral[pos] = matrix[endRow][i];
            }
            //left col bottom up
            //for this col, start from previous element as we have already added last element of col (first of previous row)
            endRow--;
            for(int i = endRow; i >= startRow; i--, pos++){
                spiral[pos] = matrix[i][startCol];
            }
            //when we process next row, continue from next element as we have already added first element of row (first or previous col)
            startCol++;
        }

        return spiral;
    }

    /**
     * A toeplitz matrix is a matrix where all elements on the left to right diagonals are same.
     * Given a matrix return true if it is a toeplitz matrix.
     * @param matrix the given matrix.
     * @return true if the matrix is a toeplitz matrix.
     */
    public static boolean isToeplitz(int[][] matrix){
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }

        /*
        Since all elements on the left-right diagonals must be same, we just loop over all such diagonals
        and test whether all elements are same to the first, if not, we stop and return false.
        To do so, we must scan the first row until the previous to last element (last element is on a diagonal
        with itself only) AND also the first column from the second element until previous to last (first element
        is already considered in the diagonal from the first element in the first row, and last element
        is on a diagonal with itself only).
        If we scanned the whole matrix successfully, we return true.
         */

        //all diagonals for all elements in first row excluding last
        for(int i = matrix[0].length - 2; i >= 0; i--){
            int elem = matrix[0][i];
            int row = 1;
            int col = i + 1;
            while(row < matrix.length && col < matrix[0].length){
                if(matrix[row][col] != elem){
                    return false;
                }
                row++;
                col++;
            }
        }

        //all diagonals for all elements in first column excluding first and last
        for(int j = 1; j < matrix.length - 1; j++){
            int elem = matrix[j][0];
            int row = j + 1;
            int col = 1;
            while(row < matrix.length && col < matrix[0].length){
                if(matrix[row][col] != elem){
                    return false;
                }
                row++;
                col++;
            }
        }

        return true;
    }

    /**
     * Given a MxN matrix of 0s and 1s, return the shortest path from 0,0 to M-1,N-1 moving only up,down,left,right
     * and avoiding obstacles (1s). You can delete at most K obstacles.
     * @param grid the input matrix.
     * @param k the maximum number of obstacles that can be deleted.
     * @return the length of the shortest path from top left to bottom right corner deleting at most K obstacles.
     */
    public static int shortestPathWithMaxKDeletions(int[][] grid, int k){
        if(grid == null || grid[0].length == 0 || k < -1){
            throw new IllegalArgumentException("Invalid input");
        }

        int m = grid.length;
        int n = grid[0].length;

        /*
        Do BFS, but track amount of remaining deletions we have when visiting a cell. If another path reached this cell
        before us AND we have fewer deletions left, we are not the best path as someone was faster to here AND he has more
        possibilities to remove obstacles further down the road.

        Otherwise continue the search updating the deletions left everytime we encounter an obstacle.
         */
        int[][] visited = new int[m][n];
        for(int i = 0; i < m; i++){
            Arrays.fill(visited[i], -1);
        }

        Queue<Integer[]> q = new LinkedList<>();
        //i, j, current path length, deletions left
        q.add(new Integer[]{0,0,0,k});

        while(!q.isEmpty()){
            Integer[] curr = q.remove();

            int i = curr[0];
            int j = curr[1];
            int len = curr[2];
            int del = curr[3];

            //we must be within bounds
            if(i < 0 || i >= m || j < 0 || j >= n){
                continue;
            }

            //reached the end
            if(i == m - 1 && j == n - 1){
                return len;
            }

            //this cell is an obstacle, use a deletion...
            if(grid[i][j] == 1){
                del--;
            }

            //...but verify we are allowed to use that deletion AND another path hasn't reached here with MORE deletions left
            if(del < 0 || visited[i][j] > del){
                continue;
            }

            //set our remaining deletions on this cell
            visited[i][j] = del;

            //explore neighbors in the 4 directions
            q.add(new Integer[]{i - 1, j,len + 1, del});
            q.add(new Integer[]{i + 1, j,len + 1, del});
            q.add(new Integer[]{i, j - 1,len + 1, del});
            q.add(new Integer[]{i, j + 1,len + 1, del});

        }

        //no path possible
        return -1;
    }
}

NumSquaresOfSumKDPJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NumSquaresOfSumKDPJTests {

    int[][] matrix;
    int expected, threshold;

    @Test
    public void nullEmpty() {
        matrix = null;
        threshold = 0;
        expected = 0;
        assertEquals("null", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));

        matrix = new int[][]{};
        threshold = 0;
        expected = 0;
        assertEquals("empty", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));

        matrix = new int[][]{{}};
        threshold = 0;
        expected = 0;
        assertEquals("array", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));
    }

    @Test
    public void noMatch(){
        matrix = new int[][]{
                {1,1},
                {1,1}
        };
        threshold = 10;
        expected = 0;
        assertEquals("threshold too big", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));
    }

    @Test
    public void oneMatch(){
        matrix = new int[][]{
                {1,1},
                {1,1}
        };
        threshold = 4;
        expected = 1;
        assertEquals("one match", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));
    }

    @Test
    public void sample(){
        /*
        squares are:
        - 1x1 =  3,3,4,3,4
        - 2x2 = 1,3,2,1 - 3,3,1,1 - 3,4,1,3 - 4,1,3,4
         */
        matrix = new int[][]{
                {1,3,3,4,1},
                {2,1,1,3,4}
        };
        threshold = 3;
        expected = 9;
        assertEquals("sample1", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));

        /*
        squares are:
        - 1x1 =  3,3,4,3,4,3,3
        - 2x2 = 1,3,2,1 - 3,3,1,1 - 3,4,1,3 - 4,1,3,4
         */
        matrix = new int[][]{
                {1,3,3,4,1},
                {2,1,1,3,4},
                {3,3,1,1,1}
        };
        threshold = 3;
        expected = 18;
        assertEquals("sample2", expected, MatrixUtils.numSquaresOfSumKDP(matrix, threshold));
    }
}

NumSquaresOfSumKJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NumSquaresOfSumKJTests {

    int[][] matrix;
    int expected, threshold;

    @Test
    public void nullEmpty() {
        matrix = null;
        threshold = 0;
        expected = 0;
        assertEquals("null", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));

        matrix = new int[][]{};
        threshold = 0;
        expected = 0;
        assertEquals("empty", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));

        matrix = new int[][]{{}};
        threshold = 0;
        expected = 0;
        assertEquals("array", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));
    }

    @Test
    public void noMatch(){
        matrix = new int[][]{
                {1,1},
                {1,1}
        };
        threshold = 10;
        expected = 0;
        assertEquals("threshold too big", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));
    }

    @Test
    public void oneMatch(){
        matrix = new int[][]{
                {1,1},
                {1,1}
        };
        threshold = 4;
        expected = 1;
        assertEquals("one match", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));
    }

    @Test
    public void sample(){
        /*
        squares are:
        - 1x1 =  3,3,4,3,4
        - 2x2 = 1,3,2,1 - 3,3,1,1 - 3,4,1,3 - 4,1,3,4
         */
        matrix = new int[][]{
                {1,3,3,4,1},
                {2,1,1,3,4}
        };
        threshold = 3;
        expected = 9;
        assertEquals("sample1", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));

        /*
        squares are:
        - 1x1 =  3,3,4,3,4,3,3
        - 2x2 = 1,3,2,1 - 3,3,1,1 - 3,4,1,3 - 4,1,3,4
         */
        matrix = new int[][]{
                {1,3,3,4,1},
                {2,1,1,3,4},
                {3,3,1,1,1}
        };
        threshold = 3;
        expected = 18;
        assertEquals("sample2", expected, MatrixUtils.numSquaresOfSumK(matrix, threshold));
    }
}

Pair.java

package com.blogspot.groglogs.structures;

import java.util.Objects;

/**
 * Defines a Pair of objects.
 * @param <T> type of the first object.
 * @param <E> type of the second object.
 */
public class Pair<T, E> {

    private T first;
    private E second;

    public Pair(){
        this.first = null;
        this.second = null;
    }

    public Pair(T first, E second){
        this.first = first;
        this.second = second;
    }

    public T getFirst(){
        return this.first;
    }

    public E getSecond(){
        return this.second;
    }

    public void setFirst(T first){
        this.first = first;
    }

    public void setSecond(E second){
        this.second = second;
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.first, this.second);
    }

    @Override
    public boolean equals(Object o) {
        if(this == o){
            return true;
        }

        if(!(o instanceof Pair)){
            return false;
        }

        //the other pair could be typed differently, we accept it since the equals later will factor these types in
        Pair<?,?> other = (Pair<?,?>)o;

        //Objects.equals logic is: this.first == null ? other.first == null : this.first.equals(other.first)
        //which guarantees null safety AND factors in the typechecking by using the relevant equals logic of our field types
        return Objects.equals(this.first, other.first) && Objects.equals(this.second, other.second);
    }
}

Point.java

package com.blogspot.groglogs.structures;

import java.util.Objects;

public class Point {
    public int x, y, val;

    public Point(int x, int y, int val){
        this.x = x;
        this.y = y;
        this.val = val;
    }

    public Point(int x, int y){
        this.x = x;
        this.y = y;
        this.val = -1;
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.x, this.y, this.val);
    }

    @Override
    public boolean equals(Object o) {
        if(this == o){
            return true;
        }

        if(!(o instanceof Point)){
            return false;
        }

        Point other = (Point)o;

        return this.x == other.x && this.y == other.y && this.val == other.val;
    }
}

SpiralVisitJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class SpiralVisitJTests {

    int[][] matrix;
    int[] visit;

    @Test
    public void nullEmpty() {
        matrix = null;
        visit = new int[]{};
        assertArrayEquals("null", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{};
        visit = new int[]{};
        assertArrayEquals("empty", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{{}};
        visit = new int[]{};
        assertArrayEquals("array", visit, MatrixUtils.spiralVisit(matrix));
    }

    @Test
    public void square() {
        matrix = new int[][]{{1}};
        visit = new int[]{1};
        assertArrayEquals("1x1", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{
                {1,2},
                {3,4}
        };
        visit = new int[]{1,2,4,3};
        assertArrayEquals("2x2", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{
                {1,2,3},
                {4,5,6},
                {7,8,9}
        };
        visit = new int[]{1,2,3,6,9,8,7,4,5};
        assertArrayEquals("3x3", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12},
                {13,14,15,16}
        };
        visit = new int[]{1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10};
        assertArrayEquals("4x4", visit, MatrixUtils.spiralVisit(matrix));
    }

    @Test
    public void rectangle() {
        matrix = new int[][]{
                {1,2,3},
                {4,5,6}
        };
        visit = new int[]{1,2,3,6,5,4};
        assertArrayEquals("2x3", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{
                {1,2},
                {3,4},
                {5,6}
        };
        visit = new int[]{1,2,4,6,5,3};
        assertArrayEquals("3x2", visit, MatrixUtils.spiralVisit(matrix));

        matrix = new int[][]{
                {1,2,3,4,5},
                {6,7,8,9,10},
                {11,12,13,14,15},
                {16,17,18,19,20}
        };
        visit = new int[]{1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12};
        assertArrayEquals("5x4", visit, MatrixUtils.spiralVisit(matrix));
    }
}

ToeplitzMatrixJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class ToeplitzMatrixJTests {

    int[][] matrix;

    @Test
    public void nullEmpty() {
        matrix = null;
        assertFalse("null", MatrixUtils.isToeplitz(matrix));

        matrix = new int[][]{};
        assertFalse("empty", MatrixUtils.isToeplitz(matrix));

        matrix = new int[][]{{}};
        assertFalse("array", MatrixUtils.isToeplitz(matrix));
    }

    @Test
    public void square() {
        matrix = new int[][]{
                {1,2,3},
                {4,1,2},
                {5,4,1}
        };
        assertTrue("3x3, toeplitz", MatrixUtils.isToeplitz(matrix));

        matrix = new int[][]{
                {1,2,3},
                {1,2,3},
                {1,2,3}
        };
        assertFalse("3x3, not toeplitz", MatrixUtils.isToeplitz(matrix));
    }

    @Test
    public void rectangle() {
        matrix = new int[][]{
                {1,2,3,4},
                {4,1,2,3},
                {5,4,1,2}
        };
        assertTrue("3x4, toeplitz", MatrixUtils.isToeplitz(matrix));

        matrix = new int[][]{
                {1,2,3,4},
                {1,2,3,4},
                {1,2,3,4}
        };
        assertFalse("3x4, not toeplitz", MatrixUtils.isToeplitz(matrix));
    }
}

WaysToTraverseGridJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class WaysToTraverseGridJTests {

    int n, m, expected;

    @Test
    public void nullEmpty() {
        n = 0;
        m = 0;
        expected = 0;
        assertEquals("null", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("null combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));

        n = 0;
        m = 1;
        expected = 0;
        assertEquals("empty n", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("empty n combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));

        n = 1;
        m = 0;
        expected = 0;
        assertEquals("empty m", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("empty m combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));
    }

    @Test
    public void square() {
        n = 1;
        m = 1;
        expected = 0;
        assertEquals("1x1", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("1x1 combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));

        n = 2;
        m = 2;
        expected = 2;
        assertEquals("2x2", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("2x2 combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));

        n = 3;
        m = 3;
        expected = 6;
        assertEquals("3x3", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("3x3 combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));
    }

    @Test
    public void rectangle() {
        n = 2;
        m = 3;
        expected = 3;
        assertEquals("2x3", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("2x3 combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));

        n = 3;
        m = 2;
        expected = 3;
        assertEquals("3x2", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("3x2 combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));

        n = 4;
        m = 3;
        expected = 10;
        assertEquals("4x3", expected, MatrixUtils.waysToTraverseGrid(n, m));
        assertEquals("4x3 combinations", expected, MatrixUtils.waysToTraverseGridCombinations(n, m));
    }
}

WordSearchLRTBJTests.java

package com.blogspot.groglogs.test.matrixutils;

import com.blogspot.groglogs.matrixutils.MatrixUtils;
import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class WordSearchLRTBJTests {

    char[][] matrix;
    String word;

    @Test
    public void nullEmpty() {
        matrix = null;
        word = null;
        assertFalse("null", MatrixUtils.wordSearchLRTB(matrix, word));

        matrix = null;
        word = "asd";
        assertFalse("null matrix", MatrixUtils.wordSearchLRTB(matrix, word));

        matrix = new char[][]{{'c'}, {'a'}};
        word = null;
        assertFalse("null word", MatrixUtils.wordSearchLRTB(matrix, word));

        matrix = new char[][]{};
        word = "asd";
        assertFalse("empty matrix", MatrixUtils.wordSearchLRTB(matrix, word));

        matrix = new char[][]{{'c'}};
        word = "asd";
        assertFalse("array matrix", MatrixUtils.wordSearchLRTB(matrix, word));

        matrix = new char[][]{{'c'}, {'a'}};
        word = "";
        assertFalse("empty word", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void wordTooLong(){
        matrix = new char[][]{{'c'}, {'a'}};
        word = "asd";
        assertFalse("word too long", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void oneCharacter(){
        matrix = new char[][]{{'c', 'b'}, {'a', 'd'}};
        word = "d";
        assertTrue("one characters", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void wordNotInMatrix(){
        matrix = new char[][]{
                {'c', 'a', 'r'},
                {'a', 's', 'd'},
                {'r', 'f', 's'}
        };
        word = "lol";
        assertFalse("word not in matrix", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void wordInRow(){
        matrix = new char[][]{
                {'c', 'a', 'r'},
                {'a', 's', 'd'},
                {'r', 'f', 's'}
        };
        word = "asd";
        assertTrue("word in row", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void wordInCol(){
        matrix = new char[][]{
                {'c', 'a', 'r'},
                {'a', 's', 'd'},
                {'r', 'f', 's'}
        };
        word = "asf";
        assertTrue("word in col", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void wordInSubmatrix(){
        matrix = new char[][]{
                {'c', 'a', 'r'},
                {'a', 's', 'd'},
                {'r', 'f', 's'}
        };
        word = "ds";
        assertTrue("word in submatrix", MatrixUtils.wordSearchLRTB(matrix, word));
    }

    @Test
    public void sample(){
        matrix = new char[][]{
                {'F', 'A', 'C', 'I'},
                {'O', 'B', 'Q', 'P'},
                {'A', 'N', 'O', 'B'},
                {'M', 'A', 'S', 'S'},
        };
        word = "FOAM";
        assertTrue("FOAM", MatrixUtils.wordSearchLRTB(matrix, word));

        word = "MASS";
        assertTrue("MASS", MatrixUtils.wordSearchLRTB(matrix, word));

        word = "OS";
        assertTrue("OS", MatrixUtils.wordSearchLRTB(matrix, word));

        word = "OB";
        assertTrue("OB", MatrixUtils.wordSearchLRTB(matrix, word));

        word = "FACE";
        assertFalse("FACE", MatrixUtils.wordSearchLRTB(matrix, word));
    }
}

Full description at:

• https://groglogs.blogspot.com/2021/09/java-matrix-path-with-at-most-k.html
• https://groglogs.blogspot.com/2021/07/java-toeplitz-matrix.html
• https://groglogs.blogspot.com/2021/07/java-matrix-spiral-visit.html
• https://groglogs.blogspot.com/2021/06/java-ways-to-traverse-grid.html
• https://groglogs.blogspot.com/2021/06/java-find-word-in-matrix.html
• https://groglogs.blogspot.com/2021/06/java-find-all-square-submatrices-of-sum.html
• https://groglogs.blogspot.com/2021/06/java-delete-islands.html
• https://groglogs.blogspot.com/2021/06/java-test-if-two-matrices-are-equals.html
• https://groglogs.blogspot.com/2021/06/java-find-pair-of-values-from-two.html
• https://groglogs.blogspot.com/2021/06/java-find-value-in-sorted-matrix.html
• http://groglogs.blogspot.ch/2018/05/java-find-biggest-square-in-matrix.html
• http://groglogs.blogspot.ch/2017/10/java-biggest-matrix-subgroup-value.html