When I first read this problem, I think this is very similar to the problem of finding the convex hull of a set of points. The optimal solution to do this is O(nlogn). I haven't code it up yet, but from reading what's on the discussion, it seems that O(nlogn) is the best run time. It might be an overkill to think this way.
zkytony
@zkytony
Posts made by zkytony

Convex Hull

[Python] Doubly linked list and dictionary. Easy to understand
I think this is a very typical solution. If you have any suggestions, please let me know! It is O(1) set and get.
Each node in the list corresponds to a keyvalue pair in the hash table. When we insert new keyvalue pair into the cache, we also add a node to the front of the list. When the cache is full and we still need to add data to it, we basically remove the last element in the list, because it is least recently used. When we actually have a cache hit, we can simply bring the corresponding node to the front of the list,by removing it (constant time for doubly linked list) then prepending it to the list.
class DLLNode: def __init__(self, data, prev=None, next=None): self.data = data self.prev = prev self.next = next class DLL: def __init__(self): self.head = None self.tail = None def prepend(self, dllnode): if self.head is None: self.head = dllnode self.tail = dllnode else: self.head.prev = dllnode dllnode.next = self.head self.head = dllnode def append(self, dllnode): if self.head is None: self.head = dllnode self.tail = dllnode else: self.tail.next = dllnode dllnode.prev = self.tail self.tail = dllnode def remove(self, dllnode): """Constant time removal in DLL""" nextnode = dllnode.next prevnode = dllnode.prev if nextnode is None and prevnode is None: self.head = None self.tail = None else: if nextnode is not None: nextnode.prev = prevnode else: # We are removing the tail node self.tail = prevnode if prevnode is not None: prevnode.next = nextnode else: # We are removing the head node self.head = nextnode if dllnode != self.tail and dllnode != self.head: dllnode.next = None dllnode.prev = None class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ self.data = {} self.capacity = capacity self.dll = DLL() def get(self, key): """ :rtype: int """ if key in self.data: self.__increasePriority(key) return self.data[key][0] else: return 1 def set(self, key, value): """ :type key: int :type value: int :rtype: nothing """ if key in self.data: self.__increasePriority(key) self.data[key] = (value, self.data[key][1]) else: if len(self.data) == self.capacity: self.__evict(key) newnode = DLLNode(key) self.dll.prepend(newnode) self.data[key] = (value, newnode) def __evict(self, key): lru_node = self.dll.tail self.dll.remove(lru_node) self.data.pop(lru_node.data, None) def __increasePriority(self, key): _, dllnode = self.data[key] self.dll.remove(dllnode) self.dll.prepend(dllnode)

Typical python DFS solution. Faster than 80.36%
Not very smart Python solution with DFS. I wonder why it is faster than 80.36% python submissions... Run time O(n!n)
def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ used = set({}) current = [] solutions = [] self.dfs(nums, used, current, solutions) return solutions def dfs(self, nums, used, current, solutions): if len(used) == len(nums): solutions.append(current[:]) return for i in range(len(nums)): if i not in used: used.add(i) current.append(nums[i]) self.dfs(nums, used, current, solutions) current.pop() used.remove(i)

RE: Does anyone come up with a nonrecursion solution?
I think my solution is pretty weird.
def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ S = {} solution = [] S['('] = (1,0) while True: if len(S.keys()) == 0: break str, tup = S.popitem() o, c = tup if o == n: if c == n: solution.append(str) continue else: S[str+')'] = (o, c+1) elif o == c: S[str+'('] = (o+1, c) else: S[str+'('] = (o+1, c) S[str+')'] = (o, c+1) return solution

DP with python, O(n) time O(1) space. Straightforward explanation.
This problem is not obvious to me (it is medium in my opinion). I spent quite some time, and came up an idea of dynamic programming approach. Let us use
p(n)
to denote the color of post n, usew(n)
to denote the number of ways to paint post n, and user(n)
to denote the returned number of ways to paint n posts.for n == 0, return 0 or 1 # Up to you; for n == 1, return k; for n == 2, if p(2) == p(1), then r(n)=k, because the two have the same color. if p(2) != p(1), then r(n)=k(k1) because w(1)=k, w(2)=k1. for n >= 3, r(n) = r(n,when p(n)==p(n1)) + r(n,when p(n)!=p(n1))
When
p(n1) == p(n)
, we requirep(n2) != p(n1)
. This is the same as if we are painting (n1) posts and the last two posts have different colors, which meanssame(n)=diff(n−1)
.When
p(n1) != p(n)
, we haver(n−1)
ways to paint the first n1 posts, andk−1
ways to paint the nth post. Sodiff(n)=r(n−1)(k−1)
.Note that
r(n−1)
is really just the sum ofsame(n−1)
anddiff(n−1)
.Code:
def paintFence(n, k): if n == 0: return 0 if n == 1: return k # Now n >= 2. # Initialize same and diff as if n == 2 same = k diff = k*(k1) for i in range(3,n+1): r_prev = same + diff # r(i1) same = diff # same(i)=diff(i1) diff = r_prev*(k1) return same + diff

