logo

TechCodeview

Kleinster Bereich mit Elementen aus k sortierten Listen

Probieren Sie es bei GfG Practice aus ' title=

Gegeben sei ein 2D-Integer-Array arr[][] der Ordnung k * n wo jede Zeile ist sortiert in aufsteigender Reihenfolge. Ihre Aufgabe besteht darin, den kleinsten Bereich zu finden, der mindestens ein Element aus jedem der Elemente enthält  K  Listen. Wenn mehr als ein solcher Bereich gefunden wird, geben Sie den ersten zurück.

Beispiele:  



Eingang: arr[][] = [[ 4 7 9 12 15 ]
[0 8 10 14 20]
[6 12 16 30 50 ]]
Ausgabe: 6 8
Erläuterung: Der kleinste Bereich wird durch die Nummer 7 aus der ersten Liste, 8 aus der zweiten Liste und 6 aus der dritten Liste gebildet.

Eingang: arr[][] = [[ 2 4 ]
[1 7]
[20 40]]
Ausgabe: 4 20
Erläuterung: Der Bereich [4 20] enthält 4 7 20, der Elemente aus allen drei Arrays enthält.

Inhaltsverzeichnis



[Naiver Ansatz] – Verwendung von K-Zeigern – O(n k^2) Zeit und O(k) Raum

Die Idee besteht darin, für jede Liste, beginnend bei Index 0, einen k-Zeiger beizubehalten. Nehmen Sie bei jedem Schritt den min. und max der aktuellen K-Elemente, um einen Bereich zu bilden. Zu Minimieren Sie die Reichweite wir müssen Erhöhen Sie den Mindestwert da wir das Maximum nicht verringern können (alle Zeiger beginnen bei 0). Bewegen Sie also den Zeiger der Liste, die das enthält aktuelles Minimum und aktualisieren Sie den Bereich. Wiederholen, bis eine Liste erschöpft ist.

Schritt-für-Schritt-Implementierung:

  • Erstellen Sie eine Liste mit Zeigern eine für jede Eingabeliste, alle beginnend bei Index 0.
  • Wiederholen Sie den Vorgang bis einer der Zeiger das Ende seiner Liste erreicht.
  • Bei jedem Schritt Wählen Sie die aktuellen Elemente aus von allen Zeigern angezeigt.
  • Finden Sie die Minimum und Maximum unter diesen Elementen.
  • Berechnen Sie die Reichweite unter Verwendung der Min- und Max-Werte.
  • Wenn dieser Bereich kleiner ist als die vorherige beste Aktualisierung der Antwort.
  • Bewegen Sie den Zeiger nach vorne der Liste, die das minimale Element hatte.
  • Hören Sie auf, wenn eine Liste erschöpft ist und geben Sie den besten gefundenen Bereich zurück.
