_3229. Minimum Operations to Make Array Equal to Target.md

3229. Minimum Operations to Make Array Equal to Target

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Completed during Weekly Contest 407 (q4)

Back to top

---

First completed : July 21, 2024

Last updated : July 21, 2024

---

Related Topics : Array, Dynamic Programming, Stack, Greedy, Monotonic Stack

Acceptance Rate : 38.83 %

---

Notes

    We can adjust the groups greedily taking the largest 
    group of similar signed values
    
    Have a feeling it's looking for a more mathematical
    approach though cause of the 
    
    Hard label --> potential speed issue?


    Realized this is a matter of identifying the crit points
    and divide and conquering from there

    I'm aware that this could be improved further by using 
    index references instead of passing nums[i:j] each time 
    since depending on the implementation, this could result 
    in Array copying. Though in the end, this is minimal and 
    if it is the case, I believe this would result in a worst 
    case O(n^2) space complexity due to it.

---

Solutions

• Weekly Contest 407/h3229 q4.py

Python

h3229 q4.py

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        # only positives are passed into here
        def zeroHelper(nums: List[int], offset: int = 0) -> int :
            if not nums :
                return 0
            if len(nums) == 1 :
                return nums[0] + offset

            valDif = -1 * min(nums)
            counter = (-valDif + offset)

            prev = 0
            prevIsZero = True
            for i, val in enumerate(nums) :
                val += valDif
                if val == 0 :
                    if not prevIsZero :
                        counter += zeroHelper(nums[prev:i], valDif)
                    prev = i + 1
                    prevIsZero = True
                else :
                    prevIsZero = False

            counter += zeroHelper(nums[prev:], valDif)
            return counter

        difs = [nums[x] - target[x] for x in range(len(nums))]
        counter = 0

        prev = 0
        prevPositive = True
        prevIsZero = True
        for i, val in enumerate(difs) :
            currIsPos = bool(val > 0)
            if val == 0 :
                if not prevIsZero :
                    counter += zeroHelper([abs(x) for x in difs[prev:i]])
                prev = i + 1
                prevIsZero = True
            elif currIsPos != prevPositive and not prevIsZero:
                counter += zeroHelper([abs(x) for x in difs[prev:i]])
                prev = i
            else :
                prevIsZero = False

            prevPositive = currIsPos
        counter += zeroHelper([abs(x) for x in difs[prev:]])

        return counter