---
# System prepended metadata

title: Greedy (8)
tags: [working]

---

# Greedy (8)

> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
> 
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)

<!-- 常用色碼紀錄
Easy:   <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard:   <font color="#ee2f56">**Hard**</font>
-->

Greedy 的題目重點在於透過適合的 greedy rule 將問題分解，找到每個 subproblem 的局部最佳解後，再從每一次的局部最佳解構成最後的解集合。

## 1. Maximum Subarray
<font color="#ffbb00">**Medium**</font>

> Given an array of integers `nums`, find the subarray with the largest sum and return the sum.
>
> A **subarray** is a contiguous non-empty sequence of elements within an array.

### Example 1:
```java
Input: nums = [2,-3,4,-2,2,1,-1,4]

Output: 8
```

Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8.

### Example 2:
```java
Input: nums = [-1]

Output: -1
```

### Constraints

* `1 <= nums.length <= 1000`
* `-1000 <= nums[i] <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(1)$

### Solution

**Greedy rule:** 對於 index = i 的元素，分析要不要將他加入至目前的 subArray 之中使它對目前的最大和(local optimal)有貢獻。

迭代輸入陣列 nums 並維護一個當前最大和 surrSum 以及全局最大和 maxSum，每個元素考慮以下狀況:

* 加上 nums[i] 後總和 >= nums[i]
    * 表示 nums[i] 對 currSum 有貢獻
    * 可加入 subarray 之中
* 加上 nums[i] 後總和 < nums[i]
    * 表示不需要前面的 subarray，因為前面的元素會拖垮後面的表現
    * 更新 currSum 與 maxSum
    * 並從 nums[i] 開始做為第一個元素，往後找新的 subarray

```python=
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        currSum = 0

        for n in nums:
            if currSum + n < n:
                currSum = 0
            currSum += n
            maxSum = max(currSum, maxSum)
        return maxSum
```

## 2. Jump Game
<font color="#ffbb00">**Medium**</font>

> You are given an integer array `nums` where each element `nums[i]` indicates your maximum jump length at that position.
> 
> Return `true` if you can reach the last index starting from index `0`, or `false` otherwise.

### Example 1:
```java
Input: nums = [1,2,0,1,0]

Output: true
```
Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.

### Example 2:
```java
Input: nums = [1,2,1,0,1]

Output: false
```

### Constraints

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(1)$

### Solution

**Greedy rule:** 找到每個能抵達局部終點的局部最佳解

(1) 能不能抵達終點最快的看法是從終點往回逆推，如果回推的某個點能夠抵達目前的終點，表示此點是一個局部最佳解

(2) 此時將終點更新為這個局部最佳解的點，並繼續逆推找下一個最佳解

(3) 直到找到起點為止，表示能夠從起點透過上述的每個局部最佳解走到終點

```python=
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dst = n - 1

        for i in range(n - 2, -1, -1):
            if nums[i] + i >=  dst:
                dst = i
        
        return True if dst == 0 else False
```

## 3. Jump Game ll
<font color="#ffbb00">**Medium**</font>

> You are given an array of integers `nums`, where `nums[i]` represents the maximum length of a jump towards the right from index `i`. For example, if you are at `nums[i]`, you can jump to any index `i + j` where:
>
> * `j <= nums[i]`
> * `i + j < nums.length`
>
> You are initially positioned at `nums[0]`.
>
> Return the minimum number of jumps to reach the last position in the array (index `nums.length - 1`). You may assume there is always a valid answer.

### Example 1:
```java
Input: nums = [2,4,1,1,1,1]

Output: 2
```
Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.

### Example 2:
```java
Input: nums = [2,1,2,1,0]

Output: 2
```

### Constraints

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 100`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(1)$

### Solution

**Greedy rule:** 每次尋找能夠走最遠距離的點作為局部最佳解

* 維護兩個指標 `leftPtr` 與 `rightPtr`，這兩個指標間的點表示目前可以抵達的點
    * 初始化，兩個指標都從 index = 0 的起點開始
    * 透過迭代可以抵達的點尋找最遠距離
* 迭代完並找到最遠距離後，更新下一段的指標
    * leftPtr = rightPtr + 1
    * rightPtr = 距離最遠的點
