Number Of Squareful Arrays - Leetcode Solution

Problem Statement:

Given an array nums of unique integers, return the number of all possible squareful arrays.

A squareful array is a permutation of the integers in nums that satisfies the following two conditions:

1. The number of adjacent pairs (i, j) where i < j and sqrt(nums[i] + nums[j]) is an integer.
2. Permutations are counted as distinct if and only if their corresponding element-wise lists are different.

Solution Approach:

In this problem, we need to count all possible squareful arrays from the given array. A squareful array is a permutation of the integers in nums that satisfies the given conditions. We will use backtracking and permutation to solve this problem.

1. We create a map that stores the frequency of each number in the given array.
2. We create a function that takes a current permutation and the last number that was appended to it.
3. We loop through each number in the given array and check if the frequency of that number in the map is greater than 0.
4. We check if the square root of the sum of the current number and the last number in the permutation is an integer.
5. If it is an integer, we decrement the frequency of the current number in the map, append it to the permutation and call the function recursively with the updated permutation and the last number as the current number.
6. After the recursive call, we restore the frequency of the current number in the map and remove it from the permutation.
7. We return the count of all squareful arrays.

Code:

class Solution {
public:
    int numSquarefulPerms(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> freq;
        for(int i=0;i<n;i++)
            freq[nums[i]]++;
        int count = 0;
        vector<int> perm;
        for(auto entry: freq) {
            perm.push_back(entry.first);
            freq[entry.first]--;
            count += dfs(perm, entry.first, n, freq);
            perm.pop_back();
            freq[entry.first]++;
        }
        return count;
    }
    
    int dfs(vector<int>& perm, int last, int n, unordered_map<int, int>& freq) {
        if(perm.size() == n) {
            return 1;
        }
        int count = 0;
        for(auto entry: freq) {
            if(entry.second > 0) {
                int curr = entry.first;
                if(isSquareful(last, curr)) {
                    perm.push_back(curr);
                    freq[curr]--;
                    count += dfs(perm, curr, n, freq);
                    perm.pop_back();
                    freq[curr]++;
                }
            }
        }   
        return count;
    }
    
    bool isSquareful(int a, int b) {
        int sum = a + b;
        int root = sqrt(sum);
        return root*root == sum;
    }
};

Time Complexity:

The time complexity of this algorithm is O(n*n!) as there can be N! permutations and checking if two numbers form a squareful pair is O(1) as we check the square root of the sum of the given numbers.

Space Complexity:

The space complexity of this algorithm is O(n) as we are storing the frequency of each number in the map and the current permutation of size n.

1