Skip to content

444. Sequence Reconstruction 👎

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
 public:
  bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    if (seqs.empty())
      return false;

    const int n = org.size();
    vector<vector<int>> graph(n);
    vector<int> inDegrees(n);

    // Build the graph.
    for (const vector<int>& seq : seqs) {
      if (seq.size() == 1 && seq[0] < 1 || seq[0] > n)
        return false;
      for (int i = 0; i + 1 < seq.size(); ++i) {
        const int u = seq[i];
        const int v = seq[i + 1];
        if (u < 1 || u > n || v < 1 || v > n)
          return false;
        graph[u - 1].push_back(v - 1);
        ++inDegrees[v - 1];
      }
    }

    // Perform topological sorting.
    queue<int> q;

    for (int i = 0; i < n; ++i)
      if (inDegrees[i] == 0)
        q.push(i);

    int i = 0;  // org's index

    while (!q.empty()) {
      if (q.size() > 1)
        return false;
      const int u = q.front();
      q.pop();
      if (u != org[i] - 1)
        return false;
      ++i;
      for (const int v : graph[u])
        if (--inDegrees[v] == 0)
          q.push(v);
    }

    return i == n;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
  public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
    if (seqs.isEmpty())
      return false;

    final int n = org.length;
    List<Integer>[] graph = new List[n];
    int[] inDegrees = new int[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    // Build the graph.
    for (List<Integer> seq : seqs) {
      if (seq.size() == 1 && seq.get(0) < 1 || seq.get(0) > n)
        return false;
      for (int i = 0; i + 1 < seq.size(); ++i) {
        final int u = seq.get(i);
        final int v = seq.get(i + 1);
        if (u < 1 || u > n || v < 1 || v > n)
          return false;
        graph[u - 1].add(v - 1);
        ++inDegrees[v - 1];
      }
    }

    // Perform topological sorting.
    Queue<Integer> q = IntStream.range(0, n)
                           .filter(i -> inDegrees[i] == 0)
                           .boxed()
                           .collect(Collectors.toCollection(ArrayDeque::new));

    int i = 0; // org's index

    while (!q.isEmpty()) {
      if (q.size() > 1)
        return false;
      final int u = q.poll();
      if (u != org[i] - 1)
        return false;
      ++i;
      for (final int v : graph[u])
        if (--inDegrees[v] == 0)
          q.offer(v);
    }

    return i == n;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
  def sequenceReconstruction(
      self,
      org: list[int],
      seqs: list[list[int]],
  ) -> bool:
    if not seqs:
      return False

    n = len(org)
    graph = [[] for _ in range(n)]
    inDegrees = [0] * n

    # Build the graph.
    for seq in seqs:
      if len(seq) == 1 and seq[0] < 1 or seq[0] > n:
        return False
      for u, v in zip(seq, seq[1:]):
        if u < 1 or u > n or v < 1 or v > n:
          return False
        graph[u - 1].append(v - 1)
        inDegrees[v - 1] += 1

    # Perform topological sorting.
    q = collections.deque([i for i, d in enumerate(inDegrees) if d == 0])
    i = 0  # org's index

    while q:
      if len(q) > 1:
        return False
      u = q.popleft()
      if u != org[i] - 1:
        return False
      i += 1
      for v in graph[u]:
        inDegrees[v] -= 1
        if inDegrees[v] == 0:
          q.append(v)

    return i == n