Number of Squareful Arrays solution and explanation
Google
8 more videos on this problem
NUMBER OF SQUAREFUL ARRAYS | LEETCODE 996 | PYTHON BACKTRACKING SOLUTIONCracking FAANG · 14:40 · 2K views
996. Number of Squareful Arrays (Leetcode Hard)Programming Live with Larry · 31:37 · 2K views
【每日一题】996. Number of Squareful Arrays, 12/10/2020Huifeng Guan · 19:11 · 1K views
NUMBER OF SQUAREFUL ARRAYS | LEETCODE 996 | HARD | PYTHONAniPy · 15:57 · 630 views
Leetcode 996. Number of Squareful Arrays (backtracking)LetsCode · 16:13 · 557 views
猩猩的乐园 Leetcode 996 Number of Squareful Arrays猩猩的乐园 · 10:55 · 468 views
996. Number of Squareful ArraysJust Coding, with Jie · 8:10 · 299 views
LeetCode 996: Number of Squareful ArraysAlitaCode · 32:08 · 35 views
No Sound Leetcode 996: Number of Squareful ArraysExtremeProgrammer · 2:22 · 12 views
The problem
An array is squareful if the sum of every pair of adjacent elements is a perfect square.
Given an integer array nums, return the number of permutations of nums that are squareful.
Two permutations perm1 and perm2 are different if there is some index i such that perm1[i] != perm2[i].
Example 1:
Input: nums = [1,17,8] Output: 2 Explanation: [1,8,17] and [17,8,1] are the valid permutations.
Example 2:
Input: nums = [2,2,2] Output: 1
Constraints:
1 <= nums.length <= 120 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an array of integers and must count how many permutations exist such that the sum of every pair of adjacent elements is a perfect square. Arrays may contain duplicates, so permutations that produce the same ordering should only be counted once.
Approach 1: Backtracking with HashSet (O(n!) time, O(n) space)
This approach generates permutations using depth‑first search while enforcing the square condition during construction. First, sort the array so duplicate handling becomes straightforward. During recursion, maintain a visited array and only place a number if it hasn't been used and if the sum with the previously placed element forms a perfect square. A small optimization is precomputing which pairs form perfect squares or checking with int(sqrt(a+b))^2 == a+b. Duplicate permutations are avoided by skipping equal elements that haven't been used in the previous position of the recursion layer. The recursion tree prunes heavily because many pairs will not produce perfect squares, making it much faster than naive permutation generation.
This method directly models the permutation constraint and is often the first correct solution candidates arrive at. It relies on recursion and pruning techniques common in backtracking problems. Space usage stays O(n) for the recursion stack and visited tracking.
Approach 2: Dynamic Programming with Bitmasking (O(n2 * 2n) time, O(n * 2n) space)
This approach treats the problem as building permutations incrementally using subset DP. Represent which elements are already used with a bitmask of length n. Define dp[mask][i] as the number of valid permutations using elements in mask where the last element is index i. For each state, try extending the permutation with an unused index j. The transition is valid only if nums[i] + nums[j] forms a perfect square.
Before the DP loop, build an adjacency matrix showing which pairs produce square sums. This avoids recomputing square checks during transitions. Duplicate values require careful handling: when selecting an element, skip indices where the previous identical value hasn't been used in the mask. Bitmask DP systematically explores subsets and ensures each state is computed once, which is why the complexity becomes O(n2 * 2n). This technique is common in permutation counting and Hamiltonian‑path style problems using dynamic programming and bitmasking.
Recommended for interviews: Start with the backtracking solution because it mirrors the problem statement: build permutations while enforcing the square constraint. Interviewers often expect pruning logic and duplicate handling. The bitmask DP approach demonstrates stronger algorithmic depth and familiarity with subset DP patterns, which can stand out in senior‑level interviews.
Approach 1: Approach 1: Backtracking with HashSet
This approach uses backtracking to generate all permutations of the array. For each permutation, it checks if the sum of every pair of adjacent elements is a perfect square. To optimize, a HashSet is used to avoid duplicates.
from math import isqrt
from itertools import permutations
def is_squareful(perm):
for i in range(len(perm) - 1):
if isqrt(perm[i] + perm[i + 1]) ** 2 != perm[i] + perm[i + 1]:
return False
return True
def numSquarefulPerms(nums):
perms = set(permutations(nums))
return sum(is_squareful(perm) for perm in perms)
# Example usage
nums = [1, 17, 8]
print(numSquarefulPerms(nums)) # Output: 2import java.util.HashSet;
import java.util.Arrays;
public class SquarefulArrays {
public static boolean isPerfectSquare(int x) {
int s = (int) Math.sqrt(x);
return s * s == x;
}
public static int numSquarefulPerms(int[] nums) {
Arrays.sort(nums);
return countPerms(nums, new boolean[nums.length], new HashSet<>());
}
private static int countPerms(int[] nums, boolean[] used, HashSet<String> perms) {
int total = 0;
StringBuilder perm = new StringBuilder();
for (int i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
used[i] = true;
perm.append(nums[i]);
if (perm.length() == nums.length * 2 - 1) {
if (!perms.contains(perm.toString())) {
if (isPermutationSquareful(perm.toString(), nums.length)) {
total += 1;
perms.add(perm.toString());
}
}
} else {
total += countPerms(nums, used, perms);
}
perm.deleteCharAt(perm.length() - 1);
used[i] = false;
}
return total;
}
private static boolean isPermutationSquareful(String perm, int length) {
for (int i = 0; i < length - 1; i++) {
char a = perm.charAt(i * 2), b = perm.charAt(i * 2 + 2);
int sum = (a - '0') + (b - '0');
if (!isPerfectSquare(sum)) return false;
}
return true;
}
public static void main(String[] args) {
int[] nums = {1, 17, 8};
System.out.println(numSquarefulPerms(nums)); // Output: 2
}
}The solution generates all unique permutations using itertools.permutations and checks each for squarefulness. It counts those that pass the check. A helper function is_squareful verifies if adjacent pairs are perfect squares.
Time Complexity: O(n!), where n is the length of nums, due to generating all permutations.
Space Complexity: O(n!), for storing permutations in a set.
Approach 2: Approach 2: Dynamic Programming with Bitmasking
This approach uses dynamic programming with bitmasking to generate permutations. A bitmask represents used elements. Recursion with memoization checks if a permutation is squareful.
from math import isqrt
def is_perfect_square(x):
root = isqrt(x)
return root * root == x
class Solution:
def numSquarefulPerms(self, nums):
self.memo = {}
return self.dfs(nums, -1, 0, [False]*len(nums))
def dfs(self, nums, last_index, used, state):
if used == (1 << len(nums)) - 1:
return 1
if (last_index, used) in self.memo:
return self.memo[(last_index, used)]
count = 0
for i in range(len(nums)):
if state[i] or (i > 0 and nums[i] == nums[i - 1] and not state[i - 1]):
continue
if last_index == -1 or is_perfect_square(nums[last_index] + nums[i]):
state[i] = True
count += self.dfs(nums, i, used | (1 << i), state)
state[i] = False
self.memo[(last_index, used)] = count
return count
# Example usage:
# nums = [1, 17, 8]
# sol = Solution()
# print(sol.numSquarefulPerms(nums)) # Output: 2#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
using namespace std;
bool isPerfectSquare(int x) {
int s = sqrt(x);
return s * s == x;
}
int dfs(vector<int>& nums, int last, int used, vector<bool>& state, unordered_map<int, int>& dp) {
if (used == (1 << nums.size()) - 1) return 1;
if (dp.count(used)) return dp[used];
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (state[i] || (i > 0 && nums[i] == nums[i - 1] && !state[i - 1])) continue;
if (last == -1 || isPerfectSquare(nums[last] + nums[i])) {
state[i] = true;
count += dfs(nums, i, used | (1 << i), state, dp);
state[i] = false;
}
}
return dp[used] = count;
}
int numSquarefulPerms(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> state(nums.size(), false);
unordered_map<int, int> dp;
return dfs(nums, -1, 0, state, dp);
}
int main() {
vector<int> nums = {1, 17, 8};
cout << numSquarefulPerms(nums) << endl; // Output: 2
return 0;
}This solution uses a recursive function with bitmasking to represent which elements have been used. The helper function dfs is called repeatedly to explore all combinations. Memoization is implemented to reduce repeated computations.
Time Complexity: O(n * 2^n), due to subsets of elements explored.
Space Complexity: O(n * 2^n), due to memoization of states.
Approach 3: Default Approach
func numSquarefulPerms(nums []int) (ans int) {
n := len(nums)
f := make([][]int, 1<<n)
for i := range f {
f[i] = make([]int, n)
}
for j := range nums {
f[1<<j][j] = 1
}
for i := 0; i < 1<<n; i++ {
for j := 0; j < n; j++ {
if i>>j&1 == 1 {
for k := 0; k < n; k++ {
if i>>k&1 == 1 && k != j {
s := nums[j] + nums[k]
t := int(math.Sqrt(float64(s)))
if t*t == s {
f[i][j] += f[i^(1<<j)][k]
}
}
}
}
}
}
for j := 0; j < n; j++ {
ans += f[(1<<n)-1][j]
}
g := [13]int{1}
for i := 1; i < 13; i++ {
g[i] = g[i-1] * i
}
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
for _, v := range cnt {
ans /= g[v]
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with HashSet | Time Complexity: O(n!), where n is the length of nums, due to generating all permutations. |
| Approach 2: Dynamic Programming with Bitmasking | Time Complexity: O(n * 2^n), due to subsets of elements explored. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with HashSet | O(n!) | O(n) | Good for understanding the constraint directly and implementing pruning with recursion |
| Dynamic Programming with Bitmask | O(n² · 2ⁿ) | O(n · 2ⁿ) | Preferred when counting permutations with state reuse and subset DP optimization |
Frequently asked questions
Is Number of Squareful Arrays easy or hard?
LeetCode classifies Number of Squareful Arrays as a Hard problem. The difficulty comes from combining permutation generation, duplicate handling, and perfect-square constraints, often requiring either careful backtracking pruning or bitmask dynamic programming.
Number of Squareful Arrays Python/Java solution
Python and Java solutions typically implement DFS backtracking with a visited array and sorted input to skip duplicates. The DP variant uses a 2D array indexed by bitmask and last position, iterating through valid square-sum neighbors to update states.
How to solve Number of Squareful Arrays in O(n^2 * 2^n)?
Use subset dynamic programming with bitmasks. Define dp[mask][i] as the number of valid permutations using elements in mask and ending at index i. Precompute which pairs of values sum to perfect squares, then transition by adding unused indices whose sums satisfy the square condition.
What is the best approach for Number of Squareful Arrays?
The most robust solution uses dynamic programming with bitmasking. It models the problem as building permutations of indices and stores intermediate results in dp[mask][i]. This reduces repeated work and runs in O(n^2 * 2^n) time, which is efficient for the constraint n ≤ 12. Backtracking with pruning is also widely accepted in interviews.
Is Number of Squareful Arrays asked at Google/Amazon/Meta?
Permutation counting and subset dynamic programming problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving bitmask DP, Hamiltonian paths, or constraint-based permutations are common patterns tested in senior algorithm rounds.
What data structure is used in Number of Squareful Arrays?
Typical implementations use arrays, hash sets for duplicate handling, recursion stacks for backtracking, and bitmasks for subset representation. In the optimized solution, a 2D DP table dp[mask][i] stores counts of permutations ending at index i.
What is the time complexity of Number of Squareful Arrays?
Backtracking solutions can take up to O(n!) time because they explore permutations, although pruning removes many invalid branches. The optimized approach uses bitmask dynamic programming with O(n^2 * 2^n) time and O(n * 2^n) space by reusing results for previously computed subsets.