Two unrelated problem for this week. First is a union find application, second is a traditional problem, converting non-tail-recursion into interation,

128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

My accepted code can be found here

O(N) complexity is tricky here, since time complexity for many algorithms and data structures are O(N) ON AVERAGE, instead of as the common sense “traversing the array only once”. And insertion and looking up for hash map and union find are O(1) on average.

The tag of the problem tell me this problem can be solved by union find, and problem become a lot simpler. The basic idea is continuouly connect all consecutive number in the union find, and at last get the size of the largest connected component. And this algorithm is obviously O(n), since while traversing the array, every operation on the element is O(1), looking up element in hash map, connect nodes in union find etc. And the size of connected components can be maintain dynamically in O(1) each time, since all we care about is the size of the roots, sizes of leaves don’t really matter.

So the algorithm is as follow:

LongestConsecutiveSequence(arr: int[]):
    let m = empty hash map of int -> int
    let uf = empty union find with size length(arr)
    for each element e in arr with index i:
        if e in m then continue
        add e -> i to m
        if e - 1 in m with value j
            then uf.union(i, j)
        if e + 1 in m with value k
            then uf.union(i, k)
    return uf.maxCCSize

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values. Note: Recursive solution is trivial, could you do it iteratively?

My accepted code can be found here

This problem is a very traditional one. And we iteratively maintain the recursion stack and store infomation into the stack. And during the iteration, we retrieve the information from stack and take actions according to the infomation.

And in the postorder traversal problem, the infomation in the stack is

  1. the current tree node
  2. the traverse state of the subtree of the node

If the neither subtree of the node is traversed, count is set to 0 If only left node is traversed, count is set to 1 If both node is traversed, set count to 2

So we take actions according to the node and count, the algorithm is as follow:

PostorderTraverse(root: Node) {
    let result = empty int array
    let stk = empty stack of pair<int, Node>
    for stk is not empty:
        let t = reference to top element of stk
        if t.node is null then continue
        case t.node of
            2 then
                append t.node.value to result
                stk.pop
            0 then
                stk.push {0, t.node.left}
                increment t.node.count
            1 then
                stk.push {1, t.node.right}
                increment t.node.count
    return result
}

Last

I thought of writing an iterative tree traversal algorithm before but didn’t ever take that into action. One of my teachers said it was a lot lot harder than the recursive version. It is, but … well I think it’s simpler to implement than I thought before..