algoadvance

Leetcode 473. Matchsticks to Square

Problem Statement

1. Matchsticks to Square

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to form a 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.

Clarifying Questions

1. Is it guaranteed that the length of the array is always positive?
2. Can any matchstick have a length of zero?
3. Should the function return false if it’s not possible to form a square using all the matchsticks?

Assumptions:

• Each matchstick length is a positive integer.
• Yes, the function should return false if it’s not possible to form a square.

Strategy

1. Calculate the sum of all matchsticks.
2. If the total length is not divisible by 4, return false (since we need four equal sides).
3. Each side of the square should have a length of total_length / 4.
4. Use a backtracking approach to try to build the four sides using the matchsticks.

Code

import java.util.Arrays;

public class MatchsticksToSquare {
    public boolean makesquare(int[] matchsticks) {
        int total_length = Arrays.stream(matchsticks).sum();
        if (total_length % 4 != 0) {
            return false;
        }

        Arrays.sort(matchsticks); // Sort to optimize - start with larger elements
        int side_length = total_length / 4;
        int[] sides = new int[4];
        
        return backtrack(matchsticks, sides, matchsticks.length - 1, side_length);
    }
    
    private boolean backtrack(int[] matchsticks, int[] sides, int index, int side_length) {
        if (index == -1) {
            // Check if all sides are equal to side_length
            return sides[0] == side_length && sides[1] == side_length &&
                   sides[2] == side_length && sides[3] == side_length;
        }
        
        int matchstick = matchsticks[index];
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchstick <= side_length) {
                sides[i] += matchstick;
                if (backtrack(matchsticks, sides, index - 1, side_length)) {
                    return true;
                }
                sides[i] -= matchstick;
            }

            // If this side is still 0 after the trial, next trials won't be different.
            if (sides[i] == 0) break;
        }

        return false;
    }

    public static void main(String[] args) {
        MatchsticksToSquare solver = new MatchsticksToSquare();
        int[] matchsticks = {1, 1, 2, 2, 2};
        System.out.println(solver.makesquare(matchsticks)); // Output: true
    }
}

Time Complexity

• Sorting the array takes (O(n \log n)).
• The backtracking process tries to place each matchstick in one of four buckets, leading to a complexity of (O(4^n)) in the worst case where (n) is the number of matchsticks.
• Given the sorting step, the overall time complexity of the algorithm is (O(n \log n + 4^n)).

While the backtracking step is computationally expensive, it is crucial to check every possible way to form equal sides with the matchsticks. The sorting helps optimize by trying larger elements first, which can help to find a solution early or cut off unsuccessful branches earlier.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?