[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] 164. Maximum Gap

A really smart solution using pigeon hole principle and bucket sort...

---

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

---

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        min_v, max_v = min(nums), max(nums)
        if min_v == max_v: return 0
        
        buckets = [[] for _ in range(len(nums)+1)]
        for num in nums:
            bkt = (num - min_v) * len(nums) / (max_v - min_v)
            buckets[bkt].append(num)
        
        i = 0
        res = 0
        while i < len(buckets) - 1:
            k = i + 1
            while len(buckets[k]) == 0:
                k = k + 1
            res = max(res, min(buckets[k]) - max(buckets[i]))
            i = k
        return res

[Leetcode] Sudoku Solver

Okay, this is a pretty classical backtracking problem. There are some details of writing recursion in python that I can't say I fully understand.

---

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

---

I referred to this post to finally get my program running. One thing I did not do is to "return True/False", but handled it like permutation that kind of questions. I do think "return True/False" make sense, but I don't know why I did not think it necessary.

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        
        self.solve(board, 0, 0)
    
    def solve(self, board, i, j):
        
        def candidates(i, j):
            not_available = []
            for x in range(9):
                if board[i][x] != '.':
                    not_available.append(board[i][x])
                if board[x][j] != '.':
                    not_available.append(board[x][j])
            grid_x, grid_y = i / 3, j / 3
            for x in (0, 1, 2):
                for y in (0, 1, 2):
                    if board[grid_x * 3 + x][grid_y * 3 + y] != '.':
                        not_available.append(board[grid_x * 3 + x][grid_y * 3 + y])
            return [i for i in '123456789' if i not in not_available]
        
        if i == 9: 
            return True
        elif j == 9:
            return self.solve(board, i+1, 0)
        else:            
            if board[i][j] == '.':
                cands = candidates(i, j)
                if not cands:
                    return False
                for cand in cands:
                    board[i][j] = cand
                    if self.solve(board, i, j + 1):
                        return True
                    board[i][j] = '.'
                return False
            else:
                return self.solve(board, i, j+1)

[Leetcode] Smallest Range

This is a smart use of heap.

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.

class Solution(object):
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        h = []
        max_v = -10**5 - 1
        min_v = 10**5 + 1
        for i, num in enumerate(nums):
            h.append([num[0], i, 0])
            if max_v < num[0]: max_v = num[0]
            if min_v > num[0]: min_v = num[0]
        res = [min_v, max_v]
        
        heapq.heapify(h)
        
        while True:
            v, list_index, element_index = heapq.heappop(h)
            if element_index == len(nums[list_index]) - 1:
                return res
            heapq.heappush(h, [nums[list_index][element_index+1], list_index, element_index+1]) 
            if nums[list_index][element_index+1] > max_v:
                max_v = nums[list_index][element_index+1]
            if max_v - h[0][0] < res[1] - res[0]:
                res = [h[0][0], max_v]

[Leetcode] 131. Palindrome Partitioning

Well, doing leetcode problems can be addictive - I used to go to Facebook everyday - not any more and I don't feel missed at all. Now, somehow I must do some leetcode problems, otherwise I just feel wrong. It sometimes gets hard and frustrating. But I guess as I read it somewhere, in our nature human beings just love something bitter, like beer, coffee, as well as challenges (but have to be meaningful and able to make progress and intellectually fulfilling, at least for me).

---

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

This problem is similar to subset problem, my solution is not the "optimal" one, but very intuitive.

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if len(s) == 0: return [[]]
        if len(s) == 1: return [[s]]
        
        res = []
        for i in range(1, len(s)+1):
            part1 = s[:i]
            part2 = s[i:]
            #print part1, part2
            if part1 == part1[::-1]:
                tmp_res = self.partition(part2)
                #print tmp_res
                for r in tmp_res:
                    res.append([part1] + r)
        return res

[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] 199. Binary Tree Right Side View

I referred to this solution: it's really succinct and ingenious. I am a little far from this level of coding.

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

# 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 rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def collect(node, depth):
            if not node:
                return
            if len(view) == depth:
                view.append(node.val)
            collect(node.right, depth+1)
            collect(node.left, depth+1)
        
        view = []
        collect(root, 0)
        return view

[Leetcode] 43. Multiply Strings

Looks like a simple problem. I thought to use Karatsuba algorithm to speed the program up, but it turns out not necessary - as the longest input will just be less than 180, then $O(180^2)$ is definitely good enough.

I briefly looked at some other people's hints and see that the key to this problem is that: num1[i] * num2[j] will be at final result's [i+j] position and [i+j+1] for the carrier.

