Leetcode week #10: Greedy

Sep 2, 2024 | monday 7:00 pm

This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.

1. 🟡 Gas Station
2. 🟡 Maximum Subarray
3. 🟡 Jump Game
4. 🟡 Jump Game II
5. 🟡
6. 🟡
7. 🟡
8. 🟡 Valid Parenthesis String

Medium

Try it yourself here!

Problem Statement: Visualizing the array has a circle, find the index i such that starting with gas[i], it’s possible to travel to each station in order, using cost[i] for the fuel needed to travel from station i to i+1. The goal is to determine if there’s a valid starting station that allows for a complete circular journey, or return -1 if it’s not possible.

Edge Cases:

1. It is not possible to start at any gas station and travel to every other station.

Example:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output: 3

Explanation: Starting at gas[3], it is possible to travel to all the gas stations without running out of gas.

Solution:

Key Steps:

1. Keep track of two states:
   1. Global State: This keeps track of the overall fuel balance. If the total amount of gas is less than the total cost, completing the circuit is impossible.
   2. Local State: This tracks the fuel balance for the current trip segment. If the local balance becomes negative, it means the current starting point can’t complete the journey, so reset the starting index to the next station.
2. Loop through the gas and cost arrays, calculating the difference gas[i] - cost[i] at each station. Add this difference to both the local and global state.
3. If the local balance (local state) ever becomes negative, it means the current start is invalid. Set the starting index to the next station and reset the local state. This ensures an amortized O(n) solution, as we don’t need to backtrack.
4. After the loop, if the global state (total gas balance) is negative, it’s impossible to complete the circuit, and the function should return -1.

Solution:

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    currGas = 0
    currIndex = 0
    totalGas = 0

    for i in range(len(gas)):
        currGas += gas[i] - cost[i]
        totalGas += gas[i] - cost[i]
        if currGas < 0:
            currGas = 0
            currIndex = i + 1
    return -1 if totalGas < 0 else currIndex

Complexity:

• Time: O(n): One iteration through both arrays is required.

• Space: O(1): Constant space is used to keep track of the cost and index.

Maximum Subarray

MediumMaximum Subarray

Try it yourself here!

Solution:

def maxSubArray(self, nums: List[int]) -> int:
    curr = 0
    res = -inf
    for n in nums:
        if curr < 0:
            curr = 0
        curr += n
        res = max(curr, res)
    return res

Complexity:

• Time: O(n): Nums is traversed once.

• Space: O(n): Constant space used.

Jump Game

MediumJump Game

Try it yourself here!

Solution:

 def canJump(self, nums: List[int]) -> bool:
        lastIndex = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if (i + nums[i] >= lastIndex):
                lastIndex = i
        return lastIndex == 0

Complexity:

• Time: O(n): Nums is traversed once.

• Space: O(1): Constant space used.

Jump Game II

Medium

Try it yourself here!

Solution:

def jump(self, nums: List[int]) -> int:
    dp = [inf] * len(nums)
    dp[-1] = 0

    for i in range(len(nums) -2, -1, -1):
        jump = min(i + nums[i], len(nums) - 1)
        for j in range(i + 1, jump + 1):
            if dp[j] != inf:
                dp[i] = min(dp[j] + 1, dp[i])
    return dp[0]

Complexity:

• Time: O(n^2): Nums is traversed twice.

• Space: O(1): Constant space used.

Medium

Try it yourself here!

Solution:

Complexity:

• Time:

• Space:

Valid Parenthesis String

MediumValid Parenthesis String

Try it yourself here!

Solution:

def checkValidString(self, s: str) -> bool:
    leftMin, leftMax = 0, 0
    for c in s:
        if c == "*":
            leftMin = max(0, leftMin - 1)
            leftMax += 1
        elif c == "(":
            leftMin += 1
            leftMax += 1
        else:
            leftMin = max(0, leftMin - 1)
            leftMax -= 1
        if leftMax < 0:
            return False
    return leftMin <= 0 <= leftMax

Complexity:

• Time: O(n), where n is the length of s.

• Space: O(1), constant space is used.

Medium

Try it yourself here!

Solution:

Complexity:

• Time:

• Space: