Leetcode 1578. Minimum Time to Make Rope Colorful

Link to 1578

Solution

Link to solution

class Solution {
    func minCost(_ colors: String, _ neededTime: [Int]) -> Int {
     // Initialize to pointers i, j
        var totalTime = 0
        var i = 0, j = 0
        let colors = Array(colors)
        while  i < neededTime.count && j < neededTime.count {
            var currTotal = 0, currMax = 0
            // Find all the balloons having the same color as the
            // balloon indexed at i, record the total removal time
            // and the maximum removal time
            while j < neededTime.count && colors[i] == colors[j] {
                currTotal += neededTime[j]
                currMax = max(currMax, neededTime[j])
                j += 1
            }
            // Once we reach the end of the current group, add the cost of
            // this group to total_time, and reset two pointers.
            totalTime += currTotal - currMax
            i = j
        }
       return totalTime
    }
}

Complexity Analysis

Time complexity: O(n)

• We need to iterate over colors and neededTime. The right index right is incremented by O(n) times while the left index left is updated by no more than O(n) times. In each step of the iteration, we have some calculations that take constant time.
  • To sum up, the overall time complexity is O(n)

Space complexity: O(1)

• We only need to update several values: totalTime, currTotal, currMax, i and j, which takes constant space.