Skip to main content
Talentd

Minimize the Maximum of Two Arrays - Solution & Explanation

MediumMathBinary SearchNumber Theory19 min readAsked at: Amazon
Practice this problem

Problem Statement

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.
  • arr2 contains uniqueCnt2 distinct positive integers, each of which is not divisible by divisor2.
  • No integer is present in both arr1 and arr2.

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 <= 105
  • 1 <= uniqueCnt1, uniqueCnt2 < 109
  • 2 <= 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.
If at any point, the counts satisfy the requirements for both arrays (i.e., remaining numbers meet or exceed the unique count required for each), adjust the search range accordingly to converge on the minimum possible maximum value.

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.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) as only a constant amount of space is used.

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.
Space Complexity: O(1) since we use constant auxiliary space.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search on Maximum ValueO(log R)O(1)General case; most intuitive and commonly used interview solution
LCM-based Mathematical CountingO(log R)O(1)When you want a pure mathematical feasibility check using inclusion–exclusion

Video Solution

Leetcode Biweekly Contest 94 | 2513 : Minimize the Maximum of Two Arrays Solution | Newton School • Coding Community | Newton School • 5,506 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimize the Maximum of Two Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer