Number of Squareful Arrays
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach generates every unique permutation of the input array nums. For each generated permutation, it then checks if it satisfies the "squareful" property. The number of such valid permutations is counted.
Algorithm
- Define a function to generate all unique permutations of
nums. This can be done with backtracking. Sortnumsfirst to handle duplicates. - Store all generated unique permutations in a list.
- Initialize a counter
squareful_countto 0. - Iterate through each permutation in the list.
- For each permutation, check if it's squareful by iterating from the first to the second-to-last element and verifying that the sum of each adjacent pair is a perfect square.
- If a permutation is squareful, increment
squareful_count. - Return
squareful_count.
Walkthrough
The core of this method is a backtracking algorithm to generate all unique permutations. To handle duplicate numbers in nums, the array is first sorted. During backtracking, we add a rule to skip an element if it's the same as the previous one and the previous one hasn't been used in the current path. This ensures each unique permutation is generated only once.
A helper function isSquareful iterates through a given permutation and checks if the sum of every adjacent pair of elements is a perfect square. Another helper isPerfectSquare checks if a number is a perfect square. The main function orchestrates this: generate all permutations, then loop through them, check each one, and count the valid ones.
// This is a conceptual snippet. A full implementation would be too long and inefficient.public int numSquarefulPerms(int[] nums) { List<List<Integer>> allPermutations = new ArrayList<>(); // 1. Generate all unique permutations of nums // ... (implementation of permutation generation) int count = 0; // 2. Iterate and check each permutation for (List<Integer> p : allPermutations) { if (isSquareful(p)) { count++; } } return count;} private boolean isSquareful(List<Integer> p) { for (int i = 0; i < p.size() - 1; i++) { if (!isPerfectSquare(p.get(i) + p.get(i+1))) { return false; } } return true;} private boolean isPerfectSquare(int n) { if (n < 0) return false; int sqrt = (int) Math.sqrt(n); return sqrt * sqrt == n;}Complexity
Time
O(N! * N). Generating all unique permutations of `N` elements takes `O(N! * N)` time. For each of the (up to) `N!` permutations, we perform a check that takes `O(N)` time. This is prohibitively slow for `N=12`.
Space
O(N! * N). We need to store all permutations. The recursion depth for generation is `O(N)`, but the storage for the results dominates.
Trade-offs
Pros
Simple to understand conceptually.
Cons
Extremely inefficient in both time and space.
Not feasible for the given constraints (
Nup to 12).
This approach avoids generating all permutations upfront. Instead, it builds permutations one element at a time using backtracking (DFS). The "squareful" condition is checked as each new element is added. If adding an element violates the condition, that entire branch of the search is pruned, leading to significant performance improvement.
Algorithm
- Count the frequencies of each number in
numsand store them in a hash map. - Initialize a result counter to 0.
- Implement a recursive backtracking function, say
dfs(path). - Base Case: If
path.size()equals the total number of elementsN, a valid permutation is found. Increment the result counter and return. - Recursive Step: Iterate through each unique number
numfrom the frequency map. - If the count of
numis greater than 0: a. Check if the path is empty or ifpath.getLast() + numis a perfect square. b. If the condition holds, addnumto the path, decrement its count in the map, and make a recursive call:dfs(path). c. Backtrack: After the call returns, removenumfrom the path and restore its count in the map. - Start the process by calling
dfswith an empty path. - Return the result counter.
Walkthrough
We use a recursive DFS function to build the permutations. To handle duplicates efficiently, we first count the frequency of each number in nums and store it in a map.
The DFS function explores adding the next number to the current partial permutation. The state of the recursion can be represented by the partial permutation being built.
At each step of the recursion, we iterate through the available numbers (those with a count > 0 in the frequency map).
Before adding a number, we check if it forms a perfect square sum with the last element of the current partial permutation. If it does (or if the permutation is empty), we add the number, decrement its frequency, and recurse.
After the recursive call returns, we backtrack by removing the number and restoring its frequency.
The base case for the recursion is when the permutation's length equals N. At this point, we've found a valid squareful permutation, so we increment a global counter.
class Solution { int count = 0; Map<Integer, Integer> freqMap = new HashMap<>(); int n; public int numSquarefulPerms(int[] nums) { this.n = nums.length; if (n == 0) return 0; for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } dfs(new ArrayList<>()); return count; } private void dfs(List<Integer> currentPath) { if (currentPath.size() == n) { count++; return; } for (int nextNum : freqMap.keySet()) { if (freqMap.get(nextNum) > 0) { if (currentPath.isEmpty() || isPerfectSquare(currentPath.get(currentPath.size() - 1) + nextNum)) { currentPath.add(nextNum); freqMap.put(nextNum, freqMap.get(nextNum) - 1); dfs(currentPath); freqMap.put(nextNum, freqMap.get(nextNum) + 1); currentPath.remove(currentPath.size() - 1); } } } } private boolean isPerfectSquare(long num) { if (num < 0) return false; long sqrt = (long) Math.sqrt(num); return sqrt * sqrt == num; }}Complexity
Time
O(N!). In the worst-case scenario (where many pairs sum to perfect squares), the algorithm explores a number of paths proportional to `N!`. However, the pruning is very effective in practice, making it much faster than the theoretical worst case.
Space
O(N). The space is dominated by the recursion stack depth, which is at most `N`, and the frequency map, which stores at most `N` unique numbers.
Trade-offs
Pros
Drastically more efficient than brute-force.
Feasible for the given constraints.
Space efficient.
Cons
The complexity is still exponential, but this is inherent to permutation-style problems.
This approach models the problem as finding the number of Hamiltonian paths in a graph. The unique numbers from the input array are the vertices. An edge exists between two vertices if their sum is a perfect square. The problem then becomes counting paths of length N that visit each number according to its frequency.
Algorithm
- Create a frequency map of numbers in
nums. - Create an adjacency list
graphwhere vertices are unique numbers fromnums. - For every pair of unique numbers
(u, v), ifu + vis a perfect square, add an edge fromutovandvtouin the graph. - Initialize a result counter to 0.
- Implement a recursive
dfs(node, path_len)function. - Base Case: If
path_len == N, increment the result counter and return. - Recursive Step: For each neighbor
vofnodein thegraph: a. If the count ofvin the frequency map is > 0: b. Decrement the count ofv, and calldfs(v, path_len + 1). c. Backtrack: Increment the count ofv. - To start the process, iterate through each unique number
uas a potential starting node. For eachu, decrement its count, calldfs(u, 1), and then backtrack by restoring its count. - Return the result counter.
Walkthrough
First, we pre-process the input. We build a frequency map of the numbers in nums.
Then, we construct a graph where vertices are the unique numbers. We iterate through all pairs of unique numbers (u, v) and add an edge between them if u + v is a perfect square. This graph is stored as an adjacency list.
With the graph and frequencies, we perform a DFS (backtracking search). The search aims to find paths of length N.
The DFS function takes the current node u and the current path length as arguments.
It explores all neighbors v of u. If v is available (its count in the frequency map is > 0), we "visit" it by decrementing its count, and recurse with dfs(v, pathLength + 1).
After the recursive call, we backtrack by restoring the count of v.
The base case is when the path length reaches N, at which point we've found a valid Hamiltonian path, and we increment our total count.
To start the search, we iterate through each unique number, treat it as a starting node, and initiate a DFS from it.
class Solution { Map<Integer, Integer> freqMap = new HashMap<>(); Map<Integer, List<Integer>> graph = new HashMap<>(); int count = 0; int n; public int numSquarefulPerms(int[] nums) { this.n = nums.length; if (n == 0) return 0; for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } for (int u : freqMap.keySet()) { graph.put(u, new ArrayList<>()); } for (int u : freqMap.keySet()) { for (int v : freqMap.keySet()) { if (isPerfectSquare((long)u + v)) { graph.get(u).add(v); } } } for (int startNode : freqMap.keySet()) { freqMap.put(startNode, freqMap.get(startNode) - 1); dfs(startNode, 1); freqMap.put(startNode, freqMap.get(startNode) + 1); } return count; } private void dfs(int u, int pathLength) { if (pathLength == n) { count++; return; } for (int v : graph.get(u)) { if (freqMap.get(v) > 0) { freqMap.put(v, freqMap.get(v) - 1); dfs(v, pathLength + 1); freqMap.put(v, freqMap.get(v) + 1); } } } private boolean isPerfectSquare(long num) { if (num < 0) return false; long sqrt = (long) Math.sqrt(num); return sqrt * sqrt == num; }}Complexity
Time
O(U^2 + N!). `U` is the number of unique elements. `O(U^2)` is for building the graph. The search part is `O(N!)` in the worst case, but it's faster than the previous approach because at each step, we only iterate over valid neighbors instead of all unique numbers.
Space
O(U^2). The space is dominated by the storage for the graph, which can have up to `U^2` edges, where `U` is the number of unique elements. The recursion depth is `O(N)`. Since `U <= N`, this is `O(N^2)`.
Trade-offs
Pros
Most efficient approach.
Pre-computation prunes the search space more effectively during the DFS.
Cons
Slightly more complex to implement due to the explicit graph construction.
Higher space complexity than the simple backtracking if the graph is dense.
Solutions
Solution
class Solution {public int numSquarefulPerms(int[] nums) { int n = nums.length; int[][] f = new int[1 << n][n]; for (int j = 0; j < n; ++j) { f[1 << j][j] = 1; } for (int i = 0; i < 1 << n; ++i) { for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { for (int k = 0; k < n; ++k) { if ((i >> k & 1) == 1 && k != j) { int s = nums[j] + nums[k]; int t = (int)Math.sqrt(s); if (t * t == s) { f[i][j] += f[i ^ (1 << j)][k]; } } } } } } long ans = 0; for (int j = 0; j < n; ++j) { ans += f[(1 << n) - 1][j]; } Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer : : sum); } int[] g = new int[13]; g[0] = 1; for (int i = 1; i < 13; ++i) { g[i] = g[i - 1] * i; } for (int v : cnt.values()) { ans /= g[v]; } return (int)ans; }}class Solution {public: int numSquarefulPerms(vector<int> &nums) { int n = nums.size(); int f[1 << n][n]; memset(f, 0, sizeof(f)); for (int j = 0; j < n; ++j) { f[1 << j][j] = 1; } for (int i = 0; i < 1 << n; ++i) { for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { for (int k = 0; k < n; ++k) { if ((i >> k & 1) == 1 && k != j) { int s = nums[j] + nums[k]; int t = sqrt(s); if (t * t == s) { f[i][j] += f[i ^ (1 << j)][k]; } } } } } } long long ans = 0; for (int j = 0; j < n; ++j) { ans += f[(1 << n) - 1][j]; } unordered_map<int, int> cnt; for (int x : nums) { ++cnt[x]; } int g[13] = {1}; for (int i = 1; i < 13; ++i) { g[i] = g[i - 1] * i; } for (auto &[_, v] : cnt) { ans /= g[v]; } return ans; }};class Solution: def numSquarefulPerms(self, nums: List[int]) -> int: n = len(nums) f = [[0] * n for _ in range(1 << n)] for j in range(n): f[1 << j][j] = 1 for i in range(1 << n): for j in range(n): if i >> j & 1: for k in range(n): if (i >> k & 1) and k != j: s = nums[j] + nums[k] t = int(sqrt(s)) if t * t == s: f[i][j] += f[i ^ (1 << j)][k] ans = sum(f[(1 << n) - 1][j] for j in range(n)) for v in Counter(nums). values(): ans //= factorial(v) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.