czxttkl

https://leetcode.com/problems/minimum-size-subarray-sum/

Code 

import sys

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        p1 = p2 = 0
        cum = 0
        min_len = sys.maxint        

        for num in nums:
            cum += num
            if cum >=s:
                min_len = min(min_len, p1-p2+1)
                while p2 < p1:
                    if cum-nums[p2] >=s:
                        cum = cum-nums[p2]
                        p2 += 1
                        min_len = min(min_len, p1-p2+1)
                    else:
                        break
            p1 += 1

        return 0 if min_len == sys.maxint else min_len

Idea

Remember that all numbers are positive. You can have a fast pointer `p1` and a slow pointer `p2`. You first make the fast pointer to traverse the numbers until sum from nums[p2] to nums[p1] is more than s. Then, you start to move `p2` forward until the sum from nums[p2] to nums[p1] is no more than s anymore. In total, `p1` and `p2` both traverse at most O(N) distance. So the time complexity of the algorithm is O(N). Since we don’t require additional space, the space complexity of the alogrithm is O(1).

https://leetcode.com/problems/implement-trie-prefix-tree/

Code

class TrieNode(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nodes = dict()
        self.is_word = False 


class Trie(object):

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        p = self.root
        for idx, ch in enumerate(word):
            if not p.nodes.get(ch, None):         
                p.nodes[ch] = TrieNode()
            p = p.nodes[ch]
            if idx==len(word)-1:
                p.is_word = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        p = self.root
        for idx, ch in enumerate(word):
            if not p.nodes.get(ch, None):
                return False
            p = p.nodes[ch]
            if idx==len(word)-1 and not p.is_word:
                return False
        
        return True
        

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie
        that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        p = self.root
        for idx, ch in enumerate(prefix):
            if not p.nodes.get(ch, None):
                return False
            p = p.nodes[ch]
            
        return True
        

# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")

Idea

See idea about Trie:

http://www.geeksforgeeks.org/trie-insert-and-search/

https://leetcode.com/discuss/34840/maybe-the-code-is-not-too-much-by-using-next-26-c

https://leetcode.com/problems/contains-duplicate-iii/

Code

import sys

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if not nums or k <=0 or t<0:
            return False

        def tran_num(org_num):
            return org_num + sys.maxint     
            
        def to_bucket(num_tran):
            return num_tran / (t+1)

        bucket_dict = {}
        for idx, num in enumerate(nums):
            num_tran = tran_num(num)
            bucket = to_bucket(num_tran)        
            
            if bucket_dict.get(bucket) or \
                bucket_dict.get(bucket+1, num_tran+t+1) - num_tran <=t or \
                num_tran - bucket_dict.get(bucket-1, num_tran-t-1) <=t:
                return True
                
            if idx >=k:
                old_bucket = to_bucket(tran_num(nums[idx-k]))
                bucket_dict.pop(old_bucket)
            
            bucket_dict[bucket] = num_tran

        return False

Idea (https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation)

We want to check if a number differs at most t with any of previous k elements by checking if any two numbers fall into the same bucket we shall create.

To do so, we first need to add every number by `sys.maxint`. This is to make sure every number can be transformed into an non-negative number so that we don’t need to worry about how to make different bucketing rules for negative and positive numbers.

For one transformed number, `num_tran`, we assign it to bucket `num_tran/(t+1)`. If two numbers fall into the same bucket, they must be of at most t difference. However, two numbers can also differ at most t if they are from two adjacent buckets. That’s why we have three condition checkings at line 25-27.

bucket_dict always has at most K elements. We maintain that by always popping out idx-k element. (line 30-32)

The time complexity is O(N) and the space complexity is O(K). 

Idea II

You can also maintain a balanced binary search tree of size K. Then you can always get the closest value of nums[i] (current visiting number) in the binary search tree in O(logK). If the closest value is within t of nums[i]’s range, you can return True.  Since you need to traverse all numbers in nums, and for each number you need to search in O(logK) time, the time complexity is O(NlogK) and the space complexity is O(K).

Reference:

https://leetcode.com/discuss/38177/java-o-n-lg-k-solution

https://leetcode.com/problems/graph-valid-tree/

Overall idea

We need to check two properties to determine whether a set of edges form a valid tree:

1. it has n-1 edges
2. it is acyclic

Code 1 (Union Find)

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        union_arr = range(n)
        def find_union(p):
            if  union_arr[p] == p:
                return p
            else:
                return find_union(union_arr[p])        
                
        for p1, p2 in edges:
            p1_set = find_union(p1)        
            p2_set = find_union(p2)
            if p1_set == p2_set:
                return False
            union_arr[p1_set] = p2_set
        
        return len(edges) == n-1

Idea

This algorithm uses an idea called union find. You first initialize each node so that each node itself forms a node set. (We use `union_arr` to record which set a node belongs to).  As we traverse all edges, we will find connected components. The union find algorithm makes sure that every node in a connected component will point to a same node set by using `find_union` function. Therefore, if we see a new edge with two points in the same node set, we will return False because the edge makes a cycle in the graph.  If no cycle is found, we will finally check if there are exactly `n-1` edges to form a tree rather than disjoint parts in the graph. (line 22)

Reference

https://leetcode.com/discuss/52563/ac-java-union-find-solution

http://www.geeksforgeeks.org/union-find/

Updated 2016/09/30:

The union find algorithm can also be used to find connected components in an undirected graph. See leetcode 130: Surrounding Regions.

Code 2 (DFS)

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        adj = {s:[] for s in range(n)}
        for p1, p2 in edges:
            adj[p1] += [p2]
            adj[p2] += [p1]
        stk = [0]
        while stk:
            cur = stk.pop()
            stk.extend(adj.pop(cur, []))
        return len(edges)==n-1 and not adj

Idea

We start to visit all nodes from node 0. (line 12) If we finish traversing all reachable nodes but there are still some adjacency matrix entry left then we know the given edges actually form multiple separate graphs. Therefore we should return False.

Code 3(BFS)

from collections import deque
class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        adj = {s:[] for s in range(n)}
        for p1, p2 in edges:
            adj[p1] += [p2]
            adj[p2] += [p1]
        q = deque()
        q.append(0)
        while q:
            cur = q.popleft()
            q.extend(adj.pop(cur, []))
        return len(edges)==n-1 and not adj

Idea

Similar idea as in code 2. But you implement the traversal of nodes using `deque`.

https://leetcode.com/problems/validate-binary-search-tree/

   1
  / \
 2   3
    /
   4
    \
     5

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 isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.helper(root, None, None)
        
    def helper(self, root, min, max):
            if not root:
                return True

            if (min is not None and root.val <= min) or (max is not None and root.val >= max):
                return False
            
            return self.helper(root.left, min, root.val) and self.helper(root.right, root.val, max)

Idea

Just check the basic rule of BST: all nodes in a node’s left subtree should be less than the node’s value. all nodes in a node’s right subtree should be larger than the node’s value. 

Another 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 isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.prev = None
        return self.inorder(root)

    def inorder(self, root):
        if not root:
            return True
        if not self.inorder(root.left):
            return False
        if self.prev and self.prev.val >= root.val:
            return False
        self.prev = root
        return self.inorder(root.right)
                

Idea

We use another property of BST: the inorder traversal of BST should return us an ascending order of numbers. We can do inorder traversal with a variable (`prev` in our code) recording which node we visited before we are visiting the current node. Whenever we find `prev.val` is larger than the current node’s value, we report invalidity of the tree.

https://leetcode.com/problems/rotate-list/

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return None
            
        len_cnt = 0
        tail_reach = False
        fast = head
        while k:
            len_cnt += 1
            if not fast.next:
                tail_reach = True
                fast = head
            else:
                fast = fast.next
            k -= 1
            if tail_reach:
                k %= len_cnt
        
        if fast == head:
            return head
        
        slow = head
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        fast.next = head
        new_head = slow.next
        slow.next = None
        return new_head
                
           
        
        

Idea

Use `fast` pointer to traverse `k` nodes. Then use a slow pointer to traverse from head. Both fast and slow pointers traverse one node by one node, until fast pointer reaches the end  (line 35-37). Therefore, the slow pointer traverses exactly len(nums)-k nodes. Its next node should be the new head.

More succinct code can be found: https://discuss.leetcode.com/topic/14470/my-clean-c-code-quite-standard-find-tail-and-reconnect-the-list

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Code

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        if len(nums)==1:
            return 1
            
        prev = nums[0]
        del_cnt = 0
        for i in xrange(1, len(nums)):
            idx = i- del_cnt
            if nums[idx] == prev:
                nums.pop(idx)
                del_cnt += 1
            else:
                prev = nums[idx]
            
        return len(nums)
        

Idea

My code doesn’t only return the length of non-duplicated elements but also pop duplicated elements in the original array.

Code that does not need to pop: https://discuss.leetcode.com/topic/3102/my-solution-time-o-n-space-o-1

https://leetcode.com/problems/maximum-subarray/

import sys
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
            
        max_sum = -sys.maxint
        tmp_sum = 0
        
        for i in xrange(0, len(nums)):
            if tmp_sum + nums[i] >= 0:
                tmp_sum += nums[i]
                max_sum = max(max_sum, tmp_sum)
            else:
                tmp_sum = 0
                # for corner case where the array only contains negative nums
                max_sum = max(max_sum, nums[i])
                
        return max_sum

Idea

We create a variable `tmp_sum` to record what is the maximum sum you have seen. If you visit a positive number, you can definitely add it to `tmp_sum`; if you visit a negative number, as long as `tmp_sum` is still larger than 0, you can add it also. If a negative number makes `tmp_sum` to negative, that means the maximum sum cannot happen by including this negative number and any arbitrary numbers before it.

Another idea is to use divide and conquer:

https://leetcode.com/discuss/694/how-solve-maximum-subarray-using-divide-and-conquer-approach

Step1. Select the middle element of the array. So the maximum subarray may contain that middle element or not.

Step 2.1 If the maximum subarray does not contain the middle element, then we can apply the same algorithm to the the subarray to the left of the middle element and the subarray to the right of the middle element.

Step 2.2 If the maximum subarray does contain the middle element, then the result will be simply the maximum suffix subarray of the left subarray plus the maximum prefix subarray of the right subarray

Step 3 return the maximum of those three answer.

Here is a sample code for divide and conquer solution. Please try to understand the algorithm before look at the code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(n==0) return 0;
        return maxSubArrayHelperFunction(A,0,n-1);
    }
    
    int maxSubArrayHelperFunction(int A[], int left, int right) {
        if(right == left) return A[left];
        int middle = (left+right)/2;
        int leftans = maxSubArrayHelperFunction(A, left, middle);
        int rightans = maxSubArrayHelperFunction(A, middle+1, right);
        int leftmax = A[middle];
        int rightmax = A[middle+1];
        int temp = 0;
        for(int i=middle;i>=left;i--) {
            temp += A[i];
            if(temp > leftmax) leftmax = temp;
        }
        temp = 0;
        for(int i=middle+1;i<=right;i++) {
            temp += A[i];
            if(temp > rightmax) rightmax = temp;
        }
        return max(max(leftans, rightans),leftmax+rightmax);
    }
};

The divide and conquer algorithm takes O(nlogn) time and O(n) space just as merge sort.

Code

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        res = ""
        arr = range(1, n+1)
        k = k-1
        for i in xrange(n-1, -1, -1):
            idx, k = divmod(k, math.factorial(i))
            res += str(arr.pop(idx))
        return res

Idea

Always try to determine which is the next character to append.

For example,

n=3, we have 6 permutations in total:

123
132
213
231
312
321

If k=3, we know we should return 213. We should first determine we need to append “2”. How to determine that? we know that there are (n-1)! permutations that start with “1”, “2” and “3” each. So the integer quotient of (k-1)/(n-1)! represents the index (0-based) of the number in the original array (1,2,3).  

You keep doing this iteratively to get the final result.