Skip to content

Greedy Others

Table of Contents

2740. Find the Value of the Partition

1033. Moving Stones Until Consecutive

1864. Minimum Number of Swaps to Make the Binary String Alternating

1899. Merge Triplets to Form Target Triplet

1899. Merge Triplets to Form Target Triplet - Python Solution
from typing import List


def mergeTriplets(triplets: List[List[int]], target: List[int]) -> bool:
    can_form = [False, False, False]

    for triplet in triplets:
        if all(triplet[i] <= target[i] for i in range(3)):
            for i in range(3):
                if triplet[i] == target[i]:
                    can_form[i] = True

    return all(can_form)


triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]]
target = [2, 7, 5]
print(mergeTriplets(triplets, target))  # True

2498. Frog Jump II

134. Gas Station

134. Gas Station - Python Solution
from typing import List


# Greedy
def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
    curSum = 0
    totalSum = 0
    start = 0

    for i in range(len(gas)):
        curSum += gas[i] - cost[i]
        totalSum += gas[i] - cost[i]

        if curSum < 0:
            start = i + 1
            curSum = 0

    if totalSum < 0:
        return -1

    return start


gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost))  # 3

2311. Longest Binary Subsequence Less Than or Equal to K

3443. Maximum Manhattan Distance After K Changes

3002. Maximum Size of a Set After Removals

2412. Minimum Money Required Before Transactions

659. Split Array into Consecutive Subsequences

2732. Find a Good Subset of the Matrix

2790. Maximum Number of Groups With Increasing Length

782. Transform to Chessboard

420. Strong Password Checker

2753. Count Houses in a Circular Street II

Comments