# brute force 
    #    - time: O(n^2)
    #    - space: O(1)
    def maxSubArray(self, nums: List[int]) -> int:
        n, res = len(nums), nums[0]
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur += nums[j]
                res = max(res, cur)
        return res
      
# greedy
# 也有一点像 sliding window，即 if cur_sum < 0, shrink the window to start from the current. Otherwise add to cur_sum
    #    - time: O(n)
    #    - space: O(1)
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        curSum = nums[0]
        for i in range(1, len(nums)):
            num = nums[i]
            # If cur_sum < 0, means the previous total sum doesn't help, and thus reset cur_sum to be current num.
            if curSum < 0:
                curSum = 0
            curSum += num
            res = max(res, curSum)
        return res

# brute force
#   - time: O(n^n)
...

# DP(top-down)
    #   - time: O(n^2)???
    #   - space: O(n)
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        dp = {}

        def dfs(i):
            if i >= len(nums) - 1:
                return True
            if i in dp:
                return dp[i]
            if nums[i] == 0:
                return False

            for step in range(1, nums[i] + 1):
                if dfs(i + step):
                    dp[i] = True
                    return True
            dp[i] = False
            return False

        return dfs(0)
      
# greedy - myself
    #   - time: O(n)
    #   - space: O(1)
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
    
        goal = len(nums) - 1
        i = len(nums) - 1
        while i >= 0:
            if i + nums[i] >= goal:
                # 如果当前位置可以跳到 goal，则设当前位置（一个更近的位置）为 goal
                goal = i
                i -= 1
            else:
                i -= 1
        return goal == 0  # goal == 0意味着从起点是一个 goal，因而起点能 reach goal
      
# greedy - leetcode
    #   - time: O(n)
    #   - space: O(1)
	def canJump(self, nums: List[int]) -> bool:
		goal = len(nums) - 1
		for i in range(len(nums) - 1, -1, -1):
			if i + nums[i] >= goal:
				goal = i

		return goal == 0
  

	def jump(self, nums: List[int]) -> int:
		l, r = 0, 0
		count = 0
		while r < len(nums) - 1:  # before r reaches the last index, continue
			farthest = 0
			for i in range(l, r + 1):
				farthest = max(farthest, i + nums[i])
			l = r + 1  # because it is guaranteed that I can rach the last index
			r = farthest
			count += 1
		return count
  
# DP(top-down)
    #  - time: O(n^2)
    #  - space: O(n)
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = {}

        def dfs(i):
            if i >= len(nums) - 1:
                return 0
            if i in dp:
                return dp[i]
            if nums[i] == 0:
                return 100000

            minStep = 100000
            for step in range(1, nums[i] + 1):
                minStep = min(minStep, dfs(i + step) + 1)
            dp[i] = minStep
            return minStep

        return dfs(0)  

# brute force
#   - time: O(n^2)
#   - space: O(1)

# greedy
    #  - time: O(n)
    #  - space: O(1)
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        if sum(gas) < sum(cost):
            # If this case, we are not able to finish the route in any ways, because the total gas is not enough
            return -1

        # If comes to here, we guarantee that we are able to finish the circular route, because sum(cost) >= sum(gas)
        left = 0
        start = 0
        for idx in range(len(gas)):
            left += gas[idx] - cost[idx]
            if left < 0:
                # 如果剩的 < 0，把下一个节点视为起始节点
                start = idx + 1
                left = 0
        # Because every time we pass every gas station and left >= 0, and sum(cost) <= sum(gas), so the gas needed for the gas stations that we haven't gone through will be < than the gas left.
        return start

	def checkValidString(self, s: str) -> bool:
		# ( * ) * ( )
		minLeft = 0
		maxLeft = 0
		# space: O(1)
		# time: O(n)
		for char in s:
			if char == "(":
				minLeft += 1
				maxLeft += 1
			elif char == ")":
				minLeft -= 1
				maxLeft -= 1
			else:
				minLeft -= 1
				maxLeft += 1

			if maxLeft < 0:  # e.g., ))((
				return False
			if minLeft < 0:  # we need this if because of s = ( * ) ( case
				minLeft = 0
		return minLeft == 0

    # greedy + hashmap
    #   - time: O(n)
    #   - space: O(1) # O(26)
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        lastIdxMap = {}  # char -> lastIndexOfThisChat map. Space: O(1)
        for i, char in enumerate(s):
            lastIdxMap[char] = i

        res =[]
        curPartitionMaxEndIdx,size = 0,0
        for idx, char in enumerate(s):
            curPartitionMaxEndIdx = max(lastIdxMap[char], curPartitionMaxEndIdx)
            size += 1
            if idx == curPartitionMaxEndIdx :
                # 扫描到当前 partition 的最右端索引时，把当前 partition 的长度加到 res，并重置 size
                res.append(size)
                size, curPartitionMaxEndIdx = 0, 0  # 更新 maxEndIdx 不是必须的
        return res

# greedy + hashmap + heap - myself
    #  - time: O(n * logn)
    #  - space: O(n)
    def isNStraightHand(self, hand, groupSize):
        """
        :type hand: List[int]
        :type groupSize: int
        :rtype: bool
        """
        if len(hand) % groupSize != 0:
            return False

        m = {}  # space: O(n)
        for n in hand:
            m[n] = m.get(n, 0) + 1
        minHeap = []  # space: O(n), 用 minHeap 可以以每次 O(1) 取出最小值
        for n in m.keys():
            minHeap.append(n)  # 不需要保存 count
        heapq.heapify(minHeap)
        # print(m)

        while minHeap:  # time: O(n * logn)
            smallest = minHeap[0]  # 取出当前最小的元素
            # 依次检查其对应的 group
            for n in range(smallest, smallest + groupSize):
                if n not in m:
                    return False
                m[n] -= 1
                if m[n] == 0:
                    del m[n]  # Not necessary to have this line
                    heapq.heappop(minHeap)
        return True
      
# greedy + hashmap + heap - leetcode
    #  - time: O(n * logn)
    #  - space: O(n)      
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
		if len(hand) % groupSize != 0:
			return False

		m = {}
		for ele in hand:
			m[ele] = m.get(ele, 0) + 1

		minHeap = list(m.keys())
		heapq.heapify(minHeap)

		while minHeap:
			cur_min = minHeap[0]
			for i in range(cur_min, cur_min + groupSize):
				if i not in m:
					return False
				m[i] -= 1
				if m[i] == 0:
					if i != minHeap[0]: 
            # 如果当前扫描的值不是 heap 中的最小值，直接可以 return False
						return False
					heapq.heappop(minHeap)
		return True

# greedy
    #   - time: O(n)
    #   - space: O(1)
    def mergeTriplets(self, triplets, target):
        """
        :type triplets: List[List[int]]
        :type target: List[int]
        :rtype: bool
        """
        hasTargetX, hasTargetY, hasTargetZ = False, False, False
        for triplet in triplets:
            if triplet[0] > target[0] or triplet[1] > target[1] or triplet[2] > target[2]:
                # Not consider such a triplet, since any of elements of this triplet is > than the corrsponding element in the target array,
                # we shouldn't consider this triplet, otherwise, we cannot form target if we use this triplet, e.g., triplet: [2,8,3] target: [2,7,3] -> the final triplet will be [*,8,*]
                continue

            if triplet[0] == target[0]:
                hasTargetX = True
            if triplet[1] == target[1]:
                hasTargetY = True
            if triplet[2] == target[2]:
                hasTargetZ = True
        return hasTargetX and hasTargetY and hasTargetZ