Minimize the Maximum of Two Arrays solution and explanation
9 more videos on this problem
Leetcode Biweekly Contest 94 | 2513 : Minimize the Maximum of Two Arrays Solution | Newton SchoolCoding Community | Newton School · 23:32 · 5K views
Minimize the Maximum of Two Arrays | 2513 LeetCode | Binary Search | Leetcode Biweekly Contest 94CodeWithSunny · 20:25 · 4K views
Biweekly Contest 94 | Minimize the Maximum of Two ArrayscodingMohan · 29:58 · 2K views
LeetCode 2513. Minimize the Maximum of Two Arrays | Simple Explanation with CodeDeep Tech · 16:24 · 1K views
Leetcode BiWeekly contest 94 - Medium - Minimize the Maximum of Two ArraysPrakhar Agrawal · 13:10 · 1K views
2513. Minimize the Maximum of Two Arrays (Leetcode Medium)Programming Live with Larry · 36:30 · 1K views
LeetCode 2513 Explained | Minimize the Maximum of Two Arrays (Interview Approach)Code Crusaders · 3:22 · 1K views
【每日一题】LeetCode 2513. Minimize the Maximum of Two ArraysHuifeng Guan · 21:36 · 607 views
Leetcode | biweekly-contest-94| 2513 Minimize the Maximum of Two ArraysCyCode · 16:49 · 180 views
Leetcode Biweekly Contest 94 | problem C | 2513. Minimize the Maximum of Two Arrays | 24/12/22CodingVerse · 8:46 · 139 views
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:
arr1containsuniqueCnt1distinct positive integers, each of which is not divisible bydivisor1.arr2containsuniqueCnt2distinct positive integers, each of which is not divisible bydivisor2.- No integer is present in both
arr1andarr2.
Given divisor1, divisor2, uniqueCnt1, and uniqueCnt2, return the minimum possible maximum integer that can be present in either array.
Example 1:
Input: divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3 Output: 4 Explanation: We can distribute the first 4 natural numbers into arr1 and arr2. arr1 = [1] and arr2 = [2,3,4]. We can see that both arrays satisfy all the conditions. Since the maximum value is 4, we return it.
Example 2:
Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1 Output: 3 Explanation: Here arr1 = [1,2], and arr2 = [3] satisfy all conditions. Since the maximum value is 3, we return it.
Example 3:
Input: divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2 Output: 15 Explanation: Here, the final possible arrays can be arr1 = [1,3,5,7,9,11,13,15], and arr2 = [2,6]. It can be shown that it is not possible to obtain a lower maximum satisfying all conditions.
Constraints:
2 <= divisor1, divisor2 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109
Approach overview
Problem Overview: You must construct two arrays of sizes uniqueCnt1 and uniqueCnt2. Numbers in the first array cannot be divisible by divisor1, and numbers in the second cannot be divisible by divisor2. All numbers must be distinct. The goal is to minimize the maximum value used across both arrays.
Approach 1: Binary Search on the Minimum Maximum Value (O(log R) time, O(1) space)
The key observation: instead of constructing arrays directly, search for the smallest value x such that numbers from 1..x can satisfy both arrays. Use binary search on the answer space because feasibility is monotonic. For a candidate x, count how many numbers are not divisible by divisor1, not divisible by divisor2, and not divisible by either. Use inclusion–exclusion with lcm(divisor1, divisor2) to compute overlaps. Check three constraints: enough numbers for array1, enough for array2, and enough total numbers not divisible by both divisors combined to satisfy uniqueCnt1 + uniqueCnt2. If the counts work, shrink the search range; otherwise increase x. This approach converts a combinatorial construction problem into a fast counting check using math and number theory.
Approach 2: LCM-based Counting and Mathematical Deduction (O(log R) time, O(1) space)
This approach focuses on categorizing numbers based on divisibility relationships. Numbers fall into three useful groups: divisible only by divisor1, divisible only by divisor2, and divisible by neither. The overlap is determined using lcm(divisor1, divisor2). During the search for the minimal maximum value, compute how many candidates are safe for array1 (x - x/divisor1) and array2 (x - x/divisor2). Then verify the shared pool of numbers not divisible by either divisor (x - x/divisor1 - x/divisor2 + x/lcm) can cover any remaining requirement after assigning exclusive numbers. This mathematical counting removes any need for simulation or data structures and keeps the feasibility check constant time.
Recommended for interviews: The binary search formulation is what interviewers typically expect. It demonstrates recognition of monotonic search space plus correct use of LCM and inclusion–exclusion. Explaining the counting logic clearly matters more than the code itself. A brute-force construction would be far too slow for large ranges, while the binary search + math approach scales efficiently and shows strong algorithmic reasoning.
Approach 1: Approach 1: Binary Search on the Minimum Maximum Value
This approach leverages binary search to efficiently find the smallest possible maximum value that satisfies all the conditions. The main idea is to binary search on the range of possible maximum integers and check if a given maximum integer can accommodate the required distinct numbers in both arrays without violating the divisibility and uniqueness constraints.
We conduct a binary search over the potential maximum integers. For each mid point, we calculate how many numbers are available for both arrays:
- For arr1, numbers that are not divisible by divisor1 or shared between the two divisors should be counted because all numbers below mid must not be divisible by divisor1 for arr1.
- Similarly, for arr2, count numbers that are not divisible by divisor2 or shared between the two divisors.
def minimize_maximum(divisor1, divisor2, uniqueCnt1, uniqueCnt2):
from math import gcd
def enough(x):
count1 = x // divisor1
count2 = x // divisor2
common = x // (divisor1 * divisor2 // gcd(divisor1, divisor2))
available1 = x - count1
available2 = x - count2
common_available = max(0, available1 + available2 - x + common)
return available1 >= uniqueCnt1 and available2 >= uniqueCnt2 and available1 + available2 - common_available >= uniqueCnt1 + uniqueCnt2
l, r = 1, 2 * (uniqueCnt1 + uniqueCnt2)
while l < r:
mid = (l + r) // 2
if enough(mid):
r = mid
else:
l = mid + 1
return l
# Example usage:
print(minimize_maximum(2, 7, 1, 3)) # Output: 4public class Solution {
public static int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
public static boolean enough(long x, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long count1 = x / divisor1;
long count2 = x / divisor2;
long common = x / ((long)divisor1 * divisor2 / gcd(divisor1, divisor2));
long available1 = x - count1;
long available2 = x - count2;
long commonAvailable = Math.max(0, available1 + available2 - x + common);
return available1 >= uniqueCnt1 && available2 >= uniqueCnt2 && available1 + available2 - commonAvailable >= uniqueCnt1 + uniqueCnt2;
}
public static int minimizeMaximum(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long l = 1, r = 2 * (uniqueCnt1 + uniqueCnt2);
while (l < r) {
long mid = (l + r) / 2;
if (enough(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
r = mid;
else
l = mid + 1;
}
return (int) l;
}
public static void main(String[] args) {
System.out.println(minimizeMaximum(2, 7, 1, 3)); // Output: 4
}
}#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
bool enough(long long x, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long count1 = x / divisor1;
long long count2 = x / divisor2;
long long common = x / ((long long)divisor1 * divisor2 / gcd(divisor1, divisor2));
long long available1 = x - count1;
long long available2 = x - count2;
long long common_available = max(0LL, available1 + available2 - x + common);
return available1 >= uniqueCnt1 && available2 >= uniqueCnt2 && available1 + available2 - common_available >= uniqueCnt1 + uniqueCnt2;
}
int minimizeMaximum(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long l = 1, r = 2LL * (uniqueCnt1 + uniqueCnt2);
while (l < r) {
long long mid = (l + r) / 2;
if (enough(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
r = mid;
else
l = mid + 1;
}
return l;
}
int main() {
cout << minimizeMaximum(2, 7, 1, 3) << endl; // Output: 4
return 0;
}function gcd(a, b) {
while (b !== 0) {
let t = a % b;
a = b;
b = t;
}
return a;
}
function enough(x, divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
let count1 = Math.floor(x / divisor1);
let count2 = Math.floor(x / divisor2);
let common = Math.floor(x / (divisor1 * divisor2 / gcd(divisor1, divisor2)));
let available1 = x - count1;
let available2 = x - count2;
let commonAvailable = Math.max(0, available1 + available2 - x + common);
return available1 >= uniqueCnt1 && available2 >= uniqueCnt2 && available1 + available2 - commonAvailable >= uniqueCnt1 + uniqueCnt2;
}
function minimizeMaximum(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
let l = 1, r = 2 * (uniqueCnt1 + uniqueCnt2);
while (l < r) {
let mid = Math.floor((l + r) / 2);
if (enough(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
r = mid;
else
l = mid + 1;
}
return l;
}
console.log(minimizeMaximum(2, 7, 1, 3)); // Output: 4#include <stdio.h>
#include <algorithm>
int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
bool enough(long long x, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long count1 = x / divisor1;
long long count2 = x / divisor2;
long long common = x / ((long long)divisor1 * divisor2 / gcd(divisor1, divisor2));
long long available1 = x - count1;
long long available2 = x - count2;
long long common_available = std::max(0LL, available1 + available2 - x + common);
return available1 >= uniqueCnt1 && available2 >= uniqueCnt2 && available1 + available2 - common_available >= uniqueCnt1 + uniqueCnt2;
}
int minimizeMaximum(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long l = 1, r = 2LL * (uniqueCnt1 + uniqueCnt2);
while (l < r) {
long long mid = (l + r) / 2;
if (enough(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
r = mid;
else
l = mid + 1;
}
return l;
}
int main() {
printf("%d\n", minimizeMaximum(2, 7, 1, 3)); // Output: 4
return 0;
}using System;
class Program {
static int GCD(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
static bool Enough(long x, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long count1 = x / divisor1;
long count2 = x / divisor2;
long common = x / ((long)divisor1 * divisor2 / GCD(divisor1, divisor2));
long available1 = x - count1;
long available2 = x - count2;
long commonAvailable = Math.Max(0, available1 + available2 - x + common);
return available1 >= uniqueCnt1 && available2 >= uniqueCnt2 && available1 + available2 - commonAvailable >= uniqueCnt1 + uniqueCnt2;
}
static int MinimizeMaximum(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long l = 1, r = 2 * (uniqueCnt1 + uniqueCnt2);
while (l < r) {
long mid = (l + r) / 2;
if (Enough(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
r = mid;
else
l = mid + 1;
}
return (int)l;
}
static void Main() {
Console.WriteLine(MinimizeMaximum(2, 7, 1, 3)); // Output: 4
}
}This Python solution implements the binary search approach. We define a helper function `enough` which checks if a given maximum integer 'x' can satisfy the conditions for both arrays given the constraints.
The binary search is performed over the interval [1, 2 * (uniqueCnt1 + uniqueCnt2)], adjusting the search range according to the outcome of the 'enough' function.
This ensures optimal determination of the minimum maximum integer efficiently.
Time Complexity: O(log(max) * log(max(a, b))), where max is the upper bound of our search range and 'a', 'b' are the divisors.
Space Complexity: O(1) as only a constant amount of space is used.
Approach 2: Approach 2: LCM-based Counting and Mathematical Deduction
This approach utilizes the Least Common Multiple (LCM) to determine integers that are not useful for any of the two arrays and applies arithmetic operations to calculate the valid count of numbers that can be distinctly placed in either array without causing violations.
Consider inclusion-exclusion principles, counting valid numbers not divisible by each divisor, and ensuring there is no overlap between chosen numbers for both arrays.
By iterating over potential ranges of numbers, use mathematical deduction to distribute numbers optimally.
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
def minimize_maximum_ld(divisor1, divisor2, uniqueCnt1, uniqueCnt2):
lo, hi = 1, (uniqueCnt1 + uniqueCnt2) * 2
while lo < hi:
mid = (lo + hi) // 2
cnt1 = mid // divisor1
cnt2 = mid // divisor2
cnt_common = mid // lcm(divisor1, divisor2)
len_valid1 = mid - cnt1
len_valid2 = mid - cnt2
if len_valid1 < uniqueCnt1 or len_valid2 < uniqueCnt2 or (len_valid1 + len_valid2 - cnt_common) < uniqueCnt1 + uniqueCnt2:
lo = mid + 1
else:
hi = mid
return lo
# Example usage:
print(minimize_maximum_ld(3, 5, 2, 1)) # Output: 3#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
long long lcm(int a, int b) {
return (long long)a * (b / gcd(a, b));
}
int minimizeMaximumLD(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long lo = 1, hi = (uniqueCnt1 + uniqueCnt2) * 2;
while (lo < hi) {
long long mid = (lo + hi) / 2;
long long count1 = mid / divisor1;
long long count2 = mid / divisor2;
long long count_common = mid / lcm(divisor1, divisor2);
long long len_valid1 = mid - count1;
long long len_valid2 = mid - count2;
if (len_valid1 < uniqueCnt1 || len_valid2 < uniqueCnt2 || (len_valid1 + len_valid2 - count_common) < uniqueCnt1 + uniqueCnt2)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
int main() {
cout << minimizeMaximumLD(3, 5, 2, 1) << endl; // Output: 3
return 0;
}This Python solution leverages mathematical principles and computes available lengths for each array after eliminating numbers divisible by each divisor. The algorithm ensures numbers are optimally assigned to either array.
Time Complexity: O(log(max_num) + log(min(divisor1, divisor2))) due to binary search and gcd calculations.
Space Complexity: O(1) since we use constant auxiliary space.
Approach 3: Default Approach
func minimizeSet(divisor1 int, divisor2 int, uniqueCnt1 int, uniqueCnt2 int) int {
divisor := lcm(divisor1, divisor2)
left, right := 1, 10000000000
for left < right {
mid := (left + right) >> 1
cnt1 := mid/divisor1*(divisor1-1) + mid%divisor1
cnt2 := mid/divisor2*(divisor2-1) + mid%divisor2
cnt := mid/divisor*(divisor-1) + mid%divisor
if cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1+uniqueCnt2 {
right = mid
} else {
left = mid + 1
}
}
return left
}
func lcm(a, b int) int {
return a * b / gcd(a, b)
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search on the Minimum Maximum Value | Time Complexity: O(log(max) * log(max(a, b))), where max is the upper bound of our search range and 'a', 'b' are the divisors. |
| Approach 2: LCM-based Counting and Mathematical Deduction | Time Complexity: O(log(max_num) + log(min(divisor1, divisor2))) due to binary search and gcd calculations. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Maximum Value | O(log R) | O(1) | General case; most intuitive and commonly used interview solution |
| LCM-based Mathematical Counting | O(log R) | O(1) | When you want a pure mathematical feasibility check using inclusion–exclusion |
Frequently asked questions
Is Minimize the Maximum of Two Arrays easy or hard?
The problem is rated Medium on LeetCode but can feel tricky at first. The challenge is recognizing that direct construction is unnecessary and that the maximum value can be found using binary search with mathematical feasibility checks.
Minimize the Maximum of Two Arrays Python/Java solution
Implement binary search over the maximum value and use arithmetic formulas to count valid numbers. Compute lcm(divisor1, divisor2) to avoid double counting when both divisibility rules overlap. The same logic translates cleanly across Python, Java, C++, and other languages since it only uses integer arithmetic.
How to solve Minimize the Maximum of Two Arrays in O(log n)?
Treat the answer as a monotonic search problem. Binary search the smallest maximum value x. For each x, compute counts of numbers not divisible by divisor1, not divisible by divisor2, and not divisible by either using inclusion–exclusion with LCM. If these counts satisfy uniqueCnt1 and uniqueCnt2 simultaneously, the value is feasible and the search moves left.
What is the best approach for Minimize the Maximum of Two Arrays?
The most efficient approach is binary search on the answer combined with mathematical counting. For a candidate maximum value x, count how many numbers from 1..x are valid for each array using divisibility rules and LCM inclusion–exclusion. This feasibility check runs in constant time, and the binary search over the value range gives an overall O(log R) time complexity.
Is Minimize the Maximum of Two Arrays asked at Google/Amazon/Meta?
This style of problem appears frequently in big tech interviews because it combines binary search on the answer with number theory. Companies such as Google, Amazon, and Meta commonly test variations of feasibility checks, divisibility counting, and LCM-based inclusion–exclusion reasoning.
What data structure is used in Minimize the Maximum of Two Arrays?
No complex data structure is required. The solution relies on mathematical counting, integer division, and least common multiple (LCM) calculations. Binary search is used to explore the answer space efficiently.
What is the time complexity of Minimize the Maximum of Two Arrays?
The optimal solution runs in O(log R) time where R is the upper bound of the search range for the maximum value. Each binary search step performs constant-time arithmetic operations such as division and LCM calculation. Space complexity is O(1) since no additional data structures are required.