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

Matchsticks to Square

Number: 473

Difficulty: Medium

Paid? No

Companies: TikTok, PhonePe, Microsoft, Uber, Rackspace

Problem Description

Given an array of matchsticks, determine if you can use all the matchsticks exactly once (without breaking any) to form a square. Each side of the square must be of equal length.

Key Insights

  • The total length of matchsticks must be divisible by 4 to form a square.
  • Sorting the matchsticks in descending order can help prune the backtracking search early.
  • Use depth-first search (DFS) or backtracking to try to assign each matchstick to one of the four sides.
  • If a matchstick does not fit in a side (i.e., would exceed the target length), skip that possibility.
  • The problem constraints (up to 15 matchsticks) ensures that an exponential backtracking solution is feasible.

Space and Time Complexity

Time Complexity: O(4^N), where N is the number of matchsticks, due to exploring up to 4 choices for each matchstick. Space Complexity: O(N) for the recursion stack.

Solution

We first check if the sum of all matchsticks is divisible by 4. If not, forming a square is impossible and we return false. Next, we calculate the target side length by summing all matchsticks and dividing by 4. To optimize the search, we sort the matchsticks in descending order. Then, using DFS/backtracking, we try to place each matchstick into one of the four sides. If a matchstick can fit (i.e., current side length plus matchstick length is less than or equal to the target), we add it and recursively try to fill the remaining matchsticks. If placing the matchstick in the current side fails, we backtrack and try another side. This approach uses recursion and pruning to efficiently determine if a valid square formation is possible.

Code Solutions

# Function to determine if matchsticks can form a square
def makesquare(matchsticks):
    # Calculate the total sum of matchsticks
    total_length = sum(matchsticks)
    # The total length must be divisible by 4 for a square
    if total_length % 4 != 0:
        return False
    side_length = total_length // 4

    # Sort matchsticks in descending order for optimization
    matchsticks.sort(reverse=True)

    # Initialize four sides with length 0
    sides = [0] * 4

    # Recursive helper function to try placing each matchstick
    def dfs(index):
        # If we have placed all matchsticks, check if all sides equal the target
        if index == len(matchsticks):
            return sides[0] == sides[1] == sides[2] == sides[3] == side_length
        # Try to place current matchstick in each side
        for i in range(4):
            # Check if placing the matchstick does not exceed the side length
            if sides[i] + matchsticks[index] <= side_length:
                sides[i] += matchsticks[index]
                # Recurse for the next matchstick
                if dfs(index + 1):
                    return True
                # Backtrack: remove the matchstick from current side
                sides[i] -= matchsticks[index]
        return False

    return dfs(0)

# Example usage:
# print(makesquare([1,1,2,2,2])) should output True
← Back to All Questions