Double Priority Queue (with.Java)

This is an article about double priority queue (with.Java).

I want to solve the coding test problem, find out how to solve it differently from the retrospective of the problem I solved, and get to know.

Let’s get to the problem first.

Problem

The dual priority queue refers to a data structure that allows you to perform the following operations.

Delete the maximum value from the D1 queue.

Delete the minimum value from the D-1 queue.

When the operation operations to be performed by the dual priority queue are given as parameters, implement a solution function to return [maximum, minimum] if the queue is empty after processing all operations.

Restrictions

• Operations is an array of strings that are greater than or equal to 1 million and less than or equal to 1 million.
• Elements in operations represent the operations that the queue will perform.
• Elements are given in the form of “command data.” - If there are more than one maximum/minimum value in the operation to delete maximum/minimum value, delete only one.
• If an empty queue is given an operation to delete data, it ignores the operation.

Input/output Examples

problem solving

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {Integer.MIN_VALUE, Integer.MAX_VALUE};
        ArrayList<Integer> list = new ArrayList<>();

        for(String str : operations){
            if(str.contains("I")){
                list.add(Integer.valueOf(str.split(" ")[1]));
                Collections.sort(list);
            }
            if(str.contains("D")){
                if(list.size() == 0){continue;}
                if(str.split(" ")[1].equals("1")){
                    list.remove(list.size() - 1);
                }else{
                    list.remove(0);
                }
            }
        }


        if(list.size() == 0){
            answer[0] = 0;
            answer[1] = 0;
            return answer;
        }else{
            for(int i = 0; i < list.size(); i++){
                if(list.get(i) > answer[0]){
                    answer[0] = list.get(i);
                }
                if(list.get(i) < answer[1]){
                    answer[1] = list.get(i);
                }
            }
        }

        return answer;
    }
}

Solution Description

• Initializing variables: the answer array has the initial values of Integrer.MIN_VALUE and Integrer.MAX_VALUE.list is the ArrayList to serve as the queue.
• Handles commands: Process commands by traversing each string in the operations array. Strings containing the “I number” use split to extract numbers, add them to the list, and sort them. “D 1” deletes the maximum value and “D-1” deletes the minimum value.
• Calculate the result: Return [0, 0] if the list is empty after the command is processed. If not, it traverses the list and stores the maximum and minimum values in the answer array.

Conclusion

A dual priority queue can be implemented as above.

This method has the advantage of processing commands in order and simply implementing them using ArrayList.

It is a method of processing the command appropriately according to the state of the queue to derive the final result.