Skip to content

Partitioning Greedy

Table of Contents

1221. Split a String in Balanced Strings

2405. Optimal Partition of String

2294. Partition Array Such That Maximum Difference Is K

from typing import List


def partitionArray(nums: List[int], k: int) -> int:
    nums.sort()
    mn = float("-inf")
    res = 0

    for num in nums:
        if num - mn > k:
            res += 1
            mn = num

    return res


if __name__ == "__main__":
    assert partitionArray([3, 6, 1, 2, 5], 2) == 2

2358. Maximum Number of Groups Entering a Competition

2522. Partition String Into Substrings With Values at Most K

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

2436. Minimum Split Into Subarrays With GCD Greater Than One

2892. Minimizing Array After Replacing Pairs With Their Product

Comments