Construct the Lexicographically Largest Valid Sequence LeetCode solution in Java

1
class Solution {
2

3
  public int[] constructDistancedSequence(int n) {
4
    int[] ans = new int[n * 2 - 1];
5
    boolean[] visited = new boolean[n + 1];
6
    calc(0, ans, visited, n);
7
    return ans;
8
  }
9

10
  private boolean calc(int index, int[] ans, boolean[] visited, int n) {
11
    if (index == ans.length) {
12
      return true;
13
    }
14
    if (ans[index] != 0)
15
      return calc(
16
          index + 1, ans, visited,
17
          n); // value already assigned in this position. So go ahead with the next index.
18
    else {
19
      // we start from n to 1 since we need to find out the lexicographically largest sequence.
20
      for (int i = n; i >= 1; i--) {
21
        if (visited[i]) continue;
22
        visited[i] = true;
23
        ans[index] = i;
24
        if (i == 1) {
25
          if (calc(index + 1, ans, visited, n)) return true;
26
        } else if (index + i < ans.length && ans[index + i] == 0) {
27
          ans[i + index] =
28
              i; // assigning the second occurence of i in the desired position i.e, (current index
29
          // + i )
30
          if (calc(index + 1, ans, visited, n))
31
            return true; // largest possible sequence satisfying the given conditions found.
32
          ans[index + i] = 0;
33
        }
34
        ans[index] = 0;
35
        visited[i] = false;
36
      }
37
    }
38
    return false;
39
  }
40
}