Simple python code. Easy to understand
Strobogrammatic numbers are special. Reverse each character by 180 degrees if possible, then reverse, and compare with original number. For example: 986 ==> 689 ==> 986 (True)
class Solution(object): def isStrobogrammatic(self, num): flipped = "" stromap = {'same': ['0','1','8']} for d in num: if d in stromap['same']: flipped += d elif d == '6': flipped += '9' elif d == '9': flipped += '6' else: return False if len(flipped) == 0: return False # Reverse flipped return flipped[::1] == num

C bitwise solution, with explanation in comments
bool isPowerOfTwo(int x) { // x = 4 // 0000 0000 0000 0000 0000 0000 0000 0100 // x = 8 // 0000 0000 0000 0000 0000 0000 0000 1000 // ... // We see that if x is power of 2, there will be only 1 at MSB // Also, x  1 gives all ones after the previous // 1 digit: e.g. x = 8  1 ==> 0000 0000 ... 0111 // So, x & (x  1) is 0 only for x is power of 2 // For zero, just return 1; // For negative number, use ~0 xor it to turn it // positive; e.g. x = 4 // 1111 1111 1111 1111 1111 1111 1111 1100 ^ // 1111 1111 1111 1111 1111 1111 1111 1111 // 0000 0000 0000 0000 0000 0000 0000 0011 > operand for & int sign_x = x >> 31; int minus = ((~0) ^ sign_x); return !((x & (x + minus)) + !x); }

Java solution with explanation in comments, beats 94%. One stack, custom stack implementation.
Java is good for solving problems that require implementing a whole class.
public class MinStack { private StackElement top; private int minVal; /** initialize your data structure here. */ public MinStack() { top = null; minVal = Integer.MAX_VALUE; } public void push(int x) { if (x <= minVal) { // x is minimum. This means 'min' is now second minimum. Push it on stack. // Update min. This way, the next time we pop the minimum value, we know // the second minimum value is right below the one we poped. Then we can just // pop that second minimum value and update 'min' (Because we pushed the second // minimum value to the stack twice). this.plainPush(minVal); minVal = x; } // Push this element to the stack always. this.plainPush(x); } public void pop() { // If the next element to pop is the minimum element, we need to // reassign the minimum value to the value of the element right // below the currently popped element, and pop that new min as well // to avoid duplicate. if (top.val == minVal) { this.plainPop(); // Pop the minimum element minVal = this.top(); // Second minimum element value this.plainPop(); // Pop the second minimum element } else { this.plainPop(); // Just pop it. No need to update minimum value. } } public int top() { return top.val; } public int getMin() { return minVal; } private void plainPush(int x) { if (top == null) { top = new StackElement(x); } else { StackElement newTop = new StackElement(x); newTop.next = top; top = newTop; } } public void plainPop() { if (top == null  top.next == null) { return; } top = top.next; } private class StackElement { public int val; public StackElement next; public StackElement(int val) { this.val = val; this.next = null; } } }

Short simple python solution
Nothing fancy. It is very simple, normal and it works!
class Solution(object): def generatePossibleNextMoves(self, s): result = [] for i in range(len(s)1): if s[i:i+2] == "++": state = s[:i] + "" if i+2 < len(s): state += s[i+2:] result.append(state) return result

Straightforward DFS with Python
When we hear "longest path" in "binary tree", DFS is very attractive.
class Solution(object): def longestConsecutive(self, root): """ :type root: TreeNode :rtype: int """ if root is None: return 0 return self.__longest(root, None, 0) + 1 def __longest(self, root, parent, count): if parent is not None: if root.val  parent.val == 1: count += 1 else: count = 0 countLeft = 0 countRight = 0 if root.left is not None: countLeft = self.__longest(root.left, root, count) if root.right is not None: countRight = self.__longest(root.right, root, count) return max(count, countLeft, countRight)