[Leetcode] 388. Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

---

I solved this problem about 7 months ago - when I first started to tackle these Leetcode problems. Back then, I wasn't proficient in any algorithms. But somehow, I managed to solve this problem with an extremely messy code. Ever since I got that job offer, I thought I should re-do some of the problems or focus those problems that require some modeling (i.e., Google problems).

This problem is on the easier side of this kind. It is very obvious files and folders are organized in tree structure. Only if we have a well-organized tree structure, then we can basically use backtracking to find out the answers. However, the input is a string. But, by looking at the string, we can see that the number of '\t' in the element is the same as the level of that elements. For example, '\tsubdir1', '\t\tfile.txt' are in the first, second level of the file organization, respectively.

We can't easily do a tree traverse on this type of string input, but hey, the elements order after input.split('\n') is similar to the  in-order traversal of the directory tree (here might be a forest).

Therefore, the abstraction of the problem will be:

Given the in-order traversal of a tree and each element's level, reconstruct the maximum length path from root to leaf where we only considers those leaves that contain '.' (file). 

Well, then we just use a stack, when the level is higher than the current level, meaning that the incoming element will be the children of current element; when lower, meaning that the incoming one is the parent; the same, siblings.

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        stack = []
        current_level = 0
        res = 0
        for name in input.split('\n'):
            #print stack, current_level
            tabs = name.split('\t')
            if len(tabs) - 1 == current_level:
                if stack:
                    stack.pop()
                stack.append(tabs[-1])
            elif len(tabs) -1 > current_level:
                stack.append(tabs[-1])
            else:
                for _ in range(current_level - len(tabs) + 2):
                    if stack: stack.pop()
                stack.append(tabs[-1])
            if '.' in tabs[-1]:
                res = max(res, len('/'.join(stack)))
            current_level = len(tabs) - 1
        return res

[Leetcode] 334. Increasing Triplet Subsequence

This problem reminds me of the fancy version of longest increasing subsequence problem ($O(n\log n)$ solution).

Let's look at an example array: 1, 2, -1, 1, -2, 3. When we go through the first two element, we are all good. Then, we encounter -1, here we face a decision, should we update the current minimum to -1?

Let's see why we should and why we shouldn't. -1 is a safer move than 1, what if later our solution is -1, 0, 1? Then we definitely want to update it. However, you might say, if we update it to -1, then 2 shouldn't be in our solution anymore, according to the "subsequence" rule.

Well, the answer is YES, but we only update the minimum, keeping the second minimum (which is 2 here).The argument is as following: when we keep the second minimum (call it min2), this means that we only count increasing when the next value is greater than min2. You see, by changing min1 to a smaller value, it doesn't really affect the decision we are going to make about adding an increasing element. However, if we see the next value is smaller than min2 but greater than min1, we then want to update min2.

In this way, we always keep track the safest possible value yet maintain the order we have for now.

In actual implementation, I used a stack instead of min1, min2. It turned out to be much easier to handle. Well, who knows such a seeming simple question took me good two hours to think through - this kind of question is very tricky.

---

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

---

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 3: return False
        
        counter = 1
        stack = []
        for i in nums:
            if len(stack) == 0:
                stack.append(i)
            elif i < stack[0]:
                stack[0] = i
            elif len(stack) == 1 and i > stack[0]:
                stack.append(i)
            elif len(stack) == 2 and stack[0] < i < stack[1]:
                stack[1] = i
            elif len(stack) == 2 and i > stack[1]:
                return True
        return False

[Leetcode] 145. Binary Tree Postorder Traversal

This is not a hard problem compared to some really hard ones. The key is to flag every node, if first in stack, 1, if all its children are in the stack, mark it as 2. Later, when encounter a node, if its flag is 1, then we push its children in the stack and mark it as 2; if it's 2, then we pop it and record the result. The order to put the children? First right, then left --> then we are able to see left first and then the right.

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        visited = {}
        stack = [root]
        visited[root] = 1
        res = []
        
        is_leaf = lambda node: not node.left and not node.right
        
        while stack:
            top = stack[-1]
            if visited[top] == 2 or is_leaf(top):
                top = stack.pop()
                res.append(top.val)
            else: 
                if top.right:
                    stack.append(top.right)
                    visited[top.right] = 1
                if top.left:
                    stack.append(top.left)
                    visited[top.left] = 1
                visited[top] = 2
        return res

[Leetcode] Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

1
    \
     2
    /
   3

return [1,2,3].

Preorder: root - left - right. When thinking about the stack property (first in, last out), we want to push right child before the left child, so that eventually we will access left child first.

This problem is really neat, letting me see more clearly the difference between BFS (using queue) and DFS (stack). Indeed, the structure of the program below is the same as BFS, except that we used a stack here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] stack = [root] res = [] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res