---

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        n1, n2 = len(num1), len(num2)
        res = [0 for _ in range(n1+n2+1)]
        num1 = num1[::-1]
        num2 = num2[::-1]
        for i in range(n1):
            b1 = int(num1[i])
            for j in range(n2):
                b2 = int(num2[j])
                cur_b = res[i+j] + b1 * b2
                if cur_b <= 9:
                    res[i+j] = cur_b
                else:
                    res[i+j] = cur_b % 10
                    res[i+j+1] += cur_b / 10
        res = map(str, res)
        res = ''.join(res[::-1])
        i = 0
        while i < len(res) - 1 and res[i] == '0':
            i += 1
        return res[i:]

[Leetcode] 545. Boundary of Binary Tree

Update: Hmm, I feel more comfortable of doing normal problems now. Seems that keeping doing these problems will soon be limited. Once I become comfortable of doing something, I just don't feel like doing it all the time any more... Luckily, computer science is such a broad subject and it is easy to improve anywhere anytime. But then, improving on new skillsets or working on harder problems will be too hard again.. I will struggle over them for a long time.. Ahh, I guess I will just live this kind of depressed life for the rest of my life...

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged.

Example 1

Input:
  1
   \
    2
   / \
  3   4

Ouput:
[1, 3, 4, 2]

Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Example 2

Input:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
       
Ouput:
[1,2,4,7,8,9,10,6,3]

Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

Idea is that the boundary is made of left arm, all the leaves, and right arm. Then, just find all of them. 

Here is the code:

# 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 boundaryOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return []
        if not root.right and not root.left: return [root.val]
        
        res = [root.val]
        m = []
        self.find_leaves(root, m)
        l = []
        self.find_left(root.left, l)
        r = []
        self.find_right(root.right, r)
        #print m, l, r
        return res + l + m + r[::-1]
    
    def find_leaves(self, node, m):
        if not node:
            return 
        elif not node.right and not node.left:
            m.append(node.val)
            return
        else:
            self.find_leaves(node.left, m)
            self.find_leaves(node.right, m)
            
    def find_left(self, node, l):
        if not node:
            return
        if not node.left and not node.right:
            return
        l.append(node.val)
        if not node.left:
            self.find_left(node.right, l)
        else: self.find_left(node.left, l)
        
    def find_right(self, node, r):
        if not node:
            return
        if not node.left and not node.right:
            return
        r.append(node.val)
        if not node.right:
            self.find_right(node.left, r)
        else:
            self.find_right(node.right, r)
        

[Leetcode] Course Schedule

This is a classical graph problem - the key is to detect cycle in a directed graph. This is usually done by flagging a node by 0, 1, 2, where 0 represents never visited, 1 in the stack, 2 visited. If at any time, we visited a node which status is 1, that it is in stack yet we visited it again, then it means that there is a cycle.

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Code: 

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
            
        visited = [0 for _ in range(numCourses)]
        
        def dfs(node, visited):
            visited[node] = 1
            for v in g[node]:
                if visited[v] == 1:
                    return False
                elif visited[v] == 0:
                    if not dfs(v, visited):
                        return False
            visited[node] = 2
            return True
            
        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i, visited):
                    return False
        return True

[Leetcode] Longest Valid Parentheses

I really enjoyed solving this problem. The debugging process let me see the fallacies my thought has been. 

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

---

We are not unfamiliar with this kind of problems: "longest increasing subsequence", "longest palindrome substring", "max money we can rob". All these questions fall to dynamic programming category. Easy or common dynamic programming isn't hard to understand or even to conceive one compared to greedy problems, IMAO, but it takes practice.

The key to dynamic programming is to have a recurrence formula. When designing it, think about what kind of variables or current we need to know to get the next state. Of course, this variable has to help you get the final answer.

In this problem, a first thought would be devise a DP array that stores the length of longest valid parentheses (LVP).  However, if we know the s[i]'s LVP, it seems not helping me to know s[i+1]'s LVP, because the matching pair would be far back. But we are asking substring, meaning that if s[i] is in a solution, then s[i+1] might be in the solution, and the s[i+1]'s matching pair should be the one back s[i]'s matching pair. Therefore, if we record the s[i] matching pair's position, we would be able to know s[i+1]'s matching pair. If it doesn't match anything, then we just make the index its value.

Okay, now we have an array dp, which stores the index of the matching pair. So far so good. But it can't handle "()()" situation. Yes, I realize it from testing...

So the next step is to integrate the dp array. Here is the code:

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 1: return 0
        # first round to get the position of the matching pair
        dp = [i for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == '(':
                continue
            k = i - 1
            while dp[k] != k and k > 0:
                k = dp[k] - 1
            if s[k] == '(' and k >= 0:
                dp[i] = k
            else:
                dp[i] = i
        # second round to get the final answer, basically
        # to connect case like this: "()()"
        i = len(s) - 1
        res = 0
        while i > 0:
            if dp[i] != i:
                tmp_res, k = 0, i
                while dp[k] != k and k > 0:
                    tmp_res += (k - dp[k] + 1)
                    k = dp[k] - 1
                res = max(res, tmp_res)
                i = k
            else:
                i -= 1
        return res