Longest Common Subpath LeetCode solution in Java

1
class Solution {
2

3
  // mod
4
  long mod = (long) (Math.pow(10, 11) + 3);
5

6
  long p = 100003;
7

8
  long p_i[];
9

10
  public int longestCommonSubpath(int n, int[][] paths) {
11

12
    // min length will be 1
13
    int min = 1;
14

15
    // max length will be the (path of min length)
16

17
    int max = Integer.MAX_VALUE;
18

19
    for (int path[] : paths) {
20
      max = Math.min(max, path.length);
21
    }
22

23
    // now we will pre calculate the the powers of base
24
    // and upto max only bcoz that's the longest subarray
25
    // we are going to deal with
26
    p_i = new long[max + 1];
27

28
    p_i[0] = 1;
29

30
    for (int i = 1; i <= max; i++) {
31
      // mod multiplication
32
      p_i[i] = mulmod(p_i[i - 1], p, mod);
33
    }
34

35
    int ans = 0;
36

37
    while (min <= max) {
38

39
      int mid = (min + max) / 2;
40

41
      if (solve(mid, paths)) {
42
        // if this length satisfies
43
        // we are moving to right
44
        // checking length greater than this
45
        ans = mid;
46
        min = mid + 1;
47
      } else {
48
        // else smaller
49
        max = mid - 1;
50
      }
51
    }
52

53
    return ans;
54
  }
55

56
  public boolean solve(int len, int paths[][]) {
57

58
    Map<Long, Long> map = new HashMap<>();
59

60
    // now for each path we are going to calculate the
61
    // hash value for each subpath of length -> len
62
    // and store the frequency of hash in map
63
    // and if for a hash value the frequency equals
64
    // paths.length it means it exists in all path array
65
    // so return true
66

67
    for (int path[] : paths) {
68

69
      long hash = 0l;
70

71
      // we are using a set for storing hash value of particular len for
72
      // each path beacuse there is a possibility
73
      // that a subpath repeats multiple times
74
      // in a path so it directly updating in map
75
      // will lead to wrong count
76
      Set<Long> set = new HashSet<>();
77

78
      // hash is calculated as
79
      // let's say len is 3
80
      // (p^3 * (path[0]+1)) + (p^2 * (path[1]+1)) + (p^1 * (path[2] + 1))
81

82
      // now when we are moving forward
83
      // and we need to update the hash value
84
      // we can do it like
85
      // delete (p^3 * (path[index-len]+1)) from prev_hash
86
      // so now the hash will become ->
87
      // (p^2 * (path[1]+1)) + (p^1 * (path[2] + 1))
88
      // and then multiply prev_hash by p
89
      // (p^3 * (path[1]+1)) + (p^2 * (path[2] + 1))
90
      // now add (p^1 * (path[3]+1))
91
      // so hash becomes->
92
      // (p^3 * (path[1]+1)) + (p^2 * (path[2] + 1)) + (p^1 * (path[3]+1))
93

94
      // using this way we avoid calculating invmod
95
      // so easier to implement
96

97
      for (int i = 0; i < len; i++) {
98
        hash = (hash + mulmod(p_i[len - i], (path[i] + 1), mod)) % mod;
99
      }
100

101
      set.add(hash);
102

103
      for (int i = len; i < path.length; i++) {
104
        long new_hash = (hash - mulmod(p_i[len], path[i - len] + 1, mod) + mod) % mod;
105
        new_hash = mulmod(new_hash, p, mod);
106
        new_hash = (new_hash + mulmod(p_i[1], path[i] + 1, mod)) % mod;
107
        hash = new_hash;
108
        set.add(new_hash);
109
      }
110

111
      // now for all the hash values in the set we will update the count
112
      // in the map
113
      for (long hsh : set) {
114
        map.put(hsh, map.getOrDefault(hsh, 0l) + 1l);
115
        if (map.get(hsh) == paths.length) {
116
          return true;
117
        }
118
      }
119
    }
120

121
    return false;
122
  }
123

124
  public long pow(long a, long b, int mod) {
125

126
    long val = a * 1l;
127

128
    long ans = 1l;
129

130
    while (b > 0) {
131
      if ((b & 1) == 1) {
132
        ans = mulmod(ans, val, mod);
133
      }
134
      val = mulmod(val, val, mod);
135
      b = b >> 1;
136
    }
137

138
    return ans % mod;
139
  }
140

141
  long mulmod(long a, long b, long mod) {
142
    return ((a % mod) * (b % mod)) % mod;
143
  }
144
}