Matchsticks to Square Leetcode Solution

Problem Statement

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

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.

Input:

 matchsticks = [3,3,3,3,4]

Output:

 false

Explanation:

 You cannot find a way to form a square with all the matchsticks.

Approach

Idea

The main idea here is to take all possibilities using Backtracking. Since we have 4 edges in a square so the ith matchstick can have 4 choices, we can explore all choices and after traversing the whole matchsticks array we can see the length of the 4 sides and whether they are all equal to the target value. If yes, we return true otherwise false.

The above solution is prolonged and has an exponential time complexity, We can speed this up considerably by sorting the matchsticks array in decreasing order so that bigger matchsticks will get processed earlier, and if there is no solution, try a longer matchstick will lead to the negative conclusion first.

We can also improve the runtime of the solution by adding cases like, whether the sum of all the stick’s lengths is a multiple of 4 or not?.

Also, if any stick length is strictly greater than the sum/4, then we cannot build the matchstick.

Code

Matchsticks to Square C++ Solution:

class Solution {
public:
    bool calc(int pos,vector<int> &nums,vector<long long int> &sides,long long int &tar){
        if(pos == nums.size()){
            if(sides[0]==tar && sides[1]==tar && sides[2]==tar && sides[3]==tar){
                return true;
            }
            return false;
        }
        
        for(int i=0;i<4;i++){
            if(sides[i] + nums[pos] <= tar){
                sides[i] += nums[pos];
                if(calc(pos+1,nums,sides,tar)){return true;}
                sides[i] -= nums[pos];
            }
        }
        
        return false;
    }
    bool makesquare(vector<int>& matchSticks) {
        
        long long int sum = 0;
        int n = matchSticks.size();
        for(int i=0;i<n;i++){
            sum += matchSticks[i];
        }
        
        if(sum%4){return false;}
        // If sum is not divisible by 4 return false.
        if(n<4){return false;}
        // if number of matchsticks are less than 4 then square cannot be formed return false.
        long long int tar = sum/4;
        
        vector<long long int> sides(4,0);
        //To store the length od each side.
        
        
        sort(matchSticks.begin(),matchSticks.end(),greater<int>());
        //sorting matchSticks in decreasing order.
        
        return calc(0,matchSticks,sides,tar);
    }
};

Matchsticks to Square Java Solution:

import java.util.HashMap;
import java.util.Collections;

class Solution {
    public List<Integer> nums;
    public int[] sums;
    public int possibleSquareSide;

    public Solution() {
        this.sums = new int[4];
    }

    // Depth First Search function.
    public boolean dfs(int index) {

        // If we have exhausted all our matchsticks, check if all sides of the square are of equal length
        if (index == this.nums.size()) {
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
        }

        // Get current matchstick.
        int element = this.nums.get(index);

        // Try adding it to each of the 4 sides (if possible)
        for(int i = 0; i < 4; i++) {
            if (this.sums[i] + element <= this.possibleSquareSide) {
                this.sums[i] += element;
                if (this.dfs(index + 1)) {
                    return true;
                }
                this.sums[i] -= element;
            }
        }

        return false;
    }

    public boolean makesquare(int[] nums) {
        // Empty matchsticks.
        if (nums == null || nums.length == 0) {
            return false;
        }

        // Find the perimeter of the square (if at all possible)
        int L = nums.length;
        int perimeter = 0;
        for(int i = 0; i < L; i++) {
            perimeter += nums[i];
        }

        this.possibleSquareSide =  perimeter / 4;
        if (this.possibleSquareSide * 4 != perimeter) {
            return false;
        }

        // Convert the array of primitive int to ArrayList (for sorting).
        this.nums = Arrays.stream(nums).boxed().collect(Collectors.toList());
        Collections.sort(this.nums, Collections.reverseOrder());
        return this.dfs(0);
    }
}

Complexity Analysis for Matchsticks to Square Leetcode Solution

Time Complexity

The overall time complexity of the solution is 4^n since, at each step of recursion, we are having 4 choices hence, O(4^N) is the worst-case time complexity. The runtime of the solution is exponential.

Space Complexity

The recursive stack space utilized is O(n), where n is the number of matchsticks, so the overall space complexity is O(n).