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.

Description Solution Video 14:40

996. Number of Squareful Arrays

Hard51.9% acceptance2 companies

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 <= 12
0 <= nums[i] <= 10⁹

Asked at 2 companies

Apple

Google

Topics

14:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

996. Number of Squareful Arrays

Asked at 2 companies

Topics

Similar problems