All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : February 16, 2025
Last updated : February 16, 2025
Related Topics : Array, Backtracking
Acceptance Rate : 73.54 %
Added a parameter check to see if we've made use of our "1" insert since the prompt tells us that it will appear once in the output array. This is in contrast to V1 where instead we would allow the recursion to fully propogate the OUTPUT array and check if any values were unused
class Solution:
def helper(self, output: List[int], curr_indx: int, pot_vals: List[int]) -> List[int] | bool :
# The check for if there are pot_vals remaining is to check
# whether multiple "1"s were used
if curr_indx >= len(output) :
return output if not pot_vals else False
if output[curr_indx] :
return self.helper(output, curr_indx + 1, pot_vals)
len_potvals = len(pot_vals)
for i in range(len_potvals - 1, -1, -1) :
# This part is quite inefficient due to it popping and inserting causing many O(n)
# operations but is somewhat needed in order to keep pot_vals sorted when
# parsing the potential answers
if curr_indx + pot_vals[i] < len(output) and not output[curr_indx + pot_vals[i]] :
curr = pot_vals.pop(i)
output[curr_indx] = curr
output[curr_indx + curr] = curr
pot_result = self.helper(output, curr_indx + 1, pot_vals)
# if returns a list, then answer found
# if returns bool FALSE, then invalid case
if pot_result :
return output
pot_vals.insert(i, curr)
output[curr_indx] = 0
output[curr_indx + curr] = 0
# Insert the "1" case since it appears once
output[curr_indx] = 1
pot_result = self.helper(output, curr_indx + 1, pot_vals)
if pot_result :
return pot_result
output[curr_indx] = 0
return False
def constructDistancedSequence(self, n: int) -> List[int]:
output = [0] * (n + n - 1)
pot_vals = list(range(2, n + 1))
return self.helper(output, 0, pot_vals)class Solution:
def helper(self,
output: List[int],
curr_indx: int,
pot_vals: List[int],
one_used: bool = False) -> List[int] | bool :
if curr_indx >= len(output) :
return output
if output[curr_indx] :
return self.helper(output, curr_indx + 1, pot_vals, one_used)
len_potvals = len(pot_vals)
for i in range(len_potvals - 1, -1, -1) :
# This part is quite inefficient due to it popping and inserting causing many O(n)
# operations but is somewhat needed in order to keep pot_vals sorted when
# parsing the potential answers
if curr_indx + pot_vals[i] < len(output) and not output[curr_indx + pot_vals[i]] :
curr = pot_vals.pop(i)
output[curr_indx] = curr
output[curr_indx + curr] = curr
pot_result = self.helper(output, curr_indx + 1, pot_vals, one_used)
# if returns a list, then answer found
# if returns bool FALSE, then invalid case
if pot_result :
return output
pot_vals.insert(i, curr)
output[curr_indx] = 0
output[curr_indx + curr] = 0
# Insert the "1" case since it appears once
if not one_used :
output[curr_indx] = 1
pot_result = self.helper(output, curr_indx + 1, pot_vals, True)
if pot_result :
return pot_result
output[curr_indx] = 0
return False
def constructDistancedSequence(self, n: int) -> List[int]:
output = [0] * (n + n - 1)
pot_vals = list(range(2, n + 1))
return self.helper(output, 0, pot_vals)