Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Trang Luong
Wrong complexity with solution

Trang Luong

Mar 2, 2025

Based on the knowledge in the previous post, path compression should reduce the time complexity to O(logN). However, in this solution, it's somehow get to "The find operation with path compression has an amortized time complexity of , which is almost equal to , where  is the inverse Ackermann function, which is very close to constant." It should only get to the almost constant time complexity if path compression was to be used with combination of union by rank or union by size

0

0

Comments
Comments