Leetcode (Python) — Array summary Easy 4
724. Find Pivot Index
303. Range Sum Query — Immutable
448. Find All Numbers Disappeared in an Array
1189. Maximum Number of Balloons
496. Next Greater Element I
O(m*n)
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1Idx={n:i for i, n in enumerate(nums1)}
res=[-1] * len(nums1)
for i in range(len(nums2)):
if nums2[i] not in nums1Idx:
continue
for j in range(i+1, len(nums2)):
if nums2[j] > nums2[i]:
idx=nums1Idx[nums2[i]]
res[idx]=nums2[j]
break
return res
find an O(m+n) with stack
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1Idx={n:i for i, n in enumerate(nums1)}
res=[-1] * len(nums1)
stack=[]
for i in range(len(nums2)):
cur=nums2[i]
while stack and cur> stack[-1]:
val=stack.pop()
idx=nums1Idx[val]
res[idx]=cur
if cur in nums1Idx:
stack.append(cur)
return res
724. Find Pivot Index
class Solution(object):
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
new_nums=[0]+nums+[0]
total_sum=sum(new_nums)
cur_sum=0
for i in range(1,len(new_nums)-1):
cur_sum+=new_nums[i-1]
if cur_sum==(float(total_sum-new_nums[i])/2):
return i-1
return -1
class Solution(object):
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
total = sum(nums) # O(n)
leftSum = 0
for i in range(len(nums)):
rightSum = total - nums[i] - leftSum
if leftSum == rightSum:
return i
leftSum += nums[i]
return -1
303. Range Sum Query — Immutable
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.prefix=[]
cur=0
for n in nums:
cur+=n
self.prefix.append(cur)
def sumRange(self, left, right):
"""
:type left: int
:type right: int
:rtype: int
"""
rightSum=self.prefix[right]
leftSum=self.prefix[left-1] if left >0 else 0
return rightSum-leftSum
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)
448. Find All Numbers Disappeared in an Array
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
hash_map={}
for i in range(1,len(nums)+1):
hash_map[i]=1
for i in nums:
if i in hash_map:
hash_map[i]-=1
new_list=[]
for k,v in hash_map.items():
if v==1:
new_list.append(k)
return new_list
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for n in nums:
i = abs(n) - 1
nums[i] = -1 * abs(nums[i])
res = []
for i, n in enumerate(nums):
if n > 0:
res.append(i + 1)
return res
1189. Maximum Number of Balloons
Instead doing hashmap for the text, there is a time saving built in library called ‘Counter’ in python.
class Solution(object):
def maxNumberOfBalloons(self, text):
"""
:type text: str
:rtype: int
"""
countText=Counter(text)
balloon=Counter('balloon')
res=float('inf')
for c in balloon:
res=min(res, countText[c]//balloon[c])
return res