Hello, reader 👋🏽 ! Welcome to day 3 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up today's LeetCode's Daily Challenge Question.

🤔 Problem Statement

There are n balloons attached on a rope. The colours for all the n balloons are given by string colours where colour[i] represents the colour of ith balloon. There's also a neededTime array given. neededTime[i] represents the time taken to remove ith balloon.

Given n balloons, they need to be modified such that no 2 consecutive balloons are of the same colour. The consecutive same coloured balloons need to be removed in the minimum time.

• For e.g. colors: "aabaa" neededTime: [1,2,3,4,1] then the minimum time required to remove consecutive same coloured balloon is 2 => removing the first and last balloon gives the least cost.
• Another e.g.: colors: "abc" neededTime: [1,2,3] then the minimum time required to remove consecutive same coloured balloon is 0 => since there are no consecutive balloons with same color.

Link to the problem.

💬 Initial Thought Process

• Looking at the word minimum cost, I could think that the problem was either DP or Greedy based.
• The very intuitive process I could think of was: at every balloon i, look for all balloons from [i+1 to i+k] such that colors[i] == colors[i+1] ... == colors[i+k]. And remove k-1 balloons that have the smallest cost.
• Then start the same process for balloons from next i+k+1.
• This initial intuition led me to think of a min heap that would allow me to poll all but 1 smallest element.
• And I began developing out a rough diagram and pseudo code.

👩🏽‍💻 Solution 1

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();

        int cost = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i<n;) {
            char color = colors.charAt(i);
            int time = neededTime[i];

            // Add the current time to the PQ
            pq.add(time);

            int j = i+1;
            // Check for consecutive balloons with same colors
            while(j < n && color == colors.charAt(j)) {
                pq.add(neededTime[j]);
                j++;
            }

            // Remove k-1 elements from the PQ => this removed k-1 smallest elements
            while(pq.size() > 1) {
                cost+= pq.poll();
            }

            // Remove the extra element
            pq.poll();
            i = j;
        }

        return cost;
    }
}

Time Complexity: O(n) => You process every element once, n = length of colours
Space Complexity: O(n) => In the worst case all n elements are of the same colour

• As I was coding the above approach, I realised that this basically sums up k-1 elements and leaves the kth element from the consecutive elements which is the element with the maximum removal time.

💬 Thought Process for optimisation

• The problem with the above code is that priority queue was not needed at all!
• I could have just summed up all the elements with the same colour from [i to i+k] while keeping track of the maximum element in this window. Let's denote this by sum and maxVal.
• Then once the window is passed, that is I reach an element that's not the same colour as colour[i], I subtract the maxVal from the sum sum - maxVal and add this to the cost.
• This gives the sum of the time needed to remove k-1 smallest elements which have the same colour.

👩🏽‍💻 Solution 2

• Below is the code for the optimised approach:

  class Solution {
    public int minCost(String colors, int[] neededTime) {
        if(colors == null || colors.length() == 0 || neededTime == null || neededTime.length == 0) {
            return 0;
        }
  
        int n = colors.length();
        int cost = 0;
  
        for(int i = 0; i<n; ) {
            char color = colors.charAt(i);
            int j = i+1;
  
            int maxVal = neededTime[i];
            int sum = neededTime[i];
  
            // Process until you reach a value that does not have the same color as colors[i]
            while(j < n && color == colors.charAt(j)) {
                int currTime = neededTime[j];
                maxVal = Math.max(currTime, maxVal);
                sum += currTime;
                j++;
            }
  
            // Remove the largest neededTime among the list of colors [i, i+j]
            cost += sum-maxVal;
            i = j;
        }
        return cost;
    }
  }
  

Time Complexity: O(n) => you traverse the colours and process every colour once,
n = length of colours
Space Complexity: O(1)

There are other solutions to this problem as well.

1. Instead of running multiple loops, we can solve this in just a single pass
2. Use pointers to represent the beginning and ending of every window with consecutive same colours.

Although I am not explaining these here, you can check out the code for the above 2 approaches in the GitHub repo.

Conclusion

That's a wrap for todays' problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!