D
DevExCode

LeetCode 996: Number of Squareful Arrays Solution

Master LeetCode problem 996 (Number of Squareful Arrays), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use backtracking to generate all permutations of the given array nums. We will keep track of the count of squareful permutations and check whether each permutation satisfies the squareful condition or not. We can use a helper function to check if the sum of two elements is a perfect square.

Algorithm:

  1. Initialize a count variable to store the number of squareful permutations.
  2. Sort the input array nums.
  3. Implement a helper function isSquareful to check if the sum of two elements is a perfect square.
  4. Implement a recursive backtracking function permute to generate all permutations.
  5. In the permute function:
    • Base case: If the current permutation's length is equal to the length of nums, check if it is squareful and increment the count if true.
    • Iterate through the remaining elements and swap them with the current index to generate permutations.
    • Ensure no duplicate permutations are generated by skipping swapping with elements that have been swapped before.
  6. Return the count of squareful permutations.

Time Complexity:

The time complexity of this approach is O(N!), where N is the length of the input array nums.

Space Complexity:

The space complexity is O(N), where N is the length of the input array nums.

Solution Code

class Solution {
    public int numSquarefulPerms(int[] nums) {
        Arrays.sort(nums);
        return permute(nums, 0, new boolean[nums.length], -1);
    }
    
    private int permute(int[] nums, int count, boolean[] visited, int prev) {
        if (count == nums.length) {
            return 1;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            if (prev == -1 || isSquareful(nums[i] + prev)) {
                visited[i] = true;
                res += permute(nums, count + 1, visited, nums[i]);
                visited[i] = false;
            }
        }
        return res;
    }
    
    private boolean isSquareful(int num) {
        int root = (int)Math.sqrt(num);
        return root * root == num;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 996 (Number of Squareful Arrays)?

This page provides optimized solutions for LeetCode problem 996 (Number of Squareful Arrays) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 996 (Number of Squareful Arrays)?

The time complexity for LeetCode 996 (Number of Squareful Arrays) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 996 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 996 in Java, C++, or Python.

Back to LeetCode Solutions