@facss what do you mean?
agave
@agave
Posts made by agave

10 lines in Python
class Solution(object): def canCross(self, stones): memo, stones, last = {}, set(stones), stones[1] def helper(pos, jump): if pos == last: return True if jump <= 0 or pos not in stones: return False if (pos, jump) in memo: return memo[pos, jump] for nex in {jump, jump  1, jump + 1}: if helper(pos + nex, nex): return True memo[pos, jump] = False return False return helper(1, 1) # 39 / 39 test cases passed. # Status: Accepted # Runtime: 166 ms
Let's talk about complexity. Right off the bat, we can get an easy bigO estimation by considering that we do 3 subrecursive call at each recursive call, leading to an
O(3^n)
complexity. However, we can achieve a better time complexity estimation by observing that for each positionpos
, there are maximumpos1
possible jumps that can lead to positionpos
. Therefore, we have a recursive tree with at most1 + 2 + ... + n
nodes, leading to a complexity ofO(n^2)
. Space is alsoO(n^2)
since we need to store inmemo
the results of the negative calls.Even shorter BFS (iterative):
class Solution(object): def canCross(self, stones): visits, stones, last, queue = {(1, 1)}, set(stones), stones[1], [(1, 1)] for pos, jump in queue: if pos == last: return True if jump <= 0 or pos not in stones: continue for nex in {jump, jump  1, jump + 1}: if (pos + nex, nex) not in visits: visits.add((pos + nex, nex)) queue.append((pos + nex, nex)) return False

RE: 12line Python O(N) guaranteed
@jedihy said in 12line Python O(N) guaranteed:
Just copy the code from another problem Maximum size subarray sum which is solved by an O(N) algorithm.
class Solution(object): def pathSum(self, root, target): """ :type root: TreeNode :type target: int :rtype: int """ self.count = 0 preDict = {0: 1} def dfs(p, target, pathSum, preDict): if p: pathSum += p.val self.count += preDict.get(pathSum  target, 0)
You could have used
collections.Counter()
and then justself.count += preDict[pathSum  target]
preDict[pathSum] = preDict.get(pathSum, 0) + 1
Ditto
dfs(p.left, target, pathSum, preDict) dfs(p.right, target, pathSum, preDict) preDict[pathSum] = 1 dfs(root, target, 0, preDict) return self.count

Nice'n'Clean recursive Python code
class Solution(object): def pathSum(self, root, target): def findSum(root, totSum): if not root: return totSum += root.val res[0] += partSums[totSum  target] partSums[totSum] += 1 findSum(root.left, totSum) findSum(root.right, totSum) partSums[totSum] = 1 res = [0] partSums = collections.Counter([0]) findSum(root, 0) return res[0] # 126 / 126 test cases passed. # Status: Accepted # Runtime: 105 ms
Time complexity is O(n) since I go through every node of the tree once. This is the best we can do (optimum runtime). Space complexity is O(n) given the additional
Counter
variable. 
RE: 1liner Python
Doesn't work in Python 3.x. One must use
itertools.zip_longest
to transpose, as done by @waigx. 
2 lines in Python
class Solution(object): def validWordSquare(self, words): other = list(itertools.izip_longest(*words)) return not any(i >= len(other) or j >= len(other[i]) or other[i][j] != char for i, word in enumerate(words) for j, char in enumerate(word))

RE: Single line Python Solution using reduce
@vnext999 Actually this is cheating because you're implicitly using the BigInt library of Python. You code is equivalent of writing
return int(num1) + int(num2)
. Converting to integer by usingreduce
doesn't make it any less cheating :) 
Very easy to understand Python solution
class Solution(object): def addStrings(self, num1, num2): def additionStrings(num1, num2, carry): if not num1 and not num2: if carry: res.append(carry) return a, b = num1.pop() if num1 else 0, num2.pop() if num2 else 0 carry, digit = divmod(a + b + carry, 10) res.append(digit) additionStrings(num1, num2, carry) res = [] additionStrings([int(c) for c in num1], [int(c) for c in num2], 0) return "".join([str(num) for num in res[::1]])

Intuitive and Short Python solution
class Solution(object): def thirdMax(self, nums): v = [float('inf'), float('inf'), float('inf')] for num in nums: if num not in v: if num > v[0]: v = [num, v[0], v[1]] elif num > v[1]: v = [v[0], num, v[1]] elif num > v[2]: v = [v[0], v[1], num] return max(nums) if float('inf') in v else v[2]
Time complexity is O(n), space complexity is O(1).

RE: Python Golf
@StefanPochmann haha great, was able to do just this
class Solution(object): def fizzBuzz(self, n): return [str(i) * (i % 3 != 0 and i % 5 != 0) + "Fizz" * (i % 3 == 0) + "Buzz" * (i % 5 == 0) for i in range(1, n + 1)]