1038. Number of Squareful Arrays
My accepted Python solution to LeetCode problem 1038, Number of Squareful Arrays, running in 4ms.
- Difficulty: Hard
- Python
- Runtime 4ms
- Memory 17.5MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 4ms, memory 17.5MB, accepted 2026-01-01.
class Solution:
def numSquarefulPerms(self, nums: List[int]) -> int:
from math import isqrt
from collections import Counter
def is_square(n):
r = isqrt(n)
return r * r == n
n = len(nums)
count = Counter(nums)
# Build graph: which numbers can be adjacent
graph = {x: [] for x in count}
for x in count:
for y in count:
if is_square(x + y):
graph[x].append(y)
result = 0
def backtrack(last, remaining):
nonlocal result
if remaining == 0:
result += 1
return
for next_num in graph[last]:
if count[next_num] > 0:
count[next_num] -= 1
backtrack(next_num, remaining - 1)
count[next_num] += 1
# Try each unique number as starting point
for start in count:
count[start] -= 1
backtrack(start, n - 1)
count[start] += 1
return result