[BUG] - 256. Paint House #26359
Description
LeetCode Username
jilsonjoseph
Problem Number, Title, and Link
Bug Category
Editorial
Bug Description
Correction in Time Complexity Explanation in the Editorial Solution Approach 1.
Corrections highlighted below.
Without writing code, we can get a good idea of the cost. We know that at the very least, we'd have to process every valid permutation. The number of valid permutations doubles with every house added. With 4 houses, there were 24 permutations. If we add another house, then all of our permutations for 4 houses could be extended with 2 different colors for the 5th house, giving 48 permutations. Because it doubles every time, this is O(n^2). -> O(2^n)
It'd be even worse if we generated all permutations of 0, 1, and 2 and then pruned out the invalid ones. There are O(n^3) -> O(3^n) such permutations in total.
Language Used for Code
None
Code used for Submit/Run operation
No response
Expected behavior
O(n^2). -> O(2^n)
O(n^3) -> O(3^n)
Above corrections in TC Explanation for approach 1 in Editorial
Screenshots
No response
Additional context
No response