You are given an array of integers nums. Perform the following steps:
nums that are non-coprime.Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.
The test cases are generated such that the values in the final array are less than or equal to 108.
Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.
Example 1:
Input: nums = [6,4,3,2,7,6,2] Output: [12,7,6] Explanation: - (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2]. - (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2]. - (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2]. - (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [12,7,6]. Note that there are other ways to obtain the same resultant array.
Example 2:
Input: nums = [2,2,1,1,3,3,3] Output: [2,1,1,3] Explanation: - (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3]. - (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3]. - (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [2,1,1,3]. Note that there are other ways to obtain the same resultant array.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105108.In #2197 Replace Non-Coprime Numbers in Array, the goal is to repeatedly replace adjacent numbers that are not coprime with their LCM until no such pair exists. A key observation is that once two numbers are merged, the result may again become non-coprime with the previous element. This naturally suggests using a stack-based approach.
Iterate through the array and push numbers onto a stack. Whenever the top element and the current value have a gcd > 1, they are not coprime. Replace them with their lcm, pop the stack, and continue checking with the new top. This repeated merging ensures all adjacent pairs remain coprime.
The algorithm relies on efficient GCD computation from number theory and controlled stack merging. Each element may be merged multiple times, but overall operations remain manageable. The typical time complexity is around O(n log M) where M is the maximum number value, with O(n) auxiliary space for the stack.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack with GCD/LCM merging | O(n log M) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Notice that the order of merging two numbers into their LCM does not matter so we can greedily merge elements to its left if possible.
If a new value is formed, we should recursively check if it can be merged with the value to its left.
To simulate the merge efficiently, we can maintain a stack that stores processed elements. When we iterate through the array, we only compare with the top of the stack (which is the value to its left).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
LCM preserves the combined divisibility properties of the numbers being merged. Since the problem requires replacing non-coprime neighbors with a single value representing both, the least common multiple ensures correctness for future comparisons.
Yes, problems involving GCD, LCM, and stack-based merging patterns are common in FAANG-style interviews. This question tests number theory concepts, array manipulation, and the ability to design iterative merge logic.
A stack is the most effective data structure for this problem. It allows you to efficiently track previous elements and repeatedly merge values when newly formed numbers are still non-coprime with earlier ones.
The optimal approach uses a stack combined with GCD calculations. As you iterate through the array, merge adjacent numbers that share a common factor by replacing them with their LCM, and continue checking with the previous elements on the stack.