MediumNo. 2513
Minimize the Maximum of Two Arrays — LeetCode 2513 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Math, Binary Search, Number Theory
- Reading time
- 3 min
- Source
- leetcode.com
The problem
We have two arrays arr1 and arr2 which are initially empty. You need to add positive integers to them such that they satisfy all the following conditions: arr1 contains uniqueCnt1 distinct positive integers, each of which is not divisible by divisor1.
Example
- Input
- divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
- Output
- 4
- Explanation
- We can distribute the first 4 natural numbers into arr1 and arr2.
Python solution
class Solution:
def minimizeSet(
self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int
) -> int:
def f(x):
cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1
cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2
cnt = x // divisor * (divisor - 1) + x % divisor
return (
cnt1 >= uniqueCnt1
and cnt2 >= uniqueCnt2
and cnt >= uniqueCnt1 + uniqueCnt2
)
divisor = lcm(divisor1, divisor2)
return bisect_left(range(10**10), True, key=f)Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 2513. Minimize the Maximum of Two Arrays is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1201 | Ugly Number III | Medium |
| 2601 | Prime Subtraction Operation | Medium |
| 0069 | Sqrt(x) | Easy |
| 0367 | Valid Perfect Square | Easy |
| 0400 | Nth Digit | Medium |
| 0441 | Arranging Coins | Easy |
Frequently asked questions
- How hard is LeetCode 2513. Minimize the Maximum of Two Arrays?
LeetCode 2513. Minimize the Maximum of Two Arrays is rated Medium on LeetCode.
- What topics does LeetCode 2513. Minimize the Maximum of Two Arrays cover?
LeetCode 2513. Minimize the Maximum of Two Arrays is tagged Math, Binary Search and Number Theory on LeetCode.