Jobs

Interviews

Discussions

Number of Squareful Arrays

#1556 Most AskedHard

Number of Squareful Arrays #1556 Most Asked

Hard

Google

8 views

Topics:

ArraysRecursionGraphsDynamic Programming

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] <= 10⁹

Try coding it in LeetCode

Number of Squareful Arrays

#1556 Most AskedHard

Number of Squareful Arrays #1556 Most Asked

Hard

Google

8 views

Topics:

ArraysRecursionGraphsDynamic Programming

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] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers or non-integer values?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when determining if a pair sums to a perfect square?
What should I return if no squareful permutations are possible?
Are we looking for distinct squareful permutations, or should I count permutations that are the same after rearranging identical elements?

Brute Force Solution

Approach

The problem asks us to find how many ways we can arrange some numbers into a list so that when you add any two adjacent numbers, the result is a perfect square. The brute force method simply tries every single possible order of the numbers. For each order, it checks if it meets the perfect square requirement.

Here's how the algorithm would work step-by-step:

First, list out all the possible ways you can order the given numbers. Think of it like shuffling a deck of cards and writing down every different arrangement.
For each of these orderings, go through the list, looking at each pair of neighboring numbers.
Add each pair of neighboring numbers together.
Check if the sum is a perfect square (a number you get by squaring a whole number, like 4, 9, or 16).
If every pair in the entire list adds up to a perfect square, then this particular ordering of the numbers is a valid one.
Keep a count of how many total orderings are valid.
After you've checked every possible ordering, the count will tell you how many "squareful" arrays exist.

Code Implementation

from itertools import permutations

def is_perfect_square(number):
    if number < 0:
        return False
    square_root = int(number**0.5)
    return square_root * square_root == number

def number_of_squareful_arrays(numbers):
    number_of_squareful_arrays_found = 0
    all_permutations = permutations(numbers)

    for permutation in all_permutations:
        is_squareful = True

        # Check if each adjacent pair sums to a perfect square
        for index in range(len(permutation) - 1):

            if not is_perfect_square(permutation[index] + permutation[index + 1]):
                is_squareful = False
                break

        # Only increment if the current permutation is squareful
        if is_squareful:
            number_of_squareful_arrays_found += 1

    return number_of_squareful_arrays_found

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach generates all possible permutations of the input array of size n. Generating all permutations takes O(n!) time. For each permutation, we iterate through the array of size n to check if the sum of adjacent elements is a perfect square. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the input array. The number of permutations grows factorially with the input size N, where N is the number of elements in the input array. Storing these permutations, either explicitly as lists or implicitly within the recursion stack of a permutation generation algorithm, requires space proportional to the number of permutations, which is N!. Therefore, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The goal is to find how many ways we can arrange a group of numbers so that when you add each pair of neighboring numbers, the result is a perfect square. We do this efficiently by only exploring arrangements that could possibly work and avoiding redundant calculations.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the original group of numbers.
Think of the numbers as nodes in a graph. Connect two numbers with an edge if adding them creates a perfect square.
Start with one number and try to build a valid arrangement by adding connected numbers one at a time.
Keep track of the numbers you've used and only choose numbers that haven't already been used up (according to the counts you did earlier).
If you reach a point where you can't add any more numbers because nothing forms a perfect square, stop that attempt.
When you've used all the numbers, you've found a valid arrangement. Add one to your count.
Repeat the process, starting with each different number in the original group.
To avoid counting the same arrangement multiple times because of duplicate numbers, divide the final count by the number of ways you can rearrange those duplicate numbers.

Code Implementation

