2583. Kth Largest Sum in a Binary Tree (#184)

remy727 · web-flow · commit 6ba9c981d827 · 2024-10-22T11:45:05.000+02:00
diff --git a/README.md b/README.md
@@ -493,6 +493,7 @@
 | 2492 | Minimum Score of a Path Between Two Cities | [Ruby](./algorithms/ruby/2492-minimum-score-of-a-path-between-two-cities.rb) | Medium |
 | 2542 | Maximum Subsequence Score | [Ruby](./algorithms/ruby/2542-maximum-subsequence-score.rb) | Medium |
 | 2551 | Put Marbles in Bags | [Ruby](./algorithms/ruby/2551-put-marbles-in-bags.rb) | Hard |
+| 2583 | Kth Largest Sum in a Binary Tree | [Ruby](./algorithms/ruby/2583-kth-largest-sum-in-a-binary-tree.rb) | Medium |
 | 2595 | Number of Even and Odd Bits | [Ruby](./algorithms/ruby/2595-number-of-even-and-odd-bits.rb) | Easy |
 | 2616 | Minimize the Maximum Difference of Pairs | [Ruby](./algorithms/ruby/2616-minimize-the-maximum-difference-of-pairs.rb) | Medium |
 | 2642 | Design Graph With Shortest Path Calculator | [Ruby](./algorithms/ruby/2642-design-graph-with-shortest-path-calculator.rb) | Hard |
diff --git a/algorithms/ruby/2583-kth-largest-sum-in-a-binary-tree.rb b/algorithms/ruby/2583-kth-largest-sum-in-a-binary-tree.rb
@@ -0,0 +1,71 @@
+# frozen_string_literal: true
+
+# 2583. Kth Largest Sum in a Binary Tree
+# Medium
+# https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree
+
+=begin
+You are given the root of a binary tree and a positive integer k.
+The level sum in the tree is the sum of the values of the nodes that are on the same level.
+Return the kth largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.
+Note that two nodes are on the same level if they have the same distance from the root.
+
+Example 1:
+Input: root = [5,8,9,2,1,3,7,4,6], k = 2
+Output: 13
+Explanation: The level sums are the following:
+- Level 1: 5.
+- Level 2: 8 + 9 = 17.
+- Level 3: 2 + 1 + 3 + 7 = 13.
+- Level 4: 4 + 6 = 10.
+The 2nd largest level sum is 13.
+
+Example 2:
+Input: root = [1,2,null,3], k = 1
+Output: 3
+Explanation: The largest level sum is 3.
+
+Constraints:
+* The number of nodes in the tree is n.
+* 2 <= n <= 105
+* 1 <= Node.val <= 106
+* 1 <= k <= n
+=end
+
+# Definition for a binary tree node.
+# class TreeNode
+#     attr_accessor :val, :left, :right
+#     def initialize(val = 0, left = nil, right = nil)
+#         @val = val
+#         @left = left
+#         @right = right
+#     end
+# end
+# @param {TreeNode} root
+# @param {Integer} k
+# @return {Integer}
+def kth_largest_level_sum(root, k)
+  return -1 if root.nil?
+
+  sums = []
+  queue = [root]
+
+  while !queue.empty?
+    lvl_sum = 0
+    size = queue.size
+
+    size.times do
+      node = queue.shift
+      lvl_sum += node.val
+
+      queue << node.left if node.left
+      queue << node.right if node.right
+    end
+
+    sums << lvl_sum
+  end
+
+  return -1 if k > sums.size
+
+  sums.sort.reverse[k - 1]
+end
