educative.io

Complexity analysis of Matchsticks To Square

Courses
,
#1

The optimal solution runs in O(n*2^n) time and O(2^n) space.

The recommended approach seems to have a branching factor of four and a branching depth of n, meaning a time complexity of O(4^n) and space complexity of O(n). Am I interpreting that correctly? If so, is the optimal solution different from the recommended one?

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Matchsticks to Square - Grokking Coding Interview Patterns in Python

1 Like
#2

Hi @Isaac_Haseley,

The recommended approach involves using backtracking and indeed results in a time complexity of O(4^N) and a space complexity of O(N). However, the optimal solution, which has a time complexity of O(N * 2^N) and a space complexity of O(2^N), can be achieved through dynamic programming.

Thank you for bringing this to our attention. We will be making updates to the lesson promptly.

Happy learning!