/* Input: 2D Array
 * 1 2 3
 * 4 5 6
 * 7 8 9
 *
 * Output: 1 2 3 5 9 8 7 4 5
 */

public void spiral(int[][] mat)
{
    int[][] rcSigns = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // The Direction Change Pattern Of The Spiral
    StringBuilder indices = new StringBuilder(); // Stores All Indexes Printed To The Screen (With A Space Between Each Index)
    int numCount = 0; // Number Of Indices In The "indices" variable

    int rPat = 0, cPat = 0; // Current Spiral Sign/Pattern
    int rSign = rcSigns[0][0], cSign = rcSigns[0][1]
    int r = 0, c = 0; // Row Index | Column Index
    int nums = mat.length * mat[0].length; // Number of Elements In The 2D Matrix

    while(numCount < nums)
    {
        String index = r + "" + c;
        indices.append(index);
        numCount++;
        System.out.println(mat[r][c]);

        r += rSign;
        c += cSign;

        if(r == 0 && c == mat[r].length - 1 ||
           r == mat.length - 1 && c == mat[r].length - 1 ||
           r == mat.length - 1 && c == 0 ||
           indices.contain(index))
        {
            // Go Back One Index
            r -= rSign;
            c -= cSign;

            // Change The Direction of the Spiral Pattern
            // I Use (Mod 4) Because There Are 4 Possible Patterns And When I Am At Index 3 And Increment By One, I Want To Go Back To
            // Index 0, And Restart The Spiral Direction Patterns
            rSign = rcSigns[++rPat % 4][0];
            cSign = rcSigns[++cPat % 4][1];

            // Increment In New Spiral Direction
            r += rSign;
            c += cSign;
        }
    }
}