DCC - 08/08/2024|| Matrix🔥
Approach and Intuition\n\n1. Initialization:\n   - You initialize the answer array to store the coordinates of the cells visited in spiral order.\n   - You mark
### Approach and Intuition\n\n1. **Initialization**:\n   - You initialize the `answer` array to store the coordinates of the cells visited in spiral order.\n   - You mark the starting cell `(rStart, cStart)` in the `answer` array.\n   - A `visited` matrix is used to keep track of which cells have been visited to avoid revisiting them.\n\n2. **Helper Function**:\n   - The `helper` function is a recursive function that performs the spiral traversal.\n   - It starts from the current position `(curr_row, curr_col)` and fills the `answer` array with the coordinates of the cells visited in the current spiral path.\n   - `counter` keeps track of the current step size for each direction (right, down, left, up).\n   - `ind` is the index in the `answer` array where the next coordinate should be placed.\n\n3. **Spiral Movement**:\n   - The function first moves right (`col = col + 1`) for `counter` steps.\n   - Then it moves down (`row = row + 1`) for `counter` steps.\n   - `counter` is incremented to account for the increased step size.\n   - Then it moves left (`col = col - 1`) for `counter` steps.\n   - Finally, it moves up (`row = row - 1`) for `counter` steps.\n   - `counter` is incremented again to account for the increased step size in the next iteration.\n\n4. **Boundary and Validity Checks**:\n   - At each step, the function checks if the new position is within the bounds of the matrix and if it has not been visited before.\n   - If the position is valid, it is added to the `answer` array, and the `visited` matrix is updated.\n\n5. **Recursion**:\n   - The `helper` function calls itself recursively with the new position and updated parameters until all cells in the matrix are visited.\n\n### Complexity Analysis\n\n1. **Time Complexity**:\n   - The helper function traverses each cell in the matrix exactly once.\n   - The time complexity is \\(O(rows * cols)\\) since each cell is processed a constant number of times.\n\n2. **Space Complexity**:\n   - The primary space usage is the `answer` array and the `visited` matrix, each of size \\(O(rows * cols)\\).\n   - The recursion depth can be up to the number of layers in the spiral, which is \\(O(sqrt(rows*cols))\\) in the worst case, but this is generally negligible compared to the size of the matrices.\n\n### Explanation of Each Part of Your Code\n\n1. **Main Function `spiralMatrixIII`**:\n   ```java\n   public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {\n       int answer[][] = new int[rows * cols][2];\n       answer[0][0] = rStart;\n       answer[0][1] = cStart;\n       boolean[][] visited = new boolean[rows][cols];\n       helper(rStart, cStart, rows, cols, answer, visited, 1, 1);\n       return answer;\n   }\n   ```\n   - Initializes the `answer` array and the `visited` matrix.\n   - Starts the spiral traversal with the `helper` function.\n\n2. **Helper Function**:\n   ```java\n   void helper(int curr_row, int curr_col, int rows, int cols, int[][] answer, boolean[][] visited, int counter, int ind) {\n       int row = curr_row;\n       int col = curr_col;\n       boolean flag = false;\n   ```\n\n3. **Move Right**:\n   ```java\n   for (int i = 1; i <= counter; i++) {\n       row = row;\n       col = col + 1;\n       if (col < cols && col >= 0 && row >= 0 && row < rows) {\n           flag = true;\n           answer[ind][0] = row;\n           answer[ind][1] = col;\n           visited[row][col] = true;\n           ind++;\n       }\n   }\n   ```\n   - Moves right `counter` steps.\n   - Checks if the position is valid and updates the `answer` and `visited` arrays.\n\n4. **Move Down**:\n   ```java\n   for (int i = 1; i <= counter; i++) {\n       row = row + 1;\n       col = col;\n       if (row < rows && row >= 0 && col >= 0 && col < cols) {\n           flag = true;\n           answer[ind][0] = row;\n           answer[ind][1] = col;\n           visited[row][col] = true;\n           ind++;\n       }\n   }\n   counter++;\n   ```\n\n5. **Move Left**:\n   ```java\n   for (int i = 1; i <= counter; i++) {\n       row = row;\n       col = col - 1;\n       if (col >= 0 && col < cols && row >= 0 && row < rows) {\n           flag = true;\n           answer[ind][0] = row;\n           answer[ind][1] = col;\n           visited[row][col] = true;\n           ind++;\n       }\n   }\n   ```\n\n6. **Move Up**:\n   ```java\n   for (int i = 1; i <= counter; i++) {\n       row = row - 1;\n       col = col;\n       if (row >= 0 && row < rows && col >= 0 && col < cols) {\n           flag = true;\n           answer[ind][0] = row;\n           answer[ind][1] = col;\n           visited[row][col] = true;\n           ind++;\n       }\n   }\n   ```\n\n7. **Recursive Call**:\n   ```java\n   if (flag)\n       helper(row, col, rows, cols, answer, visited, counter + 1, ind);\n   ```\n\n### Summary\n\n- Your code implements a recursive approach to traverse a matrix in a spiral order, starting from a given cell.\n- It correctly handles boundary checks and updates the result and visited arrays.\n- The time and space complexities are both \\(O(rows \\times cols)\\), making the approach efficient for this problem.\n\n# Code\n```\nclass Solution {\n    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {\n\n        int answer[][] = new int[rows*cols][2];\n        answer[0][0] = rStart;\n        answer[0][1] = cStart\n        helper(rStart,cStart,rows,cols,answer,visited,1 , 1);\n        return answer;\n\n        \n    }\n    void helper(int curr_row, int curr_col , int rows, int cols , int[][] answer , boolean[][] visited , int counter,int ind){\n        \n         int row = curr_row;\n         int col = curr_col;\n         boolean flag = false;\n        for(int i=1;i<=counter;i++){\n\n            row = row;\n            col = col+1;\n            if(col<cols && col>=0 && row>=0 && row<rows){\n                flag = true;\n                answer[ind][0]=row;\n                answer[ind][1]=col;\n                visited[row][col]=true;\n                ind++;\n            } \n        }\n        for(int i=1;i<=counter;i++){\n\n            row = row+1;\n            col = col;\n            if(row<rows && row>=0 && col>=0 && col<cols){\n                flag = true;\n                answer[ind][0] = row;\n                answer[ind][1] = col;\n                 visited[row][col]=true;\n                ind++;\n            }\n\n        }\n        counter++;\n\n        for(int i=1;i<=counter;i++){\n\n            row=row;\n            col=col-1;\n            if(col>=0 && col<cols &&  row>=0 && row<rows){\n                flag = true;\n                answer[ind][0]=row;\n                answer[ind][1]=col;\n                 visited[row][col]=true;\n                ind++;\n            }\n        }\n\n        for(int i=1;i<=counter;i++){\n\n            row = row-1;\n            col = col;\n            if(row>=0 && row<rows && col>=0 && col<cols){\n                flag = true;\n                answer[ind][0]=row;\n                answer[ind][1]=col;\n                visited[row][col]=true;\n                ind++;\n            }\n        }\n        if(flag)\n        helper(row,col,rows,cols,answer,visited,counter+1,ind);\n\n\n\n        \n    }\n}\n```
['Array', 'Matrix', 'Java']