Leetcode discuss: 463. Island Perimeter

July 14, 2020

Here is the link.

C# using DFS and two hashset to remove duplicate edge count

July 14, 2020

463. Island Perimeter

Introduction

It is my first algorithm in Leetcode mock interivew phone screen. I spent over 40 minutes to write a solution, and then passed online judge.

Design issue
The challenge is to design unique key for each edge, in order for me to remove duplicate ones, I need to specify a key using integer to represent edges of rectangle.

The idea is to use left start point for horizontal edge, and top point for vertical edge.

Also map horizontal edges to integer values smaller than 100 * 200 + 100. Map vertical edges to integer values bigger than all horizontal edges, so there is no overlap, zero possibility to mix horizontal edge with vertical edge.

If the above issues are resolved, all others are standard BFS/ DFS solution with base case, range check, visited mark etc.

public class Solution {
    public int IslandPerimeter(int[][] grid) {
        // apply DFS to visit all connected nodes
        // use hashset<int> to add all unique edges first
        // use hashset<int> to record all duplicate edge next
        // all edges will have unique id - 
        // horizontal - row, col - start point
        // vertical - row, col - up point
        // 100 - map row * 100 + col -> unique value 
        // return difference between two hashset's count value - unique one and duplicate ones
        if(grid == null || grid[0] == null || grid[0].Length == 0)
        {
            return 0; 
        }
        
        var rows = grid.Length; 
        var columns = grid[0].Length; 
        
        var hashSet = new HashSet<int>(); 
        var duplicateSet = new HashSet<int>(); 
        
        for(int row = 0; row < rows; row++)
        {
            for(int col = 0; col < columns; col++)
            {
                var current = grid[row][col];
                if(current != 1)
                {
                    continue; 
                }                
                
                runDFSSearch(grid, hashSet, duplicateSet, row, col);
                break;
            }
        }
        
        return hashSet.Count - duplicateSet.Count; 
    }
    
    /// Run BFS algorithm
    private void runDFSSearch(int[][] grid, HashSet<int> set, HashSet<int> duplicate, int row, int col)
    {
        var rows = grid.Length; 
        var columns = grid[0].Length; 
        
        if(row < 0 || row >= rows || col < 0 || col >= columns || grid[row][col] != 1)
        {
            return; 
        }
        
        // starting from top-left corner, horizontal first, vertical next
        // horizontal left->right
        // vertical top->down
        var keyEdges = new int[]{
            getHorizontalNumber(row, col), 
            getHorizontalNumber(row + 1, col), 
            getVerticalNumber(row, col),             
            getVerticalNumber(row, col + 1)};
        
        foreach(var item in keyEdges)
        {
            if(set.Contains(item))
            {
                duplicate.Add(item);
            }
            
            set.Add(item); 
        }
        
        // mark visited
        grid[row][col] = 2;  
        
        runDFSSearch(grid, set, duplicate, row + 1, col); 
        runDFSSearch(grid, set, duplicate, row - 1, col); 
        runDFSSearch(grid, set, duplicate, row, col - 1); 
        runDFSSearch(grid, set, duplicate, row, col + 1);         
    }
    
    // Do not overlap vertical number
    // all < 100 * 200 + 100
    private int getHorizontalNumber(int row, int col)
    {
        return row * 200 + col; 
    }
    
    // Do not overlap horizontal number
    // all > maximum of horizontal number < 200 * 100 + 20000
    // 
    private int getVerticalNumber(int row, int col)
    {
        return 200 * 100 + 20000 + (row * 200 + col);
    }
}