We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Squareful Arrays

Number: 1038

Difficulty: Hard

Paid? No

Companies: Meta, Apple

Problem Description

Given an integer array nums, count the number of permutations of nums that form a squareful array. An array is considered squareful if the sum of every pair of adjacent elements is a perfect square. Two permutations are considered different if there exists an index i where the elements differ.

Key Insights

  • The problem requires ensuring adjacent pairs sum up to a perfect square.
  • Sorting the array helps in efficiently handling duplicates; when iterating in the backtracking, skip duplicate elements to avoid overcounting.
  • For each valid candidate, check that the sum with the previous number (if any) is a perfect square.
  • Use backtracking (DFS) to generate all valid permutations while maintaining a visited flag for each index.
  • Since the array may contain duplicates, extra care is taken to only use each occurrence in a controlled order (i.e., if two identical numbers exist, only the first unvisited instance can be chosen at a given recursive call).

Space and Time Complexity

Time Complexity: O(n^2 * 2^n) in the worst-case scenario due to exploring all bitmask states with n elements and checking pairwise sums. Space Complexity: O(n) for recursion and O(n) for the visited flag, plus potentially O(2^n * n) for memoization if implemented.

Solution

The solution uses a backtracking algorithm to explore all permutations. The array is first sorted to handle duplicates. A helper function checks if a number is a perfect square and is used to validate that the sum of every adjacent pair is a perfect square. During DFS, a visited array is maintained to track elements included so far. Skipping duplicate elements (unless the earlier duplicate was used) is essential to avoid overcounting. This approach ensures that every valid permutation is considered exactly once.

Code Solutions

from math import isqrt

# Function to check if a number is a perfect square
def is_square(num):
    root = isqrt(num)
    return root * root == num

def numSquarefulPerms(nums):
    n = len(nums)
    nums.sort()  # Sort the array to handle duplicates
    visited = [False] * n
    result = 0
    
    def dfs(last_index, count):
        nonlocal result
        # If all elements have been used, we found a valid permutation
        if count == n:
            result += 1
            return
        for i in range(n):
            if visited[i]:
                continue
            # Skip duplicates: if the current element is the same as the previous one and the previous one hasn't been used
            if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
                continue
            # If it's the first element or the sum with the last element is a perfect square
            if last_index == -1 or is_square(nums[last_index] + nums[i]):
                visited[i] = True
                dfs(i, count + 1)
                visited[i] = False
                
    dfs(-1, 0)
    return result

# Example usage:
if __name__ == "__main__":
    print(numSquarefulPerms([1, 17, 8]))  # Expected output: 2
    print(numSquarefulPerms([2, 2, 2]))   # Expected output: 1
← Back to All Questions