🔗 Making It Spicier

Leo, who loves spicy food, wants to make every dish's Scoville index at least K. To make every dish's Scoville index at least K, Leo mixes the two dishes with the lowest Scoville index into a new dish using the special method below.

Scoville index of the mixed dish = Scoville index of the least spicy dish + (Scoville index of the second least spicy dish * 2)

Leo repeats this mixing until every dish's Scoville index is at least K.

Given an array scoville containing the Scoville index of each dish Leo has, and the desired Scoville index K, write a solution function that returns the minimum number of mixes needed to make every dish's Scoville index at least K.

• The length of scoville is between 2 and 1,000,000, inclusive.
• K is between 0 and 1,000,000,000, inclusive.
• Each element of scoville is between 0 and 1,000,000, inclusive.
• If it's impossible to make every dish's Scoville index at least K, return -1.

Mixing the dish with a Scoville index of 1 and the dish with a Scoville index of 2 results in the following.

New dish's Scoville index = 1 + (2 * 2) = 5

Remaining dishes' Scoville indexes = [5, 3, 9, 10, 12]

Mixing the dish with a Scoville index of 3 and the dish with a Scoville index of 5 results in the following.

New dish's Scoville index = 3 + (5 * 2) = 13

Remaining dishes' Scoville indexes = [13, 9, 10, 12]

Every dish's Scoville index is now at least 7, and it took 2 mixes.

The problem itself is simple. Take the smallest and second smallest values from scoville and mix them. Repeat this process until every element's value is at least K.

If there's a dish that can't reach K even after performing every possible operation, return -1.

Since the rule for which elements to pull out is fixed, combinations don't fit here.

1. Every time we pull data, the smallest value must come out.
2. Elements need to be freely inserted and removed.

At first glance, wouldn't sorting via ArrayList work? But this approach has extremely poor efficiency, since ArrayList would need to be re-sorted every time an operation is performed.

This problem can be solved easily if you know about the PriorityQueue object, and can be quite painful if you don't.

PriorityQueue is called a queue by name, but it doesn't work in the typical LIFO fashion. The unique rules of PriorityQueue are as follows.

1. It determines the priority of the data and outputs the data with the highest priority first.
2. Since it uses a binary tree structure, its time complexity is $O(N\log{N})$.
3. Its base follows Queue.

The characteristics of PriorityQueue fit this problem very well. Since each element is a number, if we designate the lowest number as the highest priority and output data accordingly, we can retrieve the smallest data without needing to sort at all.

JAVA
// Lowest priority first
PriorityQueue<Integer> queue = new PriorityQueue<>();

// Highest priority first
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

When declaring a PriorityQueue, you can specify the priority.

Since this problem requires pulling out the smallest number first, it makes sense to pull elements out in ascending order of priority.

If the element pulled from the PriorityQueue doesn't exceed K, there's still a dish that's not spicy enough, so we perform the operation.

If it exceeds K, then even the least spicy dish exceeds K, so there's no need to perform any more operations.

JAVA
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * Making It Spicier class
 *
 * @author RWB
 * @since 2021.12.27 Mon 13:43:34
 */
class Solution
{
	/**
	 * Answer return method
	 *
	 * @param scoville: [int[]] Array of Scoville indexes of the dishes
	 * @param K: [int] Target Scoville index
	 *
	 * @return [int] Answer
	 */
	public int solution(int[] scoville, int K)
	{
		int answer;
		
		// If there aren't enough elements to mix
		if (scoville.length < 2)
		{
			answer = -1;
		}
		
		// If there are enough elements to mix
		else
		{
			PriorityQueue<Integer> queue = new PriorityQueue<>();
			
			answer = 0;
			
			for (int item : scoville)
			{
				queue.add(item);
			}
			
			while (Objects.requireNonNull(queue.peek()) < K)
			{
				// If there aren't enough elements to mix
				if (queue.size() < 2)
				{
					answer = -1;
					
					break;
				}
				
				queue.add(Objects.requireNonNull(queue.poll()) + (Objects.requireNonNull(queue.poll()) * 2));
				
				answer++;
			}
		}
		
		return answer;
	}
}

Since queue.poll() and queue.peek() may possibly return null, use Objects.requireNonNull() to eliminate related errors.

Even without Objects.requireNonNull(), the behavior wouldn't be affected.