{"id":"e499a21a-0681-4c9b-99de-2bb6231939e7","name":"Merge K Sorted Lists","description":"1. You are given a list of lists, where each list is sorted.\r\n2. You are required to complete the body of mergeKSortedLists function. The function is expected to merge k sorted lists to create one sorted list.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"Space complextiy = O(k)\r\nTime complexity = nlogk\r\nwhere k is the number of lists and n is number of elements across all lists.","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<unordered_map>\n#include<vector>\nusing namespace std;\n\nvector<int>mergeKSortedLists(vector<vector<int>>&lists) {\n vector<int> rv;\n //write your code here\n return rv;\n}\n\nint main() {\n int k;\n cin >> k;\n vector<vector<int>>lists;\n for (int i = 0; i < k; i++) {\n vector<int>list;\n\n int n;\n cin >> n;\n for (int j = 0; j < n; j++) {\n int data;\n cin >> data;\n list.push_back(data);\n }\n\n lists.push_back(list);\n }\n\n vector<int> mlist = mergeKSortedLists(lists);\n for (int val : mlist) {\n cout << val << \" \";\n }\n cout <<endl;\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static ArrayList<Integer> mergeKSortedLists(ArrayList<ArrayList<Integer>> lists){\r\n ArrayList<Integer> rv = new ArrayList<>();\r\n\r\n // write your code here\r\n\r\n return rv;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int k = Integer.parseInt(br.readLine());\r\n ArrayList<ArrayList<Integer>> lists = new ArrayList<>();\r\n for(int i = 0; i < k; i++){\r\n ArrayList<Integer> list = new ArrayList<>();\r\n\r\n int n = Integer.parseInt(br.readLine());\r\n String[] elements = br.readLine().split(\" \");\r\n for(int j = 0; j < n; j++){\r\n list.add(Integer.parseInt(elements[j]));\r\n }\r\n\r\n lists.add(list);\r\n }\r\n\r\n ArrayList<Integer> mlist = mergeKSortedLists(lists);\r\n for(int val: mlist){\r\n System.out.print(val + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n}"},"python":{"code":"class PriorityQueue(object):\n def __init__(self):\n self.queue = []\n\n def __str__(self):\n return ' '.join([str(i) for i in self.queue])\n\n def isEmpty(self):\n return len(self.queue) == 0\n\n def insert(self, data):\n self.queue.append(data)\n\n def delete(self):\n try:\n max = 0\n for i in range(len(self.queue)):\n if self.queue[i] > self.queue[max]:\n max = i\n item = self.queue[max]\n del self.queue[max]\n return item\n except IndexError:\n print()\n exit()\n\nif __name__ == '__main__':\n k=int(input())\n arr=[]\n for i in range(k):\n n=int(input())\n row=input().split()\n for i in range(len(row)):\n row[i]=int(row[i])\n arr.append(row) "}},"points":10,"difficulty":"hard","sampleInput":"4\r\n5\r\n10 20 30 40 50\r\n7\r\n5 7 9 11 19 55 57\r\n3\r\n1 2 3\r\n2\r\n32 39","sampleOutput":"1 2 3 5 7 9 10 11 19 20 30 32 39 40 50 55 57 \r\n","questionVideo":"https://www.youtube.com/embed/k_3hDj23DuE","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1254d21e-2209-40bc-9e24-00d135ace68d","name":"Hashmap And Heap For Beginners","slug":"hashmap-and-heap-for-beginners","type":0},{"id":"76d281b2-8483-4206-83c4-39be05f4fa12","name":"Merge K Sorted Lists","slug":"merge-k-sorted-lists","type":1}],"next":{"id":"c9f81383-af18-49bf-b9d8-fed22f7eabea","name":"Merge K sorted lists","type":3,"slug":"merge-k-sorted-lists"},"prev":{"id":"fb8928a4-b4cc-4c8e-8e00-2c098fcbda2f","name":"Median Priority Queue","type":3,"slug":"median-priority-queue"}}}

Merge K Sorted Lists

1. You are given a list of lists, where each list is sorted. 2. You are required to complete the body of mergeKSortedLists function. The function is expected to merge k sorted lists to create one sorted list.

{"id":"e499a21a-0681-4c9b-99de-2bb6231939e7","name":"Merge K Sorted Lists","description":"1. You are given a list of lists, where each list is sorted.\r\n2. You are required to complete the body of mergeKSortedLists function. The function is expected to merge k sorted lists to create one sorted list.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"Space complextiy = O(k)\r\nTime complexity = nlogk\r\nwhere k is the number of lists and n is number of elements across all lists.","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<unordered_map>\n#include<vector>\nusing namespace std;\n\nvector<int>mergeKSortedLists(vector<vector<int>>&lists) {\n vector<int> rv;\n //write your code here\n return rv;\n}\n\nint main() {\n int k;\n cin >> k;\n vector<vector<int>>lists;\n for (int i = 0; i < k; i++) {\n vector<int>list;\n\n int n;\n cin >> n;\n for (int j = 0; j < n; j++) {\n int data;\n cin >> data;\n list.push_back(data);\n }\n\n lists.push_back(list);\n }\n\n vector<int> mlist = mergeKSortedLists(lists);\n for (int val : mlist) {\n cout << val << \" \";\n }\n cout <<endl;\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static ArrayList<Integer> mergeKSortedLists(ArrayList<ArrayList<Integer>> lists){\r\n ArrayList<Integer> rv = new ArrayList<>();\r\n\r\n // write your code here\r\n\r\n return rv;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int k = Integer.parseInt(br.readLine());\r\n ArrayList<ArrayList<Integer>> lists = new ArrayList<>();\r\n for(int i = 0; i < k; i++){\r\n ArrayList<Integer> list = new ArrayList<>();\r\n\r\n int n = Integer.parseInt(br.readLine());\r\n String[] elements = br.readLine().split(\" \");\r\n for(int j = 0; j < n; j++){\r\n list.add(Integer.parseInt(elements[j]));\r\n }\r\n\r\n lists.add(list);\r\n }\r\n\r\n ArrayList<Integer> mlist = mergeKSortedLists(lists);\r\n for(int val: mlist){\r\n System.out.print(val + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n}"},"python":{"code":"class PriorityQueue(object):\n def __init__(self):\n self.queue = []\n\n def __str__(self):\n return ' '.join([str(i) for i in self.queue])\n\n def isEmpty(self):\n return len(self.queue) == 0\n\n def insert(self, data):\n self.queue.append(data)\n\n def delete(self):\n try:\n max = 0\n for i in range(len(self.queue)):\n if self.queue[i] > self.queue[max]:\n max = i\n item = self.queue[max]\n del self.queue[max]\n return item\n except IndexError:\n print()\n exit()\n\nif __name__ == '__main__':\n k=int(input())\n arr=[]\n for i in range(k):\n n=int(input())\n row=input().split()\n for i in range(len(row)):\n row[i]=int(row[i])\n arr.append(row) "}},"points":10,"difficulty":"hard","sampleInput":"4\r\n5\r\n10 20 30 40 50\r\n7\r\n5 7 9 11 19 55 57\r\n3\r\n1 2 3\r\n2\r\n32 39","sampleOutput":"1 2 3 5 7 9 10 11 19 20 30 32 39 40 50 55 57 \r\n","questionVideo":"https://www.youtube.com/embed/k_3hDj23DuE","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1254d21e-2209-40bc-9e24-00d135ace68d","name":"Hashmap And Heap For Beginners","slug":"hashmap-and-heap-for-beginners","type":0},{"id":"76d281b2-8483-4206-83c4-39be05f4fa12","name":"Merge K Sorted Lists","slug":"merge-k-sorted-lists","type":1}],"next":{"id":"c9f81383-af18-49bf-b9d8-fed22f7eabea","name":"Merge K sorted lists","type":3,"slug":"merge-k-sorted-lists"},"prev":{"id":"fb8928a4-b4cc-4c8e-8e00-2c098fcbda2f","name":"Median Priority Queue","type":3,"slug":"median-priority-queue"}}}
plane

Editor

Loading...

Merge K Sorted Lists

hard

1. You are given a list of lists, where each list is sorted. 2. You are required to complete the body of mergeKSortedLists function. The function is expected to merge k sorted lists to create one sorted list.

Constraints

Space complextiy = O(k) Time complexity = nlogk where k is the number of lists and n is number of elements across all lists.

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

4 5 10 20 30 40 50 7 5 7 9 11 19 55 57 3 1 2 3 2 32 39

Sample Output

1 2 3 5 7 9 10 11 19 20 30 32 39 40 50 55 57

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode