851. Loud and Rich

Link

Solution

First solution: Find each target's return value with DFS.

if will check all the pair in richer every time. so it is not efficient.

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int N = quiet.length;
        int[] ret = new int[N];
        for(int i = 0; i < N ; i++){
            ret[i] = -1;
        }
        for(int i = 0; i < N; i++){
            if(ret[i] == -1){
                dfs(richer, quiet, ret, i);
            }
        }
        return ret;
    }
    
    public void dfs(int[][] richer, int[] quiet, int[] ret, int i){
        
        if(ret[i] != -1){
            return;
        }
        
        ret[i] = i;
        //check all the pair in richer
        for(int[] ri : richer){
            int rich = ri[0];
            int poor = ri[1];
            if(poor == i){
                dfs(richer, quiet, ret, rich);
                if(quiet[ret[i]] > quiet[ret[rich]]){
                    ret[i] = ret[rich];
                }
            }
        }
    }
}

Second Solution: Use HashMap to replace the richer

 public int[] loudAndRich(int[][] richer, int[] quiet) {
        int N = quiet.length;
        int[] ret = new int[N];
        Arrays.fill(ret, -1);
        
        HashMap<Integer, List<Integer>> richer2 = new HashMap<>();
        
        for(int[] ri : richer){
            richer2.compute(ri[1], (k,v)->{
               if(v == null) 
               {
                   ArrayList<Integer> list = new ArrayList<>();
                   list.add(ri[0]);
                   return list;
               }
                v.add(ri[0]);
                return v;
            });
        }
        
        
        for(int i = 0; i < N; i++){
            if(ret[i] == -1){
                dfs(richer2, quiet, ret, i);
            }
        }
        return ret;
    }
    
    public void dfs(HashMap<Integer, List<Integer>> richer, int[] quiet, int[] ret, int i){
        
        if(ret[i] != -1){
            return;
        }
        
        ret[i] = i;
        if(richer.get(i) == null){
            return;
        }
        for(int rich : richer.get(i)){
            dfs(richer, quiet, ret, rich);
            if(quiet[ret[i]] > quiet[ret[rich]]){
                ret[i] = ret[rich];
            }
        }
    }