DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Replace Non-Coprime Numbers in Array - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stack = []
        for num in nums:
            stack.append(num)

            while len(stack) >= 2:
                num1, num2 = stack[-1], stack[-2]

                hcf = math.gcd(num1, num2)
                if hcf == 1: # co-prime, no merging needed
                    break

                lcm = num1 * num2 // hcf
                stack.pop()
                stack.pop()
                stack.append(lcm)
                
        return stack

Complexity Analysis

Here, n is the input size, and M is the maximum value in the input.

  • Time Complexity: O(n log M)
    • Each of the n numbers enters the stack once, and every merge operation reduces the total count of numbers by one, meaning there are at most n merges.
    • Since each merge requires an O(log M) calculation to find the GCD, so the total time is simply the number of elements multiplied by the cost of merging them.
  • Space Complexity: O(n) – The stack stores at most n elements at any time, since LCMs replace existing elements rather than increasing stack size.