Visit spiral matrix - Oct. 12, 2020 - 7:00 PM mock interview

VisitSpiralMatrix.cs

using System;
using System.Collections.Generic;

/*
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k

Input:nums = [1,1,1], k = 2
Output: 2
brute force: O(N^2) subarray
O(n) linear one 
precompute - prefix sum 
sum, count -> hashmap 
 -> prefix sum -> hashmap prefix - k -> hashmap -> + value
 from index = 0 -> d
 [1, 1, 1]
 -> 

*/

/*
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

first row -> 1, 2, 3 -> last column 6, 9, last row 8, 7, first column -> 4, 5

extra space -> mark visit - go through row -> column -> row -> column -> 
-> right -> down -> 
0, 1, 2, 3
0 - go right, 1 go down, 2 go left, 3 go up

using hashset -> 


Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

*/

class Solution
{
    static void Main(string[] args)
    {
        var rows = 3; 
       var matrix =  new int[rows][];
        //for(int i = 0; i < rows; i++)
        //    matrix[i] = new int[3];
        matrix[0] =  new int[]{1, 2, 3, 4};
        matrix[1] = new int[]{5,6,7, 8};
        matrix[2] = new int[]{9, 10, 11, 12};
        
        var list = VisitSpiralOrder(matrix);
        
        foreach(var item in list )
        {
            Console.WriteLine(item); 
        }

    }
    
    // 7:24 - 7 :40
    public static List<int> VisitSpiralOrder(int[][] matrix)
    {
        if(matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
        {
            return new List<int>(); 
        }
        
        var rows = matrix.Length; 
        var columns = matrix[0].Length; 
        
        var total = rows * columns; 
        var index = 0; 
        
        // 0 - go right, 1 go down, 2 go left, 3 go up
        var directionRow = new int[]{0, 1, 0, -1};
        var directionCol = new int[]{1, 0, -1, 0};
        
        var direction = 0; 
        var list = new List<int>(); 
        
        var row = 0; 
        var col = -1; // 0,0
        
        // mark visit 
        var hashSet = new HashSet<long>();  // row, col -> row * columns + col
        
        while(index < total)  
        {
            var currentRow = row + directionRow[direction];
            var currentCol = col + directionCol[direction];
            
            if(currentRow < rows && currentRow >= 0 &&
               currentCol < columns && currentCol >=0 && !hashSet.Contains(currentRow * columns + currentCol))
            {
                list.Add(matrix[currentRow][currentCol]); 
                // mark visit
                hashSet.Add(currentRow * columns + currentCol); 
                
                // reset row, col
                row = currentRow;
                col = currentCol;
                
                index++; 
            }
            else 
            {
                direction++;
                direction = direction % 4; // next direction
            }                                  
        }
        
        return list; 
    }
}

// https://codereview.stackexchange.com/questions/185935/leetcode-54-spiral-matrix

//time complexity: O(N * M) N - rows, M columns
//space complexity : O(N * M) - hashset -> all hashset