* 當右指標(最遠點)超過終點位置，表示抵達最後終點

每次在找最遠距離時，每更新一次指標就表示選擇一個點前進 $\Rightarrow$ 步數 + 1

```python=
class Solution:
    def jump(self, nums: List[int]) -> int:
        leftPtr, rightPtr = 0, 0
        res = 0

        while rightPtr < len(nums) - 1:
            # go through the reachable index
            farIdx = rightPtr
            for i in range(leftPtr, rightPtr + 1):
                farIdx = max(farIdx, i + nums[i])
            
            # update left and right pointer
            leftPtr = rightPtr + 1
            rightPtr = farIdx
            res += 1
        
        return res
```

## 4. Gas Station
<font color="#ffbb00">**Medium**</font>

> There are `n` gas stations along a circular route. You are given two integer arrays `gas` and `cost` where:
>
> `gas[i]` is the amount of gas at the `ith` station.
> `cost[i]` is the amount of gas needed to travel from the `ith` station to the `(i + 1)th` station. (The last station is connected to the first station)
> 
> You have a car that can store an unlimited amount of gas, but you begin the journey with an empty tank at one of the gas stations.
>
> Return the starting gas station's index such that you can travel around the circuit once in the clockwise direction. If it's impossible, then return `-1`.
>
> It's guaranteed that at most one solution exists.

### Example 1:
```java
Input: gas = [1,2,3,4], cost = [2,2,4,1]

Output: 3
```
Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 1 + 1 = 3
Travel to station 1. Your tank = 3 - 2 + 2 = 3
Travel to station 2. Your tank = 3 - 2 + 3 = 4
Travel to station 3. Your tank = 2 - 4 + 4 = 2

### Example 2:
```java
Input: gas = [1,2,3], cost = [2,3,2]

Output: -1
```
Explanation:
You can't start at station 0 or 1, since there isn't enough gas to travel to the next station.
If you start at station 2, you can move to station 0, and then station 1.
At station 1 your tank = 0 + 3 - 2 + 1 - 2 = 0.
You're stuck at station 1, so you can't travel around the circuit.

### Constraints

* `1 <= gas.length == cost.length <= 1000`
* `0 <= gas[i], cost[i] <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
    * n is the size of input array
* Space complexity: $O(1)$

### Solution

**Greedy rule:** 選定起點後開始走，如果在某個中間站點的油量 < 0 表示該點不能做為起點

當發現某個點不能做為起點，意味著從這個起點開始到油量 < 0 的點，瓦斯補給(`gas`)的總和 < 消耗成本(`cost`)的總和，因此中間路途的點都不能作為起點。Step-by-step 如下: 

* 設總油量 `total = 0`，起點為 index = 0
* 以單一站點來看，離開每個站點後所剩的油量為 `remains = gas[i] - cost[i]`(先補給再消耗)
* 若 `total + remains < 0` 表示油量不夠
    * 以下一個點 index = `i + 1` 作為新的起點
    * 更新總油量 `total = 0`

```python=
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        
        totalGas = 0
        n = len(gas)
        startIdx = 0
        for i in range(n):
            remains = gas[i] - cost[i]
            totalGas += remains
            if totalGas < 0:
                totalGas = 0
                startIdx = i + 1
            
        
        return startIdx
```

## 5. Hamd of Straights
<font color="#ffbb00">**Medium**</font>

> You are given an integer array `hand` where `hand[i]` is the value written on the `ith` card and an integer `groupSize`.
>
> You want to rearrange the cards into groups so that each group is of size `groupSize`, and card values are consecutively increasing by `1`.
>
> Return `true` if it's possible to rearrange the cards in this way, otherwise, return `false`.

### Example 1:
```java
Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4

Output: true
```
Explanation: The cards can be rearranged as `[1,2,3,4]` and `[2,3,4,5]`.

### Example 2:
```java
Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4

