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] <= 109The key idea in #996 Number of Squareful Arrays is to count permutations of the array where the sum of every pair of adjacent elements forms a perfect square. A brute-force permutation approach would generate all possible permutations and validate each one, but this quickly becomes inefficient.
A better strategy is to model the problem as a graph. Treat each number as a node and connect two nodes if their sum is a perfect square. Then, use backtracking or bitmask dynamic programming to build valid permutations by traversing this graph while tracking visited elements.
Handling duplicates is important to avoid counting identical permutations multiple times. Sorting the array and skipping repeated elements during recursion helps eliminate duplicates. A common implementation uses DFS + bitmask where the bitmask represents which indices are already used in the current permutation.
The precomputation of valid square pairs significantly reduces repeated work during recursion. This combination of graph construction, backtracking, and state compression leads to an efficient solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with graph adjacency | O(N! ) in worst case, but pruned by square constraints | O(N) |
| Bitmask Dynamic Programming + DFS | O(N * 2^N) | O(N * 2^N) |
The Code Skool
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving permutations with constraints, graph modeling, and bitmask dynamic programming are common in FAANG-style interviews. While this exact question may not always appear, the techniques used here are frequently tested.
The optimal approach builds a graph where edges connect numbers whose sum forms a perfect square. Then backtracking or DFS with bitmasking is used to construct valid permutations while tracking visited indices. This reduces unnecessary checks compared to brute-force permutation generation.
If the input array contains duplicate numbers, naive permutation generation may count identical permutations multiple times. Sorting the array and skipping repeated values during recursion ensures that only unique permutations are counted.
A graph representation using adjacency lists works well to store which numbers can follow each other. Additionally, a bitmask or boolean visited array is used to track used elements during DFS or backtracking.