Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After the processed prefix has no adjacent non-coprime pair, appending one new value can create a conflict only at the end. Merging that pair into its least common multiple may create another conflict with the preceding value, so a stack naturally supports the required backward chain.

Approach

Append each input value to the result stack. While its last two values have greatest common divisor g > 1, replace them with their least common multiple a*b/g. Repeat because the merged value may share a factor with its new left neighbor. Stop when the final pair is coprime or fewer than two values remain. Return the stack, which preserves order and has no remaining legal adjacent merge.

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        res = []

        for n in nums:
            res.append(n)
            while len(res) >= 2:
                n1, n2 = res[-2], res[-1]
                g = gcd(n1, n2)
                if g == 1:
                    break
                res.pop()
                res[-1] = n1 * n2 // g

        return res

Complexity analysis

Let n = nums.length and V bound gcd operands, including intermediate LCMs. Time is O(n log(V + 1)) under unit-cost bounded-integer arithmetic: each input is pushed once, every successful merge removes one stack entry, and there is at most one failed gcd check per input. The +1 includes all-one inputs. The result stack needs O(n) peak space; other state is O(1). Intermediate LCMs divide a final value and are therefore at most 10^8 under the constraints.