Output: false
```
Explanation: The closest we can get is `[1,2,3,4]` and `[3,5,6,7]`, but the cards in the second group are not consecutive.

### Constraints:

* `1 <= hand.length <= 1000`
* `0 <= hand[i] <= 1000`
* `1 <= groupSize <= hand.length`

### Recommended complexity

* Time complexity: $O(n \cdot \log n)$
* Spce complexity: $O(n)$

### Solution

**Greedy rule:** 每次從最小的數字開始形成一個 group (局部最佳解)

* 每個數字可能提供給多個 group 使用，所以要先計算/紀錄每個數字出現的頻率
* 將給定的 array 排序，從最小的數字開始建立 group
    * 選定最小的數字(假設為 n)後，因為 group 內的數字是每次遞增 1，所以直接把 n, n+1, n+2, n+3 這四個數字的頻率 - 1 表示用這四個數字形成一個 group
    * 如果某數字不存在或頻率不夠(=0)，表示不能建立這組 group

> [!Tip]
> * 選定最小數字作為每個 group 的起點，後面 groupSize - 1 個數字直接以迭代遞增的方式找出來然後把頻率/次數 - 1 即可，不用真的創建 group 放入數字
> * 完成一個 group 後(local optimal)再完成下一個 group，這樣的目的是符合 greedy 的概念

```python=
class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False

        count = {}
        for i in hand:
            count[i] = 1 + count.get(i, 0)
        
        hand.sort()
        for i in hand:
            if count[i] != 0:
                for j in range(i, i + groupSize):
                    if (j in count) and (count[j] > 0):
                        count[j] -= 1
                    else:
                        return False
                    
        return True
```

## 6. Merge Triplets to Form Target
<font color="#ffbb00">**Medium**</font>

> You are given a 2D array of integers `triplets`, where `triplets[i] = [ai, bi, ci]` represents the `ith` triplet. You are also given an array of integers `target = [x, y, z]` which is the triplet we want to obtain.
>
> To obtain `target`, you may apply the following operation on `triplets` zero or more times:
> 
> Choose two different triplets `triplets[i]` and `triplets[j]` and update `triplets[j]` to become `[max(ai, aj), max(bi, bj), max(ci, cj)]`.
> 
> * E.g. if `triplets[i] = [1, 3, 1]` and `triplets[j] = [2, 1, 2]`, `triplets[j]` will be updated to `[max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2]`.
>
> Return `true` if it is possible to obtain `target` as an **element of** `triplets`, or `false` otherwise.

### Example 1:
```java
Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]

Output: true
```
Explanation:
Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3].

### Example 2:
```java
Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6]

Output: false
```

### Constraints:

* `1 <= triplets.length <= 1000`
* `1 <= triplets.length <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
    * n is the size of the input array
* Space complexity: $O(1)$

### Solution

**Greedy rule:** 刪除不合理的組別，每次挑選可以符合 target[i] 的位置(local optimal)

(1) 刪除不合理
只要某個組別(`tri`)中的三個數字有一個(`tri[i]`)大於對應的 target 值(`target[i]`)，表示該組不可能對 target 有貢獻。

(2) 挑選剩餘組別
剩餘組別的值必定 <= 對應的 target 值，只有剩餘組別中有一個數字 = 對應的 target 值，則該組必定可以透過交換保留它並湊出最後的 target。

```python=
class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        candidate = set()

        for tri in triplets:
            if tri[0] > target[0] or tri[1] > target[1] or tri[2] > target[2]:
                continue
            
            for idx, value in enumerate(tri):
                if value == target[idx]:
                    candidate.add(idx)
        
        return len(candidate) == 3
```

## 7. Partition Labels
<font color="#ffbb00">**Medium**</font>

> You are given a string `s` consisting of lowercase english letters.
> 
> We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.
>
> Return a list of integers representing the size of these substrings in the order they appear in the string.

### Example 1:
```java
Input: s = "xyxxyzbzbbisl"

Output: [5, 5, 1, 1, 1]
```
Explanation: The string can be split into `["xyxxy", "zbzbb", "i", "s", "l"]`.

### Example 2:
```java
Input: s = "abcabc"

Output: [6]
```

### Constraints

* `1 <= s.length <= 100`

### Recommended complexity

* Time complexity: $O(n)$
    * n is the length og the string `s`
* Space complexity: $O(m)$
    * m is the number of unique characters in the string `s`

### Solution

(1) 原本的想法

**Greedy rule:** 每次完成一個字母做為局部最佳解