def number_of_squareful_arrays(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    graph = {}
    unique_numbers = list(number_counts.keys())
    for i in range(len(unique_numbers)):
        for j in range(i, len(unique_numbers)):
            sum_of_numbers = unique_numbers[i] + unique_numbers[j]
            square_root = int(sum_of_numbers**0.5)
            if square_root * square_root == sum_of_numbers:
                number1 = unique_numbers[i]
                number2 = unique_numbers[j]

                if number1 not in graph:
                    graph[number1] = []
                if number2 not in graph:
                    graph[number2] = []
                graph[number1].append(number2)
                if number1 != number2:
                    graph[number2].append(number1)

    total_arrangements = 0

    def backtrack(current_arrangement, remaining_counts):
        nonlocal total_arrangements
        if len(current_arrangement) == len(numbers):
            total_arrangements += 1
            return

        last_number = current_arrangement[-1]

        if last_number not in graph:
            return

        for next_number in graph[last_number]:
            # Avoid using numbers beyond their available counts.
            if remaining_counts.get(next_number, 0) > 0:
                remaining_counts[next_number] -= 1
                if remaining_counts[next_number] == 0:
                    del remaining_counts[next_number]
                backtrack(current_arrangement + [next_number], remaining_counts.copy())

    for start_number in unique_numbers:
        # Start the arrangements with each possible number.
        counts_copy = number_counts.copy()
        counts_copy[start_number] -= 1
        if counts_copy[start_number] == 0:
            del counts_copy[start_number]
        backtrack([start_number], counts_copy.copy())

    # Correct for overcounting identical permutations.
    from math import factorial
    for count in number_counts.values():
        total_arrangements //= factorial(count)

    return total_arrangements

Big(O) Analysis

Time Complexity

O(n*n!) – The algorithm explores all possible permutations of the input array of size n. Building the adjacency list representing perfect square sums involves checking all pairs of numbers, costing O(n^2). The depth-first search (DFS) to find squareful permutations explores all possible arrangements, which can be up to n! in the worst case. The initial adjacency list creation is dominated by the permutation exploration. Therefore, the time complexity is approximately O(n * n!).

Space Complexity

O(N + V^2) – The space complexity stems from several sources. A hash map is used to count the frequency of each number in the input array of size N, which contributes O(N) space, where N is the number of elements in the input array. The graph, represented as an adjacency matrix, stores connections between numbers that sum to a perfect square; in the worst case, every number could potentially connect to every other number resulting in a V x V adjacency matrix using O(V^2) space, where V is the number of unique values in the input array. Furthermore, the recursive calls store visited numbers, using, at most, O(N) space on the recursion stack. Thus, the overall auxiliary space is O(N + V^2), as the adjacency matrix will likely dominate when the number of unique values is significant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as no permutations are possible.
Array with one element	Return 0, as a squareful pair requires at least two elements.
Array with two elements where their sum is not a perfect square	Return 0 because a valid permutation cannot be formed.
Array containing duplicate numbers that can form squareful pairs with other numbers multiple times.	Use a frequency map to track element counts and adjust calculations to avoid overcounting permutations.
Array with a large number of elements causing significant recursion depth.	Optimize the algorithm (e.g., using memoization or dynamic programming if possible) or consider iterative approaches to reduce recursion depth.
Array containing very large numbers that could lead to integer overflow when summed.	Use a data type with a larger range (e.g., long) or check for potential overflow before performing addition.
Array where no valid squareful permutation exists	The algorithm should correctly explore all possible permutations and return 0.
Array with identical elements, forming multiple identical squareful permutations	Divide the final permutation count by the factorial of the frequency of each repeated element to avoid overcounting.

Null or empty input array

How to Handle:

Return 0, as no permutations are possible.

Array with one element

How to Handle:

Return 0, as a squareful pair requires at least two elements.

Array with two elements where their sum is not a perfect square

How to Handle:

Return 0 because a valid permutation cannot be formed.

Array containing duplicate numbers that can form squareful pairs with other numbers multiple times.

How to Handle:

Use a frequency map to track element counts and adjust calculations to avoid overcounting permutations.

Array with a large number of elements causing significant recursion depth.

How to Handle:

Optimize the algorithm (e.g., using memoization or dynamic programming if possible) or consider iterative approaches to reduce recursion depth.

Array containing very large numbers that could lead to integer overflow when summed.

How to Handle:

Use a data type with a larger range (e.g., long) or check for potential overflow before performing addition.

Array where no valid squareful permutation exists

How to Handle:

The algorithm should correctly explore all possible permutations and return 0.

Array with identical elements, forming multiple identical squareful permutations

How to Handle:

Divide the final permutation count by the factorial of the frequency of each repeated element to avoid overcounting.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers or non-integer values?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when determining if a pair sums to a perfect square?
What should I return if no squareful permutations are possible?
Are we looking for distinct squareful permutations, or should I count permutations that are the same after rearranging identical elements?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, list out all the possible ways you can order the given numbers. Think of it like shuffling a deck of cards and writing down every different arrangement.
For each of these orderings, go through the list, looking at each pair of neighboring numbers.
Add each pair of neighboring numbers together.
Check if the sum is a perfect square (a number you get by squaring a whole number, like 4, 9, or 16).
If every pair in the entire list adds up to a perfect square, then this particular ordering of the numbers is a valid one.
Keep a count of how many total orderings are valid.
After you've checked every possible ordering, the count will tell you how many "squareful" arrays exist.

Code Implementation

from itertools import permutations

def is_perfect_square(number):
    if number < 0:
        return False
    square_root = int(number**0.5)
    return square_root * square_root == number

def number_of_squareful_arrays(numbers):
    number_of_squareful_arrays_found = 0
    all_permutations = permutations(numbers)

    for permutation in all_permutations:
        is_squareful = True

        # Check if each adjacent pair sums to a perfect square
        for index in range(len(permutation) - 1):

            if not is_perfect_square(permutation[index] + permutation[index + 1]):
                is_squareful = False
                break

        # Only increment if the current permutation is squareful
        if is_squareful:
            number_of_squareful_arrays_found += 1

    return number_of_squareful_arrays_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the original group of numbers.
Think of the numbers as nodes in a graph. Connect two numbers with an edge if adding them creates a perfect square.
Start with one number and try to build a valid arrangement by adding connected numbers one at a time.
Keep track of the numbers you've used and only choose numbers that haven't already been used up (according to the counts you did earlier).
If you reach a point where you can't add any more numbers because nothing forms a perfect square, stop that attempt.
When you've used all the numbers, you've found a valid arrangement. Add one to your count.
Repeat the process, starting with each different number in the original group.
To avoid counting the same arrangement multiple times because of duplicate numbers, divide the final count by the number of ways you can rearrange those duplicate numbers.

Code Implementation

def number_of_squareful_arrays(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    graph = {}
    unique_numbers = list(number_counts.keys())
    for i in range(len(unique_numbers)):
        for j in range(i, len(unique_numbers)):
            sum_of_numbers = unique_numbers[i] + unique_numbers[j]
            square_root = int(sum_of_numbers**0.5)
            if square_root * square_root == sum_of_numbers:
                number1 = unique_numbers[i]
                number2 = unique_numbers[j]

                if number1 not in graph:
                    graph[number1] = []
                if number2 not in graph:
                    graph[number2] = []
                graph[number1].append(number2)
                if number1 != number2:
                    graph[number2].append(number1)

    total_arrangements = 0

    def backtrack(current_arrangement, remaining_counts):
        nonlocal total_arrangements
        if len(current_arrangement) == len(numbers):
            total_arrangements += 1
            return

        last_number = current_arrangement[-1]

        if last_number not in graph:
            return

        for next_number in graph[last_number]:
            # Avoid using numbers beyond their available counts.
            if remaining_counts.get(next_number, 0) > 0:
                remaining_counts[next_number] -= 1
                if remaining_counts[next_number] == 0:
                    del remaining_counts[next_number]
                backtrack(current_arrangement + [next_number], remaining_counts.copy())

    for start_number in unique_numbers:
        # Start the arrangements with each possible number.
        counts_copy = number_counts.copy()
        counts_copy[start_number] -= 1
        if counts_copy[start_number] == 0:
            del counts_copy[start_number]
        backtrack([start_number], counts_copy.copy())

    # Correct for overcounting identical permutations.
    from math import factorial
    for count in number_counts.values():
        total_arrangements //= factorial(count)

    return total_arrangements

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as no permutations are possible.
Array with one element	Return 0, as a squareful pair requires at least two elements.
Array with two elements where their sum is not a perfect square	Return 0 because a valid permutation cannot be formed.
Array containing duplicate numbers that can form squareful pairs with other numbers multiple times.	Use a frequency map to track element counts and adjust calculations to avoid overcounting permutations.
Array with a large number of elements causing significant recursion depth.	Optimize the algorithm (e.g., using memoization or dynamic programming if possible) or consider iterative approaches to reduce recursion depth.
Array containing very large numbers that could lead to integer overflow when summed.	Use a data type with a larger range (e.g., long) or check for potential overflow before performing addition.
Array where no valid squareful permutation exists	The algorithm should correctly explore all possible permutations and return 0.
Array with identical elements, forming multiple identical squareful permutations	Divide the final permutation count by the factorial of the frequency of each repeated element to avoid overcounting.

Null or empty input array

How to Handle:

Return 0, as no permutations are possible.

Array with one element

How to Handle:

Return 0, as a squareful pair requires at least two elements.

Array with two elements where their sum is not a perfect square

How to Handle:

Return 0 because a valid permutation cannot be formed.

Array containing duplicate numbers that can form squareful pairs with other numbers multiple times.

How to Handle:

Use a frequency map to track element counts and adjust calculations to avoid overcounting permutations.

Array with a large number of elements causing significant recursion depth.

How to Handle:

Optimize the algorithm (e.g., using memoization or dynamic programming if possible) or consider iterative approaches to reduce recursion depth.

Array containing very large numbers that could lead to integer overflow when summed.

How to Handle:

Use a data type with a larger range (e.g., long) or check for potential overflow before performing addition.

Array where no valid squareful permutation exists

How to Handle:

The algorithm should correctly explore all possible permutations and return 0.

Array with identical elements, forming multiple identical squareful permutations

How to Handle:

Divide the final permutation count by the factorial of the frequency of each repeated element to avoid overcounting.

0/1916 Google questions completed

0/1916 completed