Algorithm: Leetcode Contest 409

3242. Design Neighbor Sum Service

Solution

class neighborSum {
    int[][] grid;
    public neighborSum(int[][] grid) {
        this.grid = grid;
    }
    
    public int adjacentSum(int value) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == value) {
                    int sum = 0;
                    if (i > 0) {
                        sum += grid[i - 1][j];
                    }
                    if (j > 0) {
                        sum += grid[i][j - 1];
                    }
                    if (i + 1 < grid.length) {
                        sum += grid[i + 1][j];
                    }
                    if (j + 1 < grid[0].length) {
                        sum += grid[i][j + 1];
                    }
                    
                    
                    return sum;
                }
            }
        }
        return 0;
    }
    
    public int diagonalSum(int value) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == value) {
                    int sum = 0;
                    if (i > 0 && j > 0) {
                        sum += grid[i - 1][j - 1];
                    }
                    if (i > 0 && j + 1 < grid[0].length) {
                        sum += grid[i - 1][j + 1];
                    }
                    if (i + 1 < grid.length && j > 0) {
                        sum += grid[i + 1][j - 1];
                    }
                    if (i + 1 < grid.length && j + 1 < grid[0].length) {
                        sum += grid[i + 1][j + 1];
                    }

                    return sum;
                }
            }
        }
        
        return 0;
    }
}

/**
 * Your neighborSum object will be instantiated and called as such:
 * neighborSum obj = new neighborSum(grid);
 * int param_1 = obj.adjacentSum(value);
 * int param_2 = obj.diagonalSum(value);
 */

Retro

• encountered some issue when handle the diagonal sum, use the most straightforward way can avoid some issue from “smarty” solution

3243. Shortest Distance After Road Addition Queries I

Solution

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
       List<List<Node>> adj = new ArrayList<List<Node>>();
        for(int i = 0; i < n; i++) {
            adj.add(new ArrayList<Node>());
        }

        for(int i = 0; i < n - 1; i++) {
            adj.get(i).add(new Node(i + 1, 1));
        }

        int[] res = new int[queries.length];
        int counter = 0;
        for(int[] query: queries) {
            adj.get(query[0]).add(new Node(query[1], 1));
            res[counter++] = dijkstra(adj, 0);
        }

        return res;
    }

    private int dijkstra(List<List<Node>> adj, int src) {
        int[] dist = new int[adj.size()];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> a.value - b.value);
        dist[src] = 0;
        pq.add(new Node(0, 0));

        Node curNode = null;
        while(!pq.isEmpty()) {
            curNode = pq.poll();

            if (curNode.value > dist[curNode.node]) {
                continue;
            } 

            for(Node next: adj.get(curNode.node)) {
                if (dist[next.node] > dist[curNode.node] + next.value) {
                    dist[next.node] = dist[curNode.node] + next.value;
                    pq.add(new Node(next.node, dist[next.node]));
                }
            }
            
        }

        return dist[dist.length - 1];
    }

    private class Node {
        int node;
        int value;

        public Node(int i, int j) {
            node = i;
            value = j;
        }
    }
}

Retro

• when it comes to the shortest path, always think about “Dijkstra” solution
• Dijkstra solution is using Priority Queue
• a simple way of initiating Priority Queue new PriorityQueue<Node>((a, b) -> xxx)
• how to initiate a list of list. how to handle the generic issues.