Number of Squareful Arrays - Practice Coding Problems

Number of Squareful Arrays - Problem

Array Hash Table Math Dynamic Programming Backtracking Bit Manipulation Bitmask Hard

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].

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,17,8]

› Output: 2

💡 Note: Two valid permutations: [1,8,17] (1+8=9=3², 8+17=25=5²) and [17,8,1] (17+8=25=5², 8+1=9=3²)

Example 2 — No Valid Permutations

$ Input: nums = [2,2,2]

› Output: 1

💡 Note: Only one arrangement [2,2,2], and 2+2=4=2² for all adjacent pairs, so it's squareful

Example 3 — Empty Result

$ Input: nums = [2,3,5]

› Output: 0

💡 Note: No two numbers sum to a perfect square: 2+3=5, 2+5=7, 3+5=8, none are perfect squares

Constraints

1 ≤ nums.length ≤ 12
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,17,8] - need to count squareful permutations

Check Adjacencies

Find which pairs sum to perfect squares

Count Valid

Count permutations with all adjacent pairs squareful

Key Takeaway

🎯 Key Insight: Model as a graph where edges connect numbers that sum to perfect squares, then use backtracking to count valid paths

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to model this as a graph problem where edges connect numbers that sum to perfect squares. The optimal approach uses backtracking with adjacency graph to avoid generating invalid permutations. Time: O(n! × √max_sum), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Permutations	O(n! × n)	O(n)	Generate all permutations and check each for squareful property
Backtracking with Graph	O(n! × √max_sum)	O(n²)	Build valid permutations step by step using adjacency graph

Brute Force Permutations — Algorithm Steps

Generate all permutations of nums
For each permutation, check adjacent pairs
Count permutations where all pairs sum to perfect squares

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements

Check Adjacent Sums

Verify each pair sums to perfect square

Count Valid

Count permutations that pass all checks

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int isPerfectSquare(int n) {
    if (n < 0) return 0;
    int root = (int) sqrt(n);
    return root * root == n;
}

int isSquareful(int* perm, int size) {
    for (int i = 0; i < size - 1; i++) {
        if (!isPerfectSquare(perm[i] + perm[i + 1])) {
            return 0;
        }
    }
    return 1;
}

int permute(int* arr, int size, int start) {
    if (start == size) {
        return isSquareful(arr, size) ? 1 : 0;
    }
    
    int count = 0;
    int used[1000] = {0};
    for (int i = start; i < size; i++) {
        int val = arr[i] + 500;
        if (val >= 0 && val < 1000 && !used[val]) {
            used[val] = 1;
            int temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
            count += permute(arr, size, start + 1);
            temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
        }
    }
    return count;
}

int solution(int* nums, int size) {
    int* numsCopy = (int*)malloc(size * sizeof(int));
    memcpy(numsCopy, nums, size * sizeof(int));
    int result = permute(numsCopy, size, 0);
    free(numsCopy);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations, each takes O(n) time to validate adjacent pairs

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and current permutation storage

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler