Jobs

Interviews

Discussions

Matchsticks to Square

Medium

Asked by:

More companies

110 views

Topics:

ArraysRecursion

You are given an integer array matchsticks where matchsticks[i] is the length of the i^th matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Example 1:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

Constraints:

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 10⁸

Try coding it in LeetCode

Matchsticks to Square

Medium

Asked by:

110 views

Topics:

ArraysRecursion

Return true if you can make this square and false otherwise.

Example 1:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

Constraints:

1 <= matchsticks.length <= 15
1 <= matchsticks[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:

Can the length of the `matchsticks` array be zero? Can any of the individual matchstick lengths be zero?
Are the matchstick lengths always integers, and are they guaranteed to be non-negative?
If it's impossible to form a square, what should I return? Should I return `false`, throw an exception, or is there another specified error handling?
Are there any constraints on the maximum value of an individual matchstick length?
If there are multiple ways to form a square, do I need to return a specific configuration or is any valid solution acceptable?

Brute Force Solution

Approach

The brute force approach to determining if you can form a square with matchsticks involves trying every possible combination of assigning matchsticks to the four sides. We explore all combinations until we either find a valid square or exhaust all possibilities. Think of it like trying every possible arrangement of the sticks until you find one that works.

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

First, check if the total length of all matchsticks is divisible by four. If not, it's impossible to make a square, so stop.
Calculate the required length of each side of the square by dividing the total length by four.
Imagine you have four empty piles representing the four sides of the square.
Start by picking a matchstick and try placing it in the first pile.
Then, pick another matchstick and try placing it in the first pile as well, then try the second pile, the third, and so on.
Keep going, trying all the different piles for each matchstick until all matchsticks are tentatively assigned.
After assigning all the matchsticks, check if the sum of the lengths of the matchsticks in each pile is equal to the required side length.
If they are, you've found a valid square and you're done!
If not, go back and try a different combination of assigning matchsticks to piles.
Repeat this process until you've tried every single possible combination.
If you've tried every combination and none of them form a square (each side having the calculated required side length), then it's impossible to form a square with the given matchsticks.

Code Implementation

def matchsticks_to_square(matchsticks):
    total_matchstick_length = sum(matchsticks)

    # Impossible if total length isn't divisible by 4
    if total_matchstick_length % 4 != 0:
        return False

    target_side_length = total_matchstick_length // 4
    sides = [0] * 4

    def can_form_square(index):
        if index == len(matchsticks):
            # Check if all sides are equal to the target
            return all(side == target_side_length for side in sides)

        for i in range(4):
            # Skip if adding exceeds side length
            if sides[i] + matchsticks[index] > target_side_length:
                continue

            sides[i] += matchsticks[index]

            if can_form_square(index + 1):
                return True

            # Backtrack: remove to explore other paths
            sides[i] -= matchsticks[index]

        return False

    return can_form_square(0)

Big(O) Analysis

Time Complexity

O(4^n) – The provided approach describes a brute-force method that explores all possible combinations of assigning n matchsticks to four sides. For each matchstick, there are four choices of which side to assign it to. This leads to exploring 4 * 4 * ... * 4 (n times) possible combinations. Therefore, the time complexity grows exponentially with the number of matchsticks, resulting in O(4^n). Note this is substantially worse than the more optimized backtracking solutions.

Space Complexity

O(N) – The brute force approach, as described, implicitly uses recursion to explore all possible combinations of assigning matchsticks to the four sides. The depth of the recursion can go up to N, where N is the number of matchsticks, as we potentially make a recursive call for each matchstick. Each recursive call adds a new frame to the call stack, consuming memory. Therefore, the auxiliary space complexity is O(N) due to the recursion stack.

Optimal Solution

Approach

The core idea is to determine if the matchsticks can be divided into four equal groups, each forming a side of the square. Then, try to construct each side using the matchsticks in a way that efficiently explores possible combinations. This avoids testing every possible combination of matchsticks.

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

First, add up the lengths of all the matchsticks.
Check if the total length can be evenly divided by four. If not, it's impossible to form a square, so you're done.
Calculate the target length for each side of the square (total length divided by four).
Now, try to build each side of the square, one at a time, by picking matchsticks. Start with the longest matchsticks first; this helps reduce the number of attempts.
For each side, consider each matchstick. Either include it in the current side or don't.
If you find a combination of matchsticks that exactly equals the target length for a side, mark those matchsticks as used and move on to building the next side.
If you successfully build all four sides without running out of matchsticks, then you can form a square. Otherwise, you can't.

Code Implementation

def matchsticks_to_square(matchsticks):    total_matchstick_length = sum(matchsticks)
    if total_matchstick_length % 4 != 0:
        return False

    side_length = total_matchstick_length // 4
    matchsticks.sort(reverse=True)
    number_of_matchsticks = len(matchsticks)
    sides = [0] * 4

    def can_form_square(index):
        if index == number_of_matchsticks:
            # If all sides are equal, we have a square
            return sides[0] == side_length and sides[1] == side_length and sides[2] == side_length and sides[3] == side_length

        for side_index in range(4):
            # Try adding the current matchstick to each side
            if sides[side_index] + matchsticks[index] <= side_length:
                sides[side_index] += matchsticks[index]
                if can_form_square(index + 1):
                    return True

                # Backtrack if adding to current side doesn't work
                sides[side_index] -= matchsticks[index]

        return False

    # Start recursive process, picking sticks
    return can_form_square(0)

Big(O) Analysis

Time Complexity

O(4^n) – The algorithm explores all possible combinations of matchsticks to form the sides of the square. In the worst-case scenario, for each of the 'n' matchsticks, there are two choices: either include it in a side or exclude it. This leads to a branching factor of 2 for each matchstick. Because the algorithm attempts to build four sides, this roughly translates to 2^n possibilities for each side and a runtime behavior of O(2^n * 2^n * 2^n * 2^n) which simplifies to O(4^n) accounting for searching possibilities to form four sides in a row. This exponential complexity arises because the algorithm inherently explores all possible subsets of matchsticks, until it finds the correct subsets.

Space Complexity

O(N) – The dominant space complexity stems from the recursive calls made during the attempt to build each side. In the worst-case scenario, the recursive calls can reach a depth proportional to the number of matchsticks, N, where N is the number of matchsticks. Each recursive call adds a new frame to the call stack. Therefore, the auxiliary space is O(N) due to the recursion depth.

Edge Cases

Case	How to Handle
Empty matchsticks array	Return false immediately, as a square cannot be formed with no matchsticks.
Matchsticks array with fewer than 4 elements	Return false, as at least 4 sides are needed to form a square.
Matchsticks array with one very long matchstick (longer than half the total length)	Return false, as this stick cannot possibly be used in a valid square.
Matchsticks array with many zeros	Zeros should not affect the algorithm's correctness but could cause unnecessary recursion; handle by skipping zero-length sticks.
Sum of matchsticks is not divisible by 4	Return false immediately, as equal sides are impossible if the total length is not divisible by 4.
Integer overflow when calculating the sum of matchsticks	Use a long integer type to store the sum to prevent potential overflow.
The given array leads to excessive recursion depth (stack overflow)	Consider optimization techniques such as memoization or dynamic programming to reduce recursion.
All matchstick lengths are the same.	Check if the array length is a multiple of 4; if so, a square can be formed, otherwise not.

Empty matchsticks array

How to Handle:

Return false immediately, as a square cannot be formed with no matchsticks.

Matchsticks array with fewer than 4 elements

How to Handle:

Return false, as at least 4 sides are needed to form a square.

Matchsticks array with one very long matchstick (longer than half the total length)

How to Handle:

Return false, as this stick cannot possibly be used in a valid square.

Matchsticks array with many zeros

How to Handle:

Zeros should not affect the algorithm's correctness but could cause unnecessary recursion; handle by skipping zero-length sticks.

Sum of matchsticks is not divisible by 4

How to Handle:

Return false immediately, as equal sides are impossible if the total length is not divisible by 4.

Integer overflow when calculating the sum of matchsticks

How to Handle:

Use a long integer type to store the sum to prevent potential overflow.

The given array leads to excessive recursion depth (stack overflow)

How to Handle:

Consider optimization techniques such as memoization or dynamic programming to reduce recursion.

All matchstick lengths are the same.

How to Handle:

Check if the array length is a multiple of 4; if so, a square can be formed, otherwise not.

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:

Can the length of the `matchsticks` array be zero? Can any of the individual matchstick lengths be zero?
Are the matchstick lengths always integers, and are they guaranteed to be non-negative?
If it's impossible to form a square, what should I return? Should I return `false`, throw an exception, or is there another specified error handling?
Are there any constraints on the maximum value of an individual matchstick length?
If there are multiple ways to form a square, do I need to return a specific configuration or is any valid solution acceptable?

Brute Force Solution

Approach

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

First, check if the total length of all matchsticks is divisible by four. If not, it's impossible to make a square, so stop.
Calculate the required length of each side of the square by dividing the total length by four.
Imagine you have four empty piles representing the four sides of the square.
Start by picking a matchstick and try placing it in the first pile.
Then, pick another matchstick and try placing it in the first pile as well, then try the second pile, the third, and so on.
Keep going, trying all the different piles for each matchstick until all matchsticks are tentatively assigned.
After assigning all the matchsticks, check if the sum of the lengths of the matchsticks in each pile is equal to the required side length.
If they are, you've found a valid square and you're done!
If not, go back and try a different combination of assigning matchsticks to piles.
Repeat this process until you've tried every single possible combination.
If you've tried every combination and none of them form a square (each side having the calculated required side length), then it's impossible to form a square with the given matchsticks.

Code Implementation

def matchsticks_to_square(matchsticks):
    total_matchstick_length = sum(matchsticks)

    # Impossible if total length isn't divisible by 4
    if total_matchstick_length % 4 != 0:
        return False

    target_side_length = total_matchstick_length // 4
    sides = [0] * 4

    def can_form_square(index):
        if index == len(matchsticks):
            # Check if all sides are equal to the target
            return all(side == target_side_length for side in sides)

        for i in range(4):
            # Skip if adding exceeds side length
            if sides[i] + matchsticks[index] > target_side_length:
                continue

            sides[i] += matchsticks[index]

            if can_form_square(index + 1):
                return True

            # Backtrack: remove to explore other paths
            sides[i] -= matchsticks[index]

        return False

    return can_form_square(0)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, add up the lengths of all the matchsticks.
Check if the total length can be evenly divided by four. If not, it's impossible to form a square, so you're done.
Calculate the target length for each side of the square (total length divided by four).
Now, try to build each side of the square, one at a time, by picking matchsticks. Start with the longest matchsticks first; this helps reduce the number of attempts.
For each side, consider each matchstick. Either include it in the current side or don't.
If you find a combination of matchsticks that exactly equals the target length for a side, mark those matchsticks as used and move on to building the next side.
If you successfully build all four sides without running out of matchsticks, then you can form a square. Otherwise, you can't.

Code Implementation

def matchsticks_to_square(matchsticks):    total_matchstick_length = sum(matchsticks)
    if total_matchstick_length % 4 != 0:
        return False

    side_length = total_matchstick_length // 4
    matchsticks.sort(reverse=True)
    number_of_matchsticks = len(matchsticks)
    sides = [0] * 4

    def can_form_square(index):
        if index == number_of_matchsticks:
            # If all sides are equal, we have a square
            return sides[0] == side_length and sides[1] == side_length and sides[2] == side_length and sides[3] == side_length

        for side_index in range(4):
            # Try adding the current matchstick to each side
            if sides[side_index] + matchsticks[index] <= side_length:
                sides[side_index] += matchsticks[index]
                if can_form_square(index + 1):
                    return True

                # Backtrack if adding to current side doesn't work
                sides[side_index] -= matchsticks[index]

        return False

    # Start recursive process, picking sticks
    return can_form_square(0)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty matchsticks array	Return false immediately, as a square cannot be formed with no matchsticks.
Matchsticks array with fewer than 4 elements	Return false, as at least 4 sides are needed to form a square.
Matchsticks array with one very long matchstick (longer than half the total length)	Return false, as this stick cannot possibly be used in a valid square.
Matchsticks array with many zeros	Zeros should not affect the algorithm's correctness but could cause unnecessary recursion; handle by skipping zero-length sticks.
Sum of matchsticks is not divisible by 4	Return false immediately, as equal sides are impossible if the total length is not divisible by 4.
Integer overflow when calculating the sum of matchsticks	Use a long integer type to store the sum to prevent potential overflow.
The given array leads to excessive recursion depth (stack overflow)	Consider optimization techniques such as memoization or dynamic programming to reduce recursion.
All matchstick lengths are the same.	Check if the array length is a multiple of 4; if so, a square can be formed, otherwise not.

Empty matchsticks array

How to Handle:

Return false immediately, as a square cannot be formed with no matchsticks.

Matchsticks array with fewer than 4 elements

How to Handle:

Return false, as at least 4 sides are needed to form a square.

Matchsticks array with one very long matchstick (longer than half the total length)

How to Handle:

Return false, as this stick cannot possibly be used in a valid square.

Matchsticks array with many zeros

How to Handle:

Zeros should not affect the algorithm's correctness but could cause unnecessary recursion; handle by skipping zero-length sticks.

Sum of matchsticks is not divisible by 4

How to Handle:

Return false immediately, as equal sides are impossible if the total length is not divisible by 4.

Integer overflow when calculating the sum of matchsticks

How to Handle:

Use a long integer type to store the sum to prevent potential overflow.

The given array leads to excessive recursion depth (stack overflow)

How to Handle:

Consider optimization techniques such as memoization or dynamic programming to reduce recursion.

All matchstick lengths are the same.

How to Handle:

Check if the array length is a multiple of 4; if so, a square can be formed, otherwise not.