Problem statement

https://leetcode.com/problems/replace-non-coprime-numbers-in-array/

Solution

Quite easy problem: all you need to do is to use stack to similate process: put element to stack and while last two elements have gcd more then one, extract them and put their lcm to stack. Notice, that if we have in problem something about operation with adjacent elements, you should think about stack.

Complexity

It is O(n log M) for time, where n = len(A) and M is the maximum number, we have log term due to evaluation of gcd/lcm. Space complexity is O(n).

Code

class Solution:
    def replaceNonCoprimes(self, A):
        n, stack = len(A), []
        for x in A:
            stack += [x]
            while len(stack) >= 2 and gcd(stack[-1], stack[-2]) > 1:
                stack += [lcm(stack.pop(), stack.pop())]
        return stack