Approaches To Problem Solving #21 (Multiset | Array)
Problem : Given a list of lists of integers, return the smallest difference that can be made by choosing exactly one integer from each of the lists and taking the difference between the maximum and the minimum number of the chosen integers.
Let us consider an example to understand the problem better,
At first glance, this problem seems like one of those in which we have to choose integers from each list and maintain the maximum and minimum out of the elements that have been chosen.
Whenever we think about choosing elements, recursive approaches such as Dynamic Programming comes through as one of the best tools. Let us try to explore one such solution for this problem.
Approach #1: Let us try to define the states for our dynamic programming first. If we consider the given list of lists as a matrix, then to define our position in the given matrix, we need both, row and column. But, are these two variables sufficient to define a state, in the given problem? No. We need two more state variables. One to maintain the maximum integer and another to maintain the minimum integer found so far.
The base case, here, is relatively easier to determine. We start from the first row and when we reach some row that is out of bounds, we return the difference between the maximum and minimum value found so far.
Let us discuss the transitions for our dynamic programming now. At any {row, column} position, we either pick the element or we don’t. If we pick the element, we update our maximum and minimum elements found so far. Otherwise, we move to the next element in the current row.
Talking about the time complexity of this approach, we would roughly get ~O(N * M * K * K), where N is the size of the longest row, M is the size of the longest column and K is the largest value that can be picked from all the lists. Not very impressive, of course.
We can try to solve this problem by maintaining N pointers, where every list (row) gets a single pointer. Since, the ordering of the numbers in the lists don’t really matter. We can try sorting all the lists first and then finding our solution. How does having N pointers help? If we can imagine having a data structure that can provide us with the minimum and maximum item out of the elements that the N pointers currently point to, it can ease the complexity of the problem.
Multiset is one such data structure that can be used to fetch the smallest and largest element in O(1), each, whereas maintaining them can be done in O(logN).
With all this information in our minds, let us discuss our approach.
Approach #2: We sort all the lists and appoint a pointer to each of the lists. These pointers will be pointing at the smallest element i.e., the first element of each list, initially. We insert the values being pointed to the multiset. It is easy to figure out, at this stage, that the multiset will be having one element for each list at any given instance.
How do we maintain the multiset to always have ≤ N elements? We keep updating our answer by comparing the current answer to the difference of the maximum and the minimum element in the multiset. It can be proved using some intuition that the minimum element once compared with some maximum element, won’t be getting used again. Why? because, as the lists are sorted, next elements getting explored are always going to be larger, hence increasing the difference between the maximum and minimum elements.
Hence, after updating our answer for the minimum difference, we pop the minimum element out from the multiset and if there are more elements left in that list that contains the current minimum element, we increment that list’s pointer to point to the next element.
The complexity for this solution is ~O(N * M * log(N)), where N and M represent the number of lists and the maximum size of the list present, respectively.
Hence, we have made a significant improvement over our first solution.
In our next article, one of the problems that we are going to discuss is given below,
Problem : We are looking to paint a row of N fences that can be of K different colors. Our goal is to minimise the cost while ensuring that no two neighboring fences are of the same color. Given a N by K matrix where the ith row and jth column represents the cost to paint the ith fence with jth color, return the minimum cost which achieves this goal.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Dynamic Programming, N-pointers and Multisets further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
This is the 21st article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
