In [1]:
from typing import List
In [15]:
"""
For O(1) space complexity use math operation or XOR.
a^a = 0
a^0 = a
a^b^c = a^a^b = 0^b = b
"""
class Solution(object):
def singleNumber(self, nums: List[int]) -> int:
"""
:type nums: List[int]
:rtype: int
"""
idx = {}
for i in range(len(nums)):
if nums[i] not in idx:
idx[nums[i]] = 1
else:
idx[nums[i]] += 1
for k in idx.keys():
if idx[k] == 1:
return k
In [16]:
print(Solution().singleNumber([4,1,2,1,2]))
In [32]:
class Solution(object):
def ifHappy(self, n: int) -> bool:
"""
:type n: int
:rtype: bool
"""
l = 0
while (n != 1):
add = 0
for i in str(n):
add += int(i) ** 2
n = add
l += 1
if l > 100:
return False
return True
In [33]:
print(Solution().ifHappy(19))
In [36]:
class Solution(object):
def maxSubArray(self, nums: List[int]) -> int:
"""
:type nums: List[int]
:rtype int
"""
# Special case is when all values in num are negative.
if max(nums) < 0:
return max(nums)
max_sum = 0; curr = 0
for i in range(len(nums)):
if curr + nums[i] > 0:
curr = curr + nums[i]
else:
curr = 0 # Reset the sum.
if curr > max_sum:
max_sum = curr
return max_sum
In [37]:
print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
In [58]:
class Solution(object):
def moveZeroes(self, nums: List[int]) -> None:
"""
:type nums: List[int]
:rtype None
Perform inplace ordering.
Method: Apply a form of insert sort that moves each non-negative value
to its right place in the list.
"""
for i in range(len(nums)):
if nums[i] != 0:
j = i
while j > 0 and nums[j - 1] == 0:
nums[j], nums[j-1] = nums[j-1], nums[j]
j -= 1
In [60]:
nums = [0,1,0,3,12]
Solution().moveZeroes(nums)
print(nums)
In [71]:
class Solution(object):
def maxProfit(self, prices: List[int]) -> int:
"""
:type prices: List[int]
:rtype: int
Maximum Profit is the cumulation of all positive differences.
"""
profit = 0
for i in range(1, len(prices)):
diff = prices[i] - prices[i-1]
if diff > 0:
profit += diff
return profit
In [74]:
print(Solution().maxProfit([7,6,4,3,1]))
In [79]:
class Solution(object):
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
"""
:type strs: List[str]
:rtype: List[List[str]]
Method: Build a dictionary of words creating a bag of characters representation.
Generate a has for that representation and add words with a similar hash.
"""
words = {}
# Build a dictionary of words.
for word in strs:
boc_vec = [0 for i in range(26)]
for char in word:
boc_vec[ord(char) - 97] += 1
# Check if the representation if present in the dict.
hval = hash(tuple(boc_vec))
if hval not in words:
words[hval] = [word]
else:
words[hval].append(word)
# Once, the dictionary is built, generate list.
fin = []
for key in words.keys():
fin.append(words[key])
return fin
In [80]:
print(Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
In [82]:
class Solution(object):
def countElements(self, arr: List[int]) -> int:
"""
:type arr: List[int]
:rtype: int
Method: Build a dictionary of all numbers in the list and then separately
verify if (n+1) number exists in the dictionary for every n.
"""
nums = {}
for n in arr:
if n not in nums:
nums[n] = 1
cnt = 0
for n in arr:
if n+1 in nums:
cnt += 1
return cnt
In [85]:
print(Solution().countElements([1,3,2,3,5,0]))
In [ ]:
if root.left is None and root.right is None:
return 0
def get_longest_path(root):
if root.left is None and root.right is None:
return 0
elif root.left is None:
return 1 + get_longest_path(root.right)
elif root.right is None:
return 1 + get_longest_path(root.left)
else:
return max(1 + get_longest_path(root.left), 1 + get_longest_path(root.right))
return get_longest_path(root.left) + get_longest_path(root.right)