@lizzy0127 Sure! So the runtime of iterating over a list depends on what the list contains. If we are iterating over a list that's given to us as the input, this would definitely be O(n). If we are iterating over a constant sized list, this is considered an O(1) operation. The two hashes we have here that we iterate over are constant sized.
Waynex
@Waynex
Posts made by Waynex

RE: Python O(n) Time, O(1) Space

Elegant Python Solution (4 lines)
We iterate through numbers one at a time, and combine previously seen results with our number to add new results
To prevent duplicates, we store the results in a set. To do this we need to store the results as tuples (immutable lists), which we cast back to lists before returning. Note the interesting syntax needed to create a tuple of length 1
def subsets(self, nums): res = set([()]) for num in sorted(nums): res.update([item+(num, ) for item in res if item+(num, ) not in res]) return [list(item) for item in res]

RE: Python easy to understand solutions (DFS recursively, Bit Manipulation, Iteratively).
Here's an iterative version that accounts for duplicates.
We keep the result in a set instead of a list to prevent duplicates. To do this we need to store the results as tuples, which we cast back to lists before returning. Note the interesting syntax needed to create a tuple of length 1
def subsets(self, nums): res = set([()]) for num in sorted(nums): res.update([item+(num, ) for item in res if item+(num, ) not in res]) return [list(item) for item in res]

Iterative DFS with O(h) Memory (Python)
Keep track of the DFS as well as "pathsofar" using stacks. Both stacks are of length O(h) where h is the height of the tree. This is better than solutions that make a new "pathsofar" for every single leftright branching, which takes O(h^2) memory
def binaryTreePaths(self, root): if not root: return [] stack, res, path = deque([root]), [], [] while stack: node = stack.pop() if node == "pop": path.pop() continue path.append(str(node.val)) stack.append("pop") if not node.left and not node.right: res.append(">".join(list(path))) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res

RE: Java/Python, O(n) calls, O(1) space easy to understand solution
Great code! Not sure if the first loop was a typo, but here is what might be a corrected version. Can someone clarify if these corrections are better, or if the original intended for the first check to be nonexhaustive?
Basically the first check only covers 0x instead of 0n, and also don't check if the celebrity knows themselves since this implies nothing
def findCelebrity(self, n): x = 0 for i in xrange(n): if knows(x, i): x = i if any(knows(x, i) for i in xrange(n) if i != x): return 1 if any(not knows(i, x) for i in xrange(n) if i != x): return 1 return x

Python UnionFind, Detailed English Explanation
The key idea is to make each land position in an island point to a "root" land position in that island. Also maintain a mapping from roots to all land positions in the island
posToRoot = {} rootToPos = {}
When a new land position has no neighboring island, initialize a new island and set the new land position to its root
When a new land position has 1 neighboring island, make a new island with that position as the root
When a new land position has 2+ neighboring islands, combine the multiple islands with multiple roots to have just one root
from sets import Set class Solution(object): def numIslands2(self, m, n, positions): """ :type m: int :type n: int :type positions: List[List[int]] :rtype: List[int] """ def getNeighbors(i, j): # helper that gives list of indexes within m, n neighbors = [] if i>0: neighbors.append((i1, j)) if j>0: neighbors.append((i, j1)) if i+1<m: neighbors.append((i+1, j)) if j+1<n: neighbors.append((i, j+1)) return neighbors def getNeighborRoots(i, j): # helper that returns list of roots for unique islands neighboring position i, j return list(Set([posToRoot.get(x, None) for x in getNeighbors(i, j) if posToRoot.get(x, None)])) posToRoot = {} rootToPos = {} res = [] for i, j in positions: # for each new land position to add neighborRoots = getNeighborRoots(i, j) if not neighborRoots: # no connected islands, make new island rootToPos[(i, j)] = [(i, j)] posToRoot[(i, j)] = (i, j) else: # has 1 or more connected islands targetRoot = neighborRoots[0] posToRoot[(i, j)] = targetRoot rootToPos[targetRoot].append((i, j)) for i in range(1, len(neighborRoots)): # if has more than 1 connected islands, combine # extra islands into one single island myroot = neighborRoots[i] for pos in rootToPos[myroot]: posToRoot[pos] = targetRoot rootToPos[targetRoot].append(pos) del rootToPos[myroot] res.append(len(rootToPos)) return res

RE: 4lines O(n) C++
[... a, b, c, ...]
if a > b > c
then a > c
so a > c < b is validif a < b < c
then a < c
so a < c > b is valid 
Python O(n) Time, O(1) Space
Hash the number of times each character appears in p. Iterate over s with a sliding window and maintain a similar hash. If these two hashes are ever the same, add that to the result.
Each of the hashes have a finite (az, AZ) number of possible characters, so the space used is O(1)
We iterate over s linearly, comparing constant length hashes at each iteration so each iteration is also O(1), so the runtime is O(n)
class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ res = [] n, m = len(s), len(p) if n < m: return res phash, shash = [0]*123, [0]*123 for x in p: phash[ord(x)] += 1 for x in s[:m1]: shash[ord(x)] += 1 for i in range(m1, n): shash[ord(s[i])] += 1 if im >= 0: shash[ord(s[im])] = 1 if shash == phash: res.append(i  m + 1) return res

Python O(n) time O(1) space
O(1) space not including the input and output variables
The idea is we do a linear pass using the input array itself as a hash to store which numbers have been seen before. We do this by making elements at certain indexes negative. See the full explanation here
http://www.geeksforgeeks.org/findduplicatesinontimeandconstantextraspace/
class Solution(object): def findDuplicates(self, nums): """ :type nums: List[int] :rtype: List[int] """ res = [] for x in nums: if nums[abs(x)1] < 0: res.append(abs(x)) else: nums[abs(x)1] *= 1 return res

Python One Liner
It's absolutely hideous
class Solution(object): def reverseWords(self, s): """ :type s: str :rtype: str """ return "".join([(" " + x) for x in s.split(" ") if x != ""][::1])[1::]