Number of Squareful Arrays

Hard
1596.

Number of Squareful Arrays

Number of Squareful Arrays is a hard coding problem on arrays, math and backtracking, asked in Amazon and Google interviews.

An array is squareful when the sum of every pair of adjacent elements is a perfect square (0, 1, 4, 9, 16, ...).

Return the number of distinct permutations of nums that are squareful. Two permutations are different when they differ at some index — swapping two equal values does not create a new permutation.

Example 1

Input
nums = [1,17,8]
Output
2
Explanation
`[1,8,17]` and `[17,8,1]`: 1 + 8 = 9 and 8 + 17 = 25.

Example 2

Input
nums = [2,2,2]
Output
1
Explanation
2 + 2 = 4, and all orderings are the same array.

Example 3

Input
nums = [3,6,10]
Output
2
Explanation
`[3,6,10]` and `[10,6,3]`: 9 and 16.

Constraints

  • 1 <= nums.length <= 12
  • 0 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numSquarefulPerms = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Squareful Arrays — Solution in Python, Java & C++

Number of Squareful Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Squareful Arrays is a hard coding problem on arrays, math and backtracking, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Math, Backtracking, Bitmask
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An array is squareful when the sum of every pair of adjacent elements is a perfect square (0, 1, 4, 9, 16, ...).

Return the number of distinct permutations of nums that are squareful. Two permutations are different when they differ at some index — swapping two equal values does not create a new permutation.

Example 1

Input: nums = [1,17,8]
Output: 2
Explanation: `[1,8,17]` and `[17,8,1]`: 1 + 8 = 9 and 8 + 17 = 25.

Example 2

Input: nums = [2,2,2]
Output: 1
Explanation: 2 + 2 = 4, and all orderings are the same array.

Example 3

Input: nums = [3,6,10]
Output: 2
Explanation: `[3,6,10]` and `[10,6,3]`: 9 and 16.

Constraints

  • 1 <= nums.length <= 12
  • 0 <= nums[i] <= 10^9

Hints for Number of Squareful Arrays

  1. Hint 1

    Precompute, for every pair of positions, whether their values add up to a perfect square. Sums reach 2 · 10^9, so use 64-bit arithmetic and an integer square-root check.

  2. Hint 2

    Build the permutation one position at a time, only placing a value whose sum with the previous value is a square.

  3. Hint 3

    To count each distinct permutation once, sort the array and, among equal values, always use the leftmost unused copy first (skip i if nums[i] == nums[i - 1] and i - 1 is unused).

How to solve Number of Squareful Arrays

Backtracking over permutations with two prunings: adjacency (the next value must form a square with the previous one) and duplicate suppression (equal values are used in a fixed order).

Approach

  1. Sort nums and precompute ok[i][j] = nums[i] + nums[j] is a perfect square.
  2. dfs(last, placed): if placed == n, count 1.
  3. Otherwise for each unused index i: skip it if i > 0, nums[i] == nums[i - 1] and i - 1 is unused; skip it if last >= 0 and !ok[last][i]. Mark, recurse with last = i, unmark.
  4. Return dfs(-1, 0).

Why it works

The duplicate rule allows exactly one ordering of the copies of each value, so every distinct value sequence is built once; the adjacency check rejects a prefix as soon as it stops being squareful, which keeps the tree small. An equivalent check: a bitmask DP counting index-paths, divided by the factorials of the multiplicities, gives the same number.

Complexity

  • Time — O(n!) worst case, much less with pruning; O(n^2) precomputation
  • Space — O(n^2)

Pitfalls

  • a + b can exceed 2^31 − 1 — compute it in 64 bits.
  • Floating-point sqrt can be off by one for large values; verify with an integer square.
  • 0 is a perfect square, so [0,0] is squareful.

Reference solution

Python

from typing import List
from math import isqrt

def numSquarefulPerms(nums: List[int]) -> int:
    a = sorted(nums)
    n = len(a)

    def square(x):
        r = isqrt(x)
        return r * r == x

    ok = [[square(a[i] + a[j]) for j in range(n)] for i in range(n)]
    used = [False] * n

    def dfs(last, placed):
        if placed == n:
            return 1
        total = 0
        for i in range(n):
            if used[i]:
                continue
            if i > 0 and a[i] == a[i - 1] and not used[i - 1]:
                continue
            if last >= 0 and not ok[last][i]:
                continue
            used[i] = True
            total += dfs(i, placed + 1)
            used[i] = False
        return total

    return dfs(-1, 0)

Java

public static int numSquarefulPerms(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length;
    boolean[][] ok = new boolean[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) ok[i][j] = squareSum((long) a[i] + a[j]);
    return squarefulDfs(a, ok, new boolean[n], -1, 0);
}

static boolean squareSum(long x) {
    long r = (long) Math.sqrt((double) x);
    while (r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r * r == x;
}

static int squarefulDfs(int[] a, boolean[][] ok, boolean[] used, int last, int placed) {
    if (placed == a.length) return 1;
    int total = 0;
    for (int i = 0; i < a.length; i++) {
        if (used[i]) continue;
        if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
        if (last >= 0 && !ok[last][i]) continue;
        used[i] = true;
        total += squarefulDfs(a, ok, used, i, placed + 1);
        used[i] = false;
    }
    return total;
}

C++

bool squareSum(long long x) {
    long long r = (long long)sqrt((double)x);
    while (r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r * r == x;
}

int squarefulDfs(vector<int>& a, vector<vector<bool>>& ok, vector<bool>& used, int last, int placed) {
    int n = a.size();
    if (placed == n) return 1;
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
        if (last >= 0 && !ok[last][i]) continue;
        used[i] = true;
        total += squarefulDfs(a, ok, used, i, placed + 1);
        used[i] = false;
    }
    return total;
}

int numSquarefulPerms(vector<int>& nums) {
    vector<int> a(nums.begin(), nums.end());
    sort(a.begin(), a.end());
    int n = a.size();
    vector<vector<bool>> ok(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) ok[i][j] = squareSum((long long)a[i] + a[j]);
    vector<bool> used(n, false);
    return squarefulDfs(a, ok, used, -1, 0);
}

JavaScript

var numSquarefulPerms = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var n = a.length;
    var square = function(x) {
        var r = Math.floor(Math.sqrt(x));
        while (r * r > x) r--;
        while ((r + 1) * (r + 1) <= x) r++;
        return r * r === x;
    };
    var ok = [];
    for (var i = 0; i < n; i++) {
        ok.push([]);
        for (var j = 0; j < n; j++) ok[i].push(square(a[i] + a[j]));
    }
    var used = new Array(n).fill(false);
    var dfs = function(last, placed) {
        if (placed === n) return 1;
        var total = 0;
        for (var i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && a[i] === a[i - 1] && !used[i - 1]) continue;
            if (last >= 0 && !ok[last][i]) continue;
            used[i] = true;
            total += dfs(i, placed + 1);
            used[i] = false;
        }
        return total;
    };
    return dfs(-1, 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Backtracking