Replace Non-Coprime Numbers in Array

main.md

Question

Approach

I solve this problem with a stack-based approach. I process the array from left to right, pushing each number onto the stack. Whenever the new number and the top of the stack are non-coprime (gcd > 1), I pop the stack, replace the two numbers with their LCM, and continue checking with the new top. This merging continues until the top of the stack is coprime with the current value (or the stack is empty). This ensures all adjacent non-coprime numbers collapse into their LCMs step by step, and by the problem statement, the result is unique regardless of order.

Implementation

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stack = []
        for num in nums:
            while stack:
                g = gcd(stack[-1], num)
                if g == 1:
                    break
                num = stack.pop() * num // g
            stack.append(num)
        return stack

Complexities

• Time: O(n⋅α)), where n is the number of elements and α is the cost of gcd/lcm operations.
• Space: O(n)