1578. Minimum Time To Make Rope Colorful - Explanation

Problem Link



1. Two Pointers - I

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        n = len(neededTime)
        res = i = 0
        while i < n:
            j = i
            maxi = curr = 0
            while j < n and colors[j] == colors[i]:
                maxi = max(maxi, neededTime[j])
                curr += neededTime[j]
                j += 1
            res += curr - maxi
            i = j
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

2. Two Pointers - II

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        l, res = 0, 0
        for r in range(1, len(colors)):
            if colors[l] == colors[r]:
                if neededTime[l] < neededTime[r]:
                    res += neededTime[l]
                    l = r
                else:
                    res += neededTime[r]
            else:
                l = r
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

3. Two Pointers - III

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        res = maxi = 0
        for i in range(len(colors)):
            if i and colors[i] != colors[i - 1]:
                maxi = 0
            res += min(maxi, neededTime[i])
            maxi = max(maxi, neededTime[i])
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.