Leetcode (Python) — Array summary Easy 4

496. Next Greater Element I

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