C++ 
// C++ program to find the smallest range // that includes at least one element from // each of the k sorted lists using k pointers #include    #include  #include  using namespace std; vector<int> findSmallestRange(vector<vector<int>>& arr) {    int k = arr.size();   int n = arr[0].size();   // Pointers for each of the k rows  vector<int> ptr(k 0);  int minRange = INT_MAX;  int start = -1 end = -1;  while (true) {  int minVal = INT_MAX;  int maxVal = INT_MIN;  int minRow = -1;  // Traverse all k rows to get current min and max  for (int i = 0; i < k; i++) {  // If any list is exhausted stop the loop  if (ptr[i] == n) {  return {start end};  }  // Track min value and its row index  if (arr[i][ptr[i]] < minVal) {  minVal = arr[i][ptr[i]];  minRow = i;  }  // Track current max value  if (arr[i][ptr[i]] > maxVal) {  maxVal = arr[i][ptr[i]];  }  }  // Update the result range if a   // smaller range is found  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  start = minVal;  end = maxVal;  }  // Move the pointer of the   // row with minimum value  ptr[minRow]++;  }  return {start end}; } int main() {  vector<vector<int>> arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  vector<int> res = findSmallestRange(arr);  cout << res[0] << ' ' << res[1];  return 0; }
Java 
// Java program to find the smallest range import java.util.*; class GfG{  static ArrayList<Integer> findSmallestRange(int[][] arr) {  int k = arr.length;  int n = arr[0].length;  // Pointers for each of the k rows  int[] ptr = new int[k];  int minRange = Integer.MAX_VALUE;  int start = -1 end = -1;  while (true) {  int minVal = Integer.MAX_VALUE;  int maxVal = Integer.MIN_VALUE;  int minRow = -1;  // Traverse all k rows to get current min and max  for (int i = 0; i < k; i++) {  // If any list is exhausted stop the loop  if (ptr[i] == n) {  ArrayList<Integer> result = new ArrayList<>();  result.add(start);  result.add(end);  return result;  }  // Track min value and its row index  if (arr[i][ptr[i]] < minVal) {  minVal = arr[i][ptr[i]];  minRow = i;  }  // Track current max value  if (arr[i][ptr[i]] > maxVal) {  maxVal = arr[i][ptr[i]];  }  }  // Update the result range if a smaller range is found  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  start = minVal;  end = maxVal;  }  // Move the pointer of the row with minimum value  ptr[minRow]++;  }  }  public static void main(String[] args) {  int[][] arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  ArrayList<Integer> res = findSmallestRange(arr);  System.out.println(res.get(0) + ' ' + res.get(1));  } }
Python 
# Python program to find the smallest range def findSmallestRange(arr): k = len(arr) n = len(arr[0]) # Pointers for each of the k rows ptr = [0] * k min_range = float('inf') start = -1 end = -1 while True: min_val = float('inf') max_val = float('-inf') min_row = -1 # Traverse all k rows to get current min and max for i in range(k): # If any list is exhausted stop the loop if ptr[i] == n: return [start end] # Track min value and its row index if arr[i][ptr[i]] < min_val: min_val = arr[i][ptr[i]] min_row = i # Track current max value if arr[i][ptr[i]] > max_val: max_val = arr[i][ptr[i]] # Update the result range if a smaller range is found if max_val - min_val < min_range: min_range = max_val - min_val start = min_val end = max_val # Move the pointer of the row with minimum value ptr[min_row] += 1 if __name__ == '__main__': arr = [ [4 7 9 12 15] [0 8 10 14 20] [6 12 16 30 50] ] res = findSmallestRange(arr) print(res[0] res[1])
C# 
using System; using System.Collections.Generic; class GfG{  static List<int> findSmallestRange(int[] arr) {  int k = arr.GetLength(0);  int n = arr.GetLength(1);  // Pointers for each of the k rows  int[] ptr = new int[k];   int minRange = int.MaxValue;  int start = -1 end = -1;  while (true) {  int minVal = int.MaxValue;  int maxVal = int.MinValue;  int minRow = -1;  // Traverse all k rows to get current min and max  for (int i = 0; i < k; i++) {  // If any list is exhausted stop the loop  if (ptr[i] == n) {  return new List<int> { start end };  }  int current = arr[i ptr[i]];  if (current < minVal) {  minVal = current;  minRow = i;  }  if (current > maxVal) {  maxVal = current;  }  }  // Update the result range if a smaller range is found  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  start = minVal;  end = maxVal;  }  // Move the pointer of the row with minimum value  ptr[minRow]++;  }  }  public static void Main(string[] args) {  int[] arr = {  { 4 7 9 12 15 }  { 0 8 10 14 20 }  { 6 12 16 30 50 }  };  List<int> res = findSmallestRange(arr);  Console.WriteLine(res[0] + ' ' + res[1]);  } }
JavaScript 
// JavaScript program to find the smallest range function findSmallestRange(arr) {  let k = arr.length;  let n = arr[0].length;  // Pointers for each of the k rows  let ptr = new Array(k).fill(0);  let minRange = Infinity;  let start = -1 end = -1;  while (true) {  let minVal = Infinity;  let maxVal = -Infinity;  let minRow = -1;  // Traverse all k rows to get current min and max  for (let i = 0; i < k; i++) {  // If any list is exhausted stop the loop  if (ptr[i] === n) {  return [start end];  }  // Track min value and its row index  if (arr[i][ptr[i]] < minVal) {  minVal = arr[i][ptr[i]];  minRow = i;  }  // Track current max value  if (arr[i][ptr[i]] > maxVal) {  maxVal = arr[i][ptr[i]];  }  }  // Update the result range if a smaller range is found  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  start = minVal;  end = maxVal;  }  // Move the pointer of the row with minimum value  ptr[minRow]++;  } } const arr = [  [4 7 9 12 15]  [0 8 10 14 20]  [6 12 16 30 50] ]; const res = findSmallestRange(arr); console.log(res[0] + ' ' + res[1]);

Ausgabe 
6 8

[Besserer Ansatz] Verwendung von zwei Zeigern – O(n*k log (n*k)) Zeit und O(n*k) Raum

Die Idee besteht darin, das Problem des kleinsten Bereichs zu finden, indem es in ein Schiebefensterproblem über einer zusammengeführten und sortierten Liste aller Elemente aus den Eingabelisten umgewandelt wird. Jedes Element wird zusammen mit seinem ursprünglichen Listenindex gespeichert, um seine Quelle zu verfolgen. Nach dem Sortieren der kombinierten Liste nach Wert zwei Zeiger (leftUndright) werden verwendet, um ein Fenster zu definieren, das sich durch die Liste bewegt. Während sich das Fenster vergrößert, verfolgt eine Häufigkeitskarte, wie viele eindeutige Listen dargestellt werden. Wenn das Fenster mindestens eine Zahl aus jeder Liste enthält, versucht der Algorithmus, es von links her zu verkleinern, um einen kleineren gültigen Bereich zu finden. Als Ergebnis wird der kleinste bei diesem Vorgang gefundene Bereich zurückgegeben.



C++ 
#include    using namespace std; vector<int> findSmallestRange(vector<vector<int>>& arr) {    int k = arr.size();   // Stores the current index for each list  vector<int> pointers(k 0);  // Stores the current smallest range  vector<int> smallestRange = {0 INT_MAX};  while (true) {  int currentMin = INT_MAX currentMax = INT_MIN;  int minListIndex = -1;  // Find the minimum and maximum among current elements of all lists  for (int i = 0; i < k; i++) {  int value = arr[i][pointers[i]];  if (value < currentMin) {  currentMin = value;  minListIndex = i;  }  if (value > currentMax) {  currentMax = value;  }  }  // Update the smallest range if this one is smaller  if (currentMax - currentMin < smallestRange[1] - smallestRange[0]) {  smallestRange[0] = currentMin;  smallestRange[1] = currentMax;  }  // Move the pointer in the list that had the minimum value  pointers[minListIndex]++;  // If that list is exhausted break the loop  if (pointers[minListIndex] == arr[minListIndex].size()) break;  }  return smallestRange; } // Driver code int main() {  vector<vector<int>> arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  vector<int> result = findSmallestRange(arr);  cout << result[0] << ' ' << result[1];  return 0; }
Java 
import java.util.*; class GfG {  // Function to find the smallest range  public static ArrayList<Integer> findSmallestRange(int[][] arr) {  int k = arr.length; // Number of lists  // Stores the current index for each list  int[] pointers = new int[k];  // Stores the current smallest range  ArrayList<Integer> smallestRange = new ArrayList<>  (Arrays.asList(0 Integer.MAX_VALUE));  // Continue the loop until one list is exhausted  while (true) {  int currentMin = Integer.MAX_VALUE currentMax = Integer.MIN_VALUE;  int minListIndex = -1;  // Find the minimum and maximum among current elements of all lists  for (int i = 0; i < k; i++) {  int value = arr[i][pointers[i]];  // Update the current minimum  if (value < currentMin) {  currentMin = value;  minListIndex = i;  }  // Update the current maximum  if (value > currentMax) {  currentMax = value;  }  }  // Update the smallest range if this one is smaller  if (currentMax - currentMin < smallestRange.get(1) - smallestRange.get(0)) {  smallestRange.set(0 currentMin);  smallestRange.set(1 currentMax);  }  // Move the pointer in the list that had the minimum value  pointers[minListIndex]++;  // If that list is exhausted break the loop  if (pointers[minListIndex] == arr[minListIndex].length) break;  }  return smallestRange; // Return the result as ArrayList  }  // Driver code  public static void main(String[] args) {  int[][] arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  ArrayList<Integer> result = findSmallestRange(arr);  System.out.println(result.get(0) + ' ' + result.get(1));  } }
Python 
def findSmallestRange(arr): k = len(arr) # Number of lists # Stores the current index for each list pointers = [0] * k # Stores the current smallest range smallestRange = [0 float('inf')] # Continue the loop until one list is exhausted while True: currentMin = float('inf') currentMax = -float('inf') minListIndex = -1 # Find the minimum and maximum among current elements of all lists for i in range(k): value = arr[i][pointers[i]] # Update the current minimum if value < currentMin: currentMin = value minListIndex = i # Update the current maximum if value > currentMax: currentMax = value # Update the smallest range if this one is smaller if currentMax - currentMin < smallestRange[1] - smallestRange[0]: smallestRange[0] = currentMin smallestRange[1] = currentMax # Move the pointer in the list that had the minimum value pointers[minListIndex] += 1 # If that list is exhausted break the loop if pointers[minListIndex] == len(arr[minListIndex]): break return smallestRange # Return the result as a list # Driver code if __name__ == '__main__': arr = [ [4 7 9 12 15] [0 8 10 14 20] [6 12 16 30 50] ] result = findSmallestRange(arr) print(result[0] result[1])
C# 
using System; using System.Collections.Generic; class GfG{  // Function to find the smallest range  public static List<int> findSmallestRange(int[] arr) {  int k = arr.GetLength(0); // Number of lists (rows)  // Stores the current index for each list (row)  int[] pointers = new int[k];  // Stores the current smallest range  List<int> smallestRange = new List<int> { 0 int.MaxValue };  // Continue the loop until one list is exhausted  while (true) {  int currentMin = int.MaxValue currentMax = int.MinValue;  int minListIndex = -1;  // Find the minimum and maximum among current elements   // of all lists  for (int i = 0; i < k; i++) {  int value = arr[i pointers[i]];  // Update the current minimum  if (value < currentMin) {  currentMin = value;  minListIndex = i;  }  // Update the current maximum  if (value > currentMax) {  currentMax = value;  }  }  // Update the smallest range if this one is smaller  if (currentMax - currentMin < smallestRange[1] - smallestRange[0]) {  smallestRange[0] = currentMin;  smallestRange[1] = currentMax;  }  // Move the pointer in the list that had the minimum value  pointers[minListIndex]++;  // If that list is exhausted break the loop  if (pointers[minListIndex] == arr.GetLength(1)) break;  }  return smallestRange; // Return the result as List    }  // Driver code  public static void Main(string[] args) {  int[] arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  List<int> result = findSmallestRange(arr);  Console.WriteLine(result[0] + ' ' + result[1]);  } }
JavaScript 
function findSmallestRange(arr) {  const k = arr.length; // Number of lists  // Stores the current index for each list  let pointers = new Array(k).fill(0);  // Stores the current smallest range  let smallestRange = [0 Number.MAX_VALUE];  // Continue the loop until one list is exhausted  while (true) {  let currentMin = Number.MAX_VALUE currentMax = -Number.MAX_VALUE;  let minListIndex = -1;  // Find the minimum and maximum among current elements of all lists  for (let i = 0; i < k; i++) {  const value = arr[i][pointers[i]];  // Update the current minimum  if (value < currentMin) {  currentMin = value;  minListIndex = i;  }  // Update the current maximum  if (value > currentMax) {  currentMax = value;  }  }  // Update the smallest range if this one is smaller  if (currentMax - currentMin < smallestRange[1] - smallestRange[0]) {  smallestRange[0] = currentMin;  smallestRange[1] = currentMax;  }  // Move the pointer in the list that had the minimum value  pointers[minListIndex]++;  // If that list is exhausted break the loop  if (pointers[minListIndex] === arr[minListIndex].length) break;  }  return smallestRange; // Return the result as an array } // Driver code const arr = [  [4 7 9 12 15]  [0 8 10 14 20]  [6 12 16 30 50] ]; const result = findSmallestRange(arr); console.log(result[0] result[1]);

Ausgabe 
6 8

[Effizienter Ansatz] – Verwendung von Min Heap – O(n k Log k) Zeit und O(k) Raum

Min-Heap kann verwendet werden, um den Minimalwert in logarithmischer Zeit oder log k-Zeit statt in linearer Zeit zu ermitteln. Um den Maximalwert zu ermitteln, initialisieren wir zunächst den Maximalwert aller 0-Indizes. Für den Rest der Maximalwerte in der Schleife vergleichen wir einfach den aktuellen Maximalwert mit dem nächsten Element aus der Liste, aus dem das Minimalelement entfernt wird. Der Rest des Ansatzes bleibt gleich. 

Schritt-für-Schritt-Implementierung:

  • Min-Heap kann verwendet werden, um den Minimalwert in logarithmischer Zeit oder log k-Zeit statt in linearer Zeit zu ermitteln. Um den Maximalwert zu ermitteln, initialisieren wir zunächst den Maximalwert aller 0-Indizes. Für den Rest der Maximalwerte in der Schleife vergleichen wir einfach den aktuellen Maximalwert mit dem nächsten Element aus der Liste, aus dem das Minimalelement entfernt wird. Der Rest des Ansatzes bleibt gleich. 

    Erstellen Sie einen Min-Heap, um K-Elemente, eines aus jedem Array und eine Variable zu speichern Min. Bereich auf einen Maximalwert initialisiert und auch eine Variable behalten max um die maximale Ganzzahl zu speichern.

  • Min-Heap kann verwendet werden, um den Minimalwert in logarithmischer Zeit oder log k-Zeit statt in linearer Zeit zu ermitteln. Um den Maximalwert zu ermitteln, initialisieren wir zunächst den Maximalwert aller 0-Indizes. Für den Rest der Maximalwerte in der Schleife vergleichen wir einfach den aktuellen Maximalwert mit dem nächsten Element aus der Liste, aus dem das Minimalelement entfernt wird. Der Rest des Ansatzes bleibt gleich. 

    Fügen Sie zunächst das erste Element aus jeder Liste ein und speichern Sie den Maximalwert darin max .

  • Min-Heap kann verwendet werden, um den Minimalwert in logarithmischer Zeit oder log k-Zeit statt in linearer Zeit zu ermitteln. Um den Maximalwert zu ermitteln, initialisieren wir zunächst den Maximalwert aller 0-Indizes. Für den Rest der Maximalwerte in der Schleife vergleichen wir einfach den aktuellen Maximalwert mit dem nächsten Element aus der Liste, aus dem das Minimalelement entfernt wird. Der Rest des Ansatzes bleibt gleich. 

    Wiederholen Sie die folgenden Schritte, bis mindestens eine Liste erschöpft ist: 

    • Finden Sie den Mindestwert oder min Verwenden Sie die Spitze oder Wurzel des Min-Heaps, bei dem es sich um das minimale Element handelt.
    • Aktualisieren Sie nun die Min. Bereich wenn der Strom (max-min) kleiner ist als Min. Bereich .
    • Entfernen Sie das oberste oder Wurzelelement aus der Prioritätswarteschlange und fügen Sie das nächste Element aus der Liste ein, das das Mindestelement enthält
    • Aktualisieren Sie den Maximalwert mit dem neuen eingefügten Element, wenn das neue Element größer als der vorherige Maximalwert ist.
Min-Heap kann verwendet werden, um den Minimalwert in logarithmischer Zeit oder log k-Zeit statt in linearer Zeit zu ermitteln. Um den Maximalwert zu ermitteln, initialisieren wir zunächst den Maximalwert aller 0-Indizes. Für den Rest der Maximalwerte in der Schleife vergleichen wir einfach den aktuellen Maximalwert mit dem nächsten Element aus der Liste, aus dem das Minimalelement entfernt wird. Der Rest des Ansatzes bleibt gleich. 

C++ 

#include    using namespace std; // Struct to represent elements in the heap struct Node {  int val row col;  bool operator>(const Node& other) const {  return val > other.val;  } }; // Function to find the smallest range vector<int> findSmallestRange(vector<vector<int>>& arr) {  int N = arr.size(); // Number of rows  int K = arr[0].size(); // Number of columns (same for each row)  priority_queue<Node vector<Node> greater<Node>> pq;  int maxVal = INT_MIN;  // Push the first element of each list into the min-heap  for (int i = 0; i < N; i++) {  pq.push({arr[i][0] i 0});  maxVal = max(maxVal arr[i][0]);  }  int minRange = INT_MAX minEl maxEl;  while (true) {  Node curr = pq.top(); pq.pop();  int minVal = curr.val;  // Update range if better  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  minEl = minVal;  maxEl = maxVal;  }  // If we've reached the end of a list break  if (curr.col + 1 == K) break;  // Push next element from the same list  int nextVal = arr[curr.row][curr.col + 1];  pq.push({nextVal curr.row curr.col + 1});  maxVal = max(maxVal nextVal);  }  return {minEl maxEl}; } // Driver code int main() {  vector<vector<int>> arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  vector<int> result = findSmallestRange(arr);  cout << result[0] << ' ' << result[1];  return 0; }
Java 
import java.util.*; // Class to represent elements in the heap class Node implements Comparable<Node> {  int val row col;  Node(int val int row int col) {  this.val = val;  this.row = row;  this.col = col;  }  // For min-heap based on value  public int compareTo(Node other) {  return this.val - other.val;  } } class GfG {  // Function to find the smallest range  static ArrayList<Integer> findSmallestRange(int[][] arr) {  int k = arr.length;  int n = arr[0].length;  PriorityQueue<Node> pq = new PriorityQueue<>();  int maxVal = Integer.MIN_VALUE;  // Push the first element of each list into the min-heap  for (int i = 0; i < k; i++) {  pq.add(new Node(arr[i][0] i 0));  maxVal = Math.max(maxVal arr[i][0]);  }  int minRange = Integer.MAX_VALUE minEl = -1 maxEl = -1;  while (true) {  Node curr = pq.poll();  int minVal = curr.val;  // Update range if better  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  minEl = minVal;  maxEl = maxVal;  }  // If we've reached the end of a list break  if (curr.col + 1 == n)  break;  // Push next element from the same list  int nextVal = arr[curr.row][curr.col + 1];  pq.add(new Node(nextVal curr.row curr.col + 1));  maxVal = Math.max(maxVal nextVal);  }  // Return result as ArrayList  ArrayList<Integer> result = new ArrayList<>();  result.add(minEl);  result.add(maxEl);  return result;  }  // Driver code  public static void main(String[] args) {  int[][] arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  ArrayList<Integer> res = findSmallestRange(arr);  System.out.println(res.get(0) + ' ' + res.get(1));  } }
Python 
import heapq # Function to find the smallest range def findSmallestRange(arr): k = len(arr) n = len(arr[0]) heap = [] maxVal = float('-inf') # Push the first element of each  # list into the min-heap for i in range(k): heapq.heappush(heap (arr[i][0] i 0)) maxVal = max(maxVal arr[i][0]) minRange = float('inf') minEl = maxEl = -1 while True: minVal row col = heapq.heappop(heap) # Update range if better if maxVal - minVal < minRange: minRange = maxVal - minVal minEl = minVal maxEl = maxVal # If we've reached the end of a list break if col + 1 == n: break # Push next element from the same list nextVal = arr[row][col + 1] heapq.heappush(heap (nextVal row col + 1)) maxVal = max(maxVal nextVal) return [minEl maxEl] # Driver code if __name__ == '__main__': arr = [ [4 7 9 12 15] [0 8 10 14 20] [6 12 16 30 50] ] res = findSmallestRange(arr) print(res[0] res[1])
C# 
using System; using System.Collections.Generic; // Class to represent elements in the heap class Node : IComparable<Node> {  public int val row col;  public Node(int val int row int col) {  this.val = val;  this.row = row;  this.col = col;  }  // For min-heap based on value  public int CompareTo(Node other) {  if (this.val != other.val)  return this.val.CompareTo(other.val);  // To avoid duplicate keys in SortedSet  if (this.row != other.row)  return this.row.CompareTo(other.row);  return this.col.CompareTo(other.col);  } } class GfG {  // Function to find the smallest range  static List<int> findSmallestRange(int[] arr) {  int k = arr.GetLength(0);  int n = arr.GetLength(1);  var pq = new SortedSet<Node>();  int maxVal = int.MinValue;  // Push the first element of each list into the min-heap  for (int i = 0; i < k; i++) {  var node = new Node(arr[i 0] i 0);  pq.Add(node);  maxVal = Math.Max(maxVal arr[i 0]);  }  int minRange = int.MaxValue minEl = -1 maxEl = -1;  while (true) {  var curr = GetMin(pq);  pq.Remove(curr);  int minVal = curr.val;  // Update range if better  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  minEl = minVal;  maxEl = maxVal;  }  // If we've reached the end of a list break  if (curr.col + 1 == n)  break;  // Push next element from the same list  int nextVal = arr[curr.row curr.col + 1];  var nextNode = new Node(nextVal curr.row curr.col + 1);  pq.Add(nextNode);  maxVal = Math.Max(maxVal nextVal);  }  return new List<int> { minEl maxEl }; // Return result as List    }  // Helper to get the minimum element (first element in SortedSet)  static Node GetMin(SortedSet<Node> pq) {  foreach (var node in pq)  return node;  return null;  }  // Driver code  static void Main() {  int[] arr = {  {4 7 9 12 15}  {0 8 10 14 20}  {6 12 16 30 50}  };  List<int> res = findSmallestRange(arr);  Console.WriteLine(res[0] + ' ' + res[1]);  } }
JavaScript 
class Node {  constructor(val row col) {  this.val = val;  this.row = row;  this.col = col;  } } // Function to find the smallest range function findSmallestRange(arr) {  const k = arr.length;  const n = arr[0].length;  const heap = new MinHeap();  let maxVal = -Infinity;  // Push the first element of each list into the min-heap  for (let i = 0; i < k; i++) {  heap.push(new Node(arr[i][0] i 0));  maxVal = Math.max(maxVal arr[i][0]);  }  let minRange = Infinity;  let minEl = -1 maxEl = -1;  while (true) {  const curr = heap.pop();  const minVal = curr.val;  // Update range if better  if (maxVal - minVal < minRange) {  minRange = maxVal - minVal;  minEl = minVal;  maxEl = maxVal;  }  // If we've reached the end of a list break  if (curr.col + 1 === n) break;  // Push next element from the same list  const nextVal = arr[curr.row][curr.col + 1];  heap.push(new Node(nextVal curr.row curr.col + 1));  maxVal = Math.max(maxVal nextVal);  }  return [minEl maxEl]; } // Min-heap comparator class MinHeap {  constructor() {  this.heap = [];  }  push(node) {  this.heap.push(node);  this._heapifyUp();  }  pop() {  if (this.size() === 1) return this.heap.pop();  const top = this.heap[0];  this.heap[0] = this.heap.pop();  this._heapifyDown();  return top;  }  top() {  return this.heap[0];  }  size() {  return this.heap.length;  }  _heapifyUp() {  let idx = this.size() - 1;  while (idx > 0) {  let parent = Math.floor((idx - 1) / 2);  if (this.heap[parent].val <= this.heap[idx].val) break;  [this.heap[parent] this.heap[idx]] = [this.heap[idx] this.heap[parent]];  idx = parent;  }  }  _heapifyDown() {  let idx = 0;  const n = this.size();  while (true) {  let left = 2 * idx + 1;  let right = 2 * idx + 2;  let smallest = idx;  if (left < n && this.heap[left].val < this.heap[smallest].val) {  smallest = left;  }  if (right < n && this.heap[right].val < this.heap[smallest].val) {  smallest = right;  }  if (smallest === idx) break;  [this.heap[smallest] this.heap[idx]] = [this.heap[idx] this.heap[smallest]];  idx = smallest;  }  } } // Driver code const arr = [  [4 7 9 12 15]  [0 8 10 14 20]  [6 12 16 30 50] ]; const res = findSmallestRange(arr); console.log(res[0] + ' ' + res[1]);

Ausgabe 
6 8