Challenge: The k Cheapest Flights

Lab Java Beginner 10 points

Read n flight prices and print the k cheapest in ascending order, using a PriorityQueue (poll k times).

Input

Line 1: n k (1 ≤ k ≤ n). Line 2: n prices.

Output

The k cheapest prices, ascending.

Example

Input

6 3
450 120 300 120 999 210

Output

120 120 210

Sample input available Sample output available

Editor

Java

Hints

offer every price into a PriorityQueue (a min-heap).

poll() k times – each poll gives the next cheapest.

Solution explanation

n offers and k polls: O((n + k) log n).

Show solution

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i = 0; i < n; i++) pq.offer(sc.nextInt());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            if (i > 0) sb.append(' ');
            sb.append(pq.poll());
        }
        System.out.println(sb);
    }
}

Output

Answer