Given an array arr[][] consisting of N lists representing N transactions, the task is to merge the given lists of transactions in the order of their occurrences, such that at any point of time, the sum of already performed transactions is non-negative. If found to negative, then print “-1”. Otherwise, print the merged list of transactions.
Examples:
Input: arr[][] = {{100 ? 400 ? -1000 ? -500}, {-300 ? 2000 ? -500}}
Output: 100 ? 400 ? -300 ? 2000 ? -500 ? -1000 ? -500
Explanation: The sum at every instant of the above list of transactions is given by {100, 500, 200, 2200, 1700, 700, 200}, which has no negative values.Input: arr[][] = [[100 ? 400]]
Output: 100 400
Approach: The given problem can be visualized as a variation of merge K-sorted linked lists with criteria that the sum of the merged list of transactions at any instant should be non-negative.
Follow the steps below to solve the problem:
- Initialize a new node, say P, that denotes the head of the constructed Linked List.
- Initialize a priority queue, say PQ, of size N to implement a Max Heap.
- Insert the first N transactions as nodes into PQ.
- Iterate until PQ is non-empty and perform the following steps:
- Pop the top node of the priority queue and insert that node at the end of the list, having head P.
- If the next node of the popped node exists, then insert the next node of the popped node in PQ.
- After completing the above steps, print the linked list formed having head P.
Below is the implementation of the above approach:-
C++
// C++ code for the above approach#include <iostream>#include <queue>#include <vector>using namespace std;// Structure of a Node in the linked liststruct Node { int val; Node* next; Node(int val) : val(val) , next(NULL) { }};struct Compare { bool operator()(Node* a, Node* b) { return a->val < b->val; }};// Function to merge the Bank sheetsvoid mergeSheets(vector<Node*>& lists){ // Initialize Max_Heap priority_queue<Node*, vector<Node*>, Compare> pq; // Insert the first element of each list for (int i = 0; i < lists.size(); i++) { // If list is not NULL if (lists[i]) { // Insert element in the priority queue pq.push(lists[i]); } } // Stores the output list Node* head = new Node(0); Node* curr = head; // Iterate until PQ is non-empty while (!pq.empty()) { auto t = pq.top(); pq.pop(); curr->next = t; curr = curr->next; if (curr->next) { pq.push(curr->next); } } curr = head->next; // Print the output list while (curr->next) { cout << curr->val << " "; curr = curr->next; } cout << curr->val << endl;}int main(){ int N = 2; vector<Node*> lists(N); lists[0] = new Node(100); lists[0]->next = new Node(400); lists[0]->next->next = new Node(-1000); lists[0]->next->next->next = new Node(-500); lists[1] = new Node(-300); lists[1]->next = new Node(2000); lists[1]->next->next = new Node(-500); // Function call mergeSheets(lists); return 0;} |
Java
// Java program for the above approachimport java.util.*;// Structure of a Node// in the Linked Listclass Node { int val; Node next; // Constructor Node(int val) { this.val = val; this.next = null; }}class GFG { // Function to merge the Bank sheets public static void mergeSheets( Node lists[]) { // Initialize Max_Heap PriorityQueue<Node> pq = new PriorityQueue<>( new Comparator<Node>() { // Comparator Function // to make it maxHeap public int compare(Node a, Node b) { return b.val - a.val; } }); // Stores the output list Node p, head = new Node(0); p = head; // Insert the first element // of each list for (int i = 0; i < lists.length; i++) { // If the list is not NULL if (lists[i] != null) { // Insert element in // the priority queue pq.add(lists[i]); } } // Iterate until PQ is non-empty while (!pq.isEmpty()) { p.next = pq.poll(); p = p.next; if (p.next != null) pq.add(p.next); } p = head.next; // Print the output list while (p.next != null) { System.out.print(p.val + " "); p = p.next; } System.out.print(p.val); } // Driver Code public static void main(String[] args) { int N = 2; Node arr[] = new Node[N]; arr[0] = new Node(100); arr[0].next = new Node(400); arr[0].next.next = new Node(-1000); arr[0].next.next.next = new Node(-500); arr[1] = new Node(-300); arr[1].next = new Node(2000); arr[1].next.next = new Node(-500); // Function Call mergeSheets(arr); }} |
Python3
# Python code for the above approachimport heapq# Structure of a Node in the Linked Listclass Node: def __init__(self, val): self.val = val self.next = None# Function to merge the Bank sheetsdef mergeSheets(lists): # Initialize Max_Heap pq = [] # Insert the first element of each list for i in range(len(lists)): # If list is not NULL if lists[i] != None: # Insert element in the priority queue heapq.heappush(pq, (-lists[i].val, lists[i])) # Stores the output list p = Node(0) head = p # Iterate until PQ is non-empty while len(pq) > 0: p.next = heapq.heappop(pq)[1] p = p.next if p.next != None: heapq.heappush(pq, (-p.next.val, p.next)) p = head.next # Print the output list while p.next != None: print(p.val, end=" ") p = p.next print(p.val)# Driver codeN = 2lists = [None]*Nlists[0] = Node(100)lists[0].next = Node(400)lists[0].next.next = Node(-1000)lists[0].next.next.next = Node(-500)lists[1] = Node(-300)lists[1].next = Node(2000)lists[1].next.next = Node(-500)# Function CallmergeSheets(lists)# This code is contributed by lokeshpotta20. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class Node{ public int val; public Node next; public Node(int val) { this.val = val; this.next = null; }}class Program{ public static Node MergeSheets(List<Node> lists) { // Initialize Max_Heap var pq = new List<Node>(); // Insert the first element of each list for (int i = 0; i < lists.Count; i++) { // If list is not NULL if (lists[i] != null) { // Insert element in the priority queue pq.Add(lists[i]); } } // Sort the pq pq.Sort((a, b) => b.val.CompareTo(a.val)); // Stores the output list Node head = new Node(0); Node p = head; // Iterate until PQ is non-empty while (pq.Count > 0) { p.next = pq[0]; pq.RemoveAt(0); p = p.next; if (p.next != null) { pq.Add(p.next); pq.Sort((a, b) => b.val.CompareTo(a.val)); } } return head.next; } public static void Main() { int N = 2; var lists = new List<Node>(); lists.Add(null); lists.Add(null); lists[0] = new Node(100); lists[0].next = new Node(400); lists[0].next.next = new Node(-1000); lists[0].next.next.next = new Node(-500); lists[1] = new Node(-300); lists[1].next = new Node(2000); lists[1].next.next = new Node(-500); // Function Call Node p = MergeSheets(lists); // Print the output list while (p.next != null) { Console.Write(p.val + " "); p = p.next; } Console.Write(p.val); }}//This code is contributed by shivamsharma215 |
Javascript
// JavaScript program for the above approach// Structure of a Node// in the Linked Listclass Node { constructor(val) { this.val = val; this.next = null; }}function mergeSheets(lists) { // Initialize Max_Heap const pq = new PriorityQueue((a, b) => b.val - a.val); // Stores the output list let p, head = new Node(0); p = head; // Insert the first element // of each list for (let i = 0; i < lists.length; i++) { // If the list is not NULL if (lists[i] !== null) { // Insert element in the priority queue pq.enqueue(lists[i]); } } // Iterate until PQ is non-empty while (!pq.isEmpty()) { p.next = pq.dequeue(); p = p.next; if (p.next !== null) { pq.enqueue(p.next); } } p = head.next; // Print the output list let result = ""; while (p.next !== null) { result += p.val + " "; p = p.next; } result += p.val; console.log(result);}// Priority Queue implementationclass PriorityQueue { constructor(comparator) { this.comparator = comparator; this.queue = []; } enqueue(item) { this.queue.push(item); this.queue.sort(this.comparator); } dequeue() { return this.queue.shift(); } isEmpty() { return this.queue.length === 0; }}// Driver Codefunction main() { const N = 2; const arr = new Array(N); arr[0] = new Node(100); arr[0].next = new Node(400); arr[0].next.next = new Node(-1000); arr[0].next.next.next = new Node(-500); arr[1] = new Node(-300); arr[1].next = new Node(2000); arr[1].next.next = new Node(-500); // Function Call mergeSheets(arr);}main();//This code is contributed by chinmaya121221 |
Output:
100 400 -300 2000 -500 -1000 -500
Time Complexity: O(N * log K)
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
