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).
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; }}Video 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.