* 根據題意所說，每個字母只能出現在最多一個 substring 中，所以需要計算每個字母剩餘的出現次數/頻率
* 以 two pointer 做搜索，左指標指向目前正在處理的字元，右指標歷遍 substring 字串
    * 右指標歷遍字串的過程中，每碰到一個字元就將它的出現次數 - 1，直到左指標指向的字元的頻率 = 0 時表示該字元處理完
    * 左指標 + 1 處理下一個字元
* 直到左指標 = 右指標，表示找到 substring 的分界點，再計算 sustring 的長度

```python=
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        count = {}
        for ch in s:
            count[ch] = 1 + count.get(ch, 0)
        
        LP, RP = 0, 0
        start = 0
        res = []
        
        while LP < len(s):
            ch = s[LP]

            while count[ch] != 0:
                count[s[RP]] -= 1
                RP += 1
            
            LP += 1
            
            if LP == RP:
                res.append(RP - start)
                start = RP
        return res
```

(2) Improvement

**Greedy rule:** 每次完成一個字母做為局部最佳解

* 要完成一個字母最快的方式就是直接找到它出現的最後位置，就是該字母需要對應的 substring 長度
* 從頭開始歷遍字串 `s`
    * 尋找每個字母最後出現的位置並取最大值
    * 當最大位置 = 目前正在處理的位置，表示找到 substring 的分界點
    * 再計算 substring 長度

```python=
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        lastIndex = {}
        for idx, ch in enumerate(s):
            lastIndex[ch] = idx
        
        res = []
        size = 0
        end = 0
        for idx, ch in enumerate(s):
            size += 1
            end = max(end, lastIndex[ch])

            if idx == end:
                res.append(size)
                size = 0
        return res
```

## 8. Valid Parenthesis String
<font color="#ffbb00">**Medium**</font>

> You are given a string `s` which contains only three types of characters: `'('`, `')'` and `'*'`.
>
> Return `true` if `s` is **valid**, otherwise return `false`.
>
> A string is valid if it follows all of the following rules:
>
> * Every left parenthesis `'('` must have a corresponding right parenthesis `')'`.
> * Every right parenthesis `')'` must have a corresponding left parenthesis `'('`.
> * Left parenthesis `'('` must go before the corresponding right parenthesis `')'`.
> * A `'*'` could be treated as a right parenthesis `')'` character or a left parenthesis `'('` character, or as an empty string `""`.

### Example 1:
```java
Input: s = "((**)"

Output: true
```
Explanation: One of the `'*'` could be a `')'` and the other could be an empty string.

### Example 2:
```java
Input: s = "(((*)"

Output: false
```
Explanation: The string is not valid because there is an extra `'('` at the beginning, regardless of the extra `'*'`.

### Constraints

* `1 <= s.length <= 100`

### Recommended complexity

* Time complexity: as good or better than $O(n)$
* Space complexity: as good or better than $O(n)$

### Soluton

**Greedy rule**: 維護一個可能的左括的出現次數的範圍

每一個 ( 都需要一個 ) 配對才能組成一組括號，因此當發現一個 ( 時左括號的出現次數 + 1，反之出現 ) 時左括號出現次數 - 1。又因為 `*` 符號可以作為 ( 與 ) 使用，所以遇到 `*` 時可以同時 + 1 或 - 1。因此最後計算出的結果 ( 出現次數應該是一個範圍，具有最大值 leftMax(未匹配的 `(` 的最大數量) 與最小值 leftMin(未匹配的 `(` 的最小數量)。

只有 leftMin = 0 的狀況才是合理的，因為每組括號都可以正確閉合。

* 當 leftMax < 0 表示 ) 太多，無法形成合理的括號對
* 當 leftMin < 0 表示出現了多餘的 )，無法形成合理的括號對

```python=
class Solution:
    def checkValidString(self, s: str) -> bool:
        leftMin, leftMax = 0, 0

        for ch in s:
            if ch == ')':
                leftMin, leftMax = leftMin - 1, leftMax - 1
            elif ch == '(':
                leftMin, leftMax = leftMin + 1, leftMax + 1
            else: #  when * appear
                leftMin, leftMax = leftMin - 1, leftMax + 1
            
            if leftMax < 0:
                return False
            
            if leftMin < 0:
                leftMin = 0
        
        return leftMin == 0
```
