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.Problem Overview: You receive an integer array. Whenever two adjacent numbers are not coprime (their gcd > 1), replace them with their lcm. Continue until every adjacent pair is coprime. The final array after all merges is the result.
Approach 1: Brute Force Simulation (O(n2 log M) time, O(n) space)
Directly simulate the process described in the problem. Iterate through the array and check adjacent elements using gcd(a, b). If the gcd is greater than 1, compute lcm(a, b) and replace the pair with the merged value. Because a merge can create new non‑coprime neighbors, restart the scan or step backward after each replacement.
This approach repeatedly scans the array and performs many shifts after merges, which leads to quadratic behavior in the worst case. It demonstrates the rule clearly but becomes slow when many cascading merges happen. Still useful for understanding the mechanics of repeated LCM replacement using number theory operations.
Approach 2: Stack-Based Merge (O(n log M) time, O(n) space)
Use a stack to maintain the current valid sequence. Iterate through the array and push each number. After pushing, check the top two values. If their gcd is greater than 1, pop them and push their lcm. Continue merging while the new top pair remains non‑coprime.
The key insight: each number only participates in a limited number of merges, so the total operations stay linear relative to the array length. The stack naturally handles chain reactions where one merge triggers another. This pattern is common when resolving adjacent constraints in stack-based processing of an array.
Recommended for interviews: The stack-based approach is the expected solution. It reduces repeated scans and handles cascading merges efficiently with amortized linear processing. Interviewers often want to see recognition that adjacent operations with possible backtracking are naturally solved with a stack. Mention the brute-force simulation first to show understanding, then optimize using the stack merge strategy.
This basic solution involves iterating through the list repeatedly to check if any two adjacent elements are non-coprime. If found, we replace them with their LCM and continue. We keep scanning and modifying the list until no such pairs are found. Though straightforward, this approach may be inefficient due to repeated scans of the list as elements change.
We define two functions: gcd (from the Python standard library) to find the Greatest Common Divisor and lcm to compute the Least Common Multiple. The main function, replace_non_coprimes, uses a while loop to traverse the list. Whenever adjacent non-coprime numbers are found, they are replaced with their LCM and the subsequent element is removed. The index i is adjusted to ensure all potential pairs are evaluated. This continues until no modifications are required.
Python
JavaScript
Time Complexity: O(n^2), due to repeated list scanning and modification.
Space Complexity: O(1), as alterations are in-place.
Utilizing a stack data structure can effectively manage the merging process when working with adjacent non-coprime numbers. By pushing elements onto a stack, we can consistently assess the conditions for non-coprimality, merging elements as we identify them and leveraging the stack's Last-In-First-Out (LIFO) nature to efficiently manage remaining elements.
The Java solution employs a stack to hold elements as we iterate through the array. If the peek of the stack and the current number are non-coprime, we repeatedly pop and merge them until coprime pairs appear. This ensures minimal temporal space and logical quandaries, especially as the stack's nature facilitates the arbitrary order nature of the operation.
Time Complexity: O(n), each element is pushed/popped from the stack a limited number of times.
Space Complexity: O(n), in the worst case, all elements may reside in the stack.
If there exist three adjacent numbers x, y, z that can be merged, then the result of first merging x and y, then merging z, is the same as the result of first merging y and z, then merging x. Both results are LCM(x, y, z).
Therefore, we can always prefer to merge the adjacent numbers on the left, and then merge the result with the adjacent number on the right.
We use a stack to simulate this process. We traverse the array, and for each number, we push it into the stack. Then we continuously check whether the top two numbers of the stack are coprime. If they are not coprime, we pop these two numbers out of the stack, and then push their least common multiple into the stack, until the top two numbers of the stack are coprime, or there are less than two elements in the stack.
The final elements in the stack are the final result.
The time complexity is O(n times log M), and the space complexity is O(n). Where M is the maximum value in the array.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), due to repeated list scanning and modification. |
| Stack-Based Approach | Time Complexity: O(n), each element is pushed/popped from the stack a limited number of times. |
| Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2 log M) | O(n) | Good for understanding the merge rule and quick prototypes |
| Stack-Based Merge with GCD/LCM | O(n log M) | O(n) | Optimal solution for interviews and large inputs |
Replace Non-Coprime Numbers in Array | Simple Intuition | Leetcode 2197 | codestorywithMIK • codestorywithMIK • 8,375 views views
Watch 9 more video solutions →Practice Replace Non-Coprime Numbers in Array with our built-in code editor and test cases.
Practice on FleetCode