996. Number of Squareful Arrays LeetCode Solution

In this guide, you will get 996. Number of Squareful Arrays LeetCode Solution with the best time and space complexity. The solution to Number of Squareful Arrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Squareful Arrays solution in C++
Number of Squareful Arrays solution in Java
Number of Squareful Arrays solution in Python
Additional Resources

996. Number of Squareful Arrays LeetCode Solution image

Problem Statement of Number of Squareful Arrays

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] <= 109

Complexity Analysis

Time Complexity: O(n \cdot 2^n)
Space Complexity: O(n \cdot 2^n)

996. Number of Squareful Arrays LeetCode Solution in C++

class Solution {
 public:
  int numSquarefulPerms(vector<int>& nums) {
    int ans = 0;
    ranges::sort(nums);
    dfs(nums, vector<bool>(nums.size()), {}, ans);
    return ans;
  }

 private:
  void dfs(vector<int>& nums, vector<bool>&& used, vector<int>&& path,
           int& ans) {
    if (path.size() > 1 && !isSquare(path.back() + path[path.size() - 2]))
      return;
    if (path.size() == nums.size()) {
      ++ans;
      return;
    }

    for (int i = 0; i < nums.size(); ++i) {
      if (used[i])
        continue;
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
        continue;
      used[i] = true;
      path.push_back(nums[i]);
      dfs(nums, std::move(used), std::move(path), ans);
      path.pop_back();
      used[i] = false;
    }
  }

  bool isSquare(int num) {
    const int root = sqrt(num);
    return root * root == num;
  }
};
/* code provided by PROGIEZ */

996. Number of Squareful Arrays LeetCode Solution in Java

class Solution {
  public int numSquarefulPerms(int[] nums) {
    boolean[] used = new boolean[nums.length];
    Arrays.sort(nums);
    dfs(nums, used, new ArrayList<>());
    return ans;
  }

  private int ans = 0;

  private void dfs(int[] nums, boolean[] used, List<Integer> path) {
    if (path.size() > 1 && !isSquare(path.get(path.size() - 1) + path.get(path.size() - 2)))
      return;
    if (path.size() == nums.length) {
      ++ans;
      return;
    }

    for (int i = 0; i < nums.length; ++i) {
      if (used[i])
        continue;
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
        continue;
      used[i] = true;
      path.add(nums[i]);
      dfs(nums, used, path);
      path.remove(path.size() - 1);
      used[i] = false;
    }
  }

  private boolean isSquare(int num) {
    int root = (int) Math.sqrt(num);
    return root * root == num;
  }
}
// code provided by PROGIEZ

996. Number of Squareful Arrays LeetCode Solution in Python

class Solution:
  def numSquarefulPerms(self, nums: list[int]) -> int:
    ans = 0
    used = [False] * len(nums)

    def isSquare(num: int) -> bool:
      root = math.isqrt(num)
      return root * root == num

    def dfs(path: list[int]) -> None:
      nonlocal ans
      if len(path) > 1 and not isSquare(path[-1] + path[-2]):
        return
      if len(path) == len(nums):
        ans += 1
        return

      for i, a in enumerate(nums):
        if used[i]:
          continue
        if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
          continue
        used[i] = True
        dfs(path + [a])
        used[i] = False

    nums.sort()
    dfs([])
    return ans
 # code by PROGIEZ