Largest Color Value in a Directed Graph LeetCode solution in Java

1
class Solution {
2
  private int max;
3
  private Map<Integer, Map<Character, Integer>> memo;
4
  private boolean hasCycle;
5

6
  public int largestPathValue(String colors, int[][] edges) {
7
    Map<Integer, List<Integer>> map = new HashMap<>();
8

9
    for (int edge[] : edges) {
10
      List<Integer> list = map.getOrDefault(edge[0], new ArrayList<>());
11
      list.add(edge[1]);
12
      map.put(edge[0], list);
13
    }
14

15
    max = -1;
16
    memo = new HashMap<>();
17

18
    boolean visited[] = new boolean[colors.length()];
19
    hasCycle = false;
20

21
    for (int i = 0; i < colors.length(); i++) {
22
      dfs(i, map, colors, visited);
23

24
      if (hasCycle) {
25
        return -1;
26
      }
27
    }
28

29
    return max;
30
  }
31

32
  private Map<Character, Integer> dfs(
33
      int curr, Map<Integer, List<Integer>> map, String colors, boolean visited[]) {
34
    if (visited[curr]) {
35
      hasCycle = true;
36
      return new HashMap<>();
37
    }
38

39
    if (memo.get(curr) != null) {
40
      return memo.get(curr);
41
    }
42

43
    visited[curr] = true;
44
    List<Integer> list = map.get(curr);
45
    Map<Character, Integer> currMap = new HashMap<>();
46

47
    if (list != null && !list.isEmpty()) {
48
      for (int i : list) {
49
        Map<Character, Integer> resMap = dfs(i, map, colors, visited);
50

51
        if (hasCycle) {
52
          return currMap;
53
        }
54

55
        for (char c : resMap.keySet()) {
56
          int val = resMap.get(c);
57
          int currVal = currMap.getOrDefault(c, 0);
58
          currVal = Math.max(currVal, val);
59
          currMap.put(c, currVal);
60
          max = Math.max(currVal, max);
61
        }
62
      }
63
    }
64

65
    int currentNodeColorCount = currMap.getOrDefault(colors.charAt(curr), 0);
66
    currMap.put(colors.charAt(curr), currentNodeColorCount + 1);
67

68
    max = Math.max(currentNodeColorCount + 1, max);
69

70
    visited[curr] = false;
71
    memo.put(curr, currMap);
72
    return currMap;
73
  }
74
}