LC-2509 Hard LeetCode

2509. Cycle Length Queries in a Tree

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 58% Topics: Array, Tree, Binary Tree

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(q * n)
# Space: O(1)

# tree, lca
class Solution(object):
    def cycleLengthQueries(self, n, queries):
        """
        :type n: int
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        result = []
        for x, y in queries:
            cnt = 1
            while x != y:
                if x > y:
                    x, y = y, x
                y //= 2
                cnt += 1
            result.append(cnt)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT