← rocketlawyer / People Operations Generalist
coding_drills / art_EF4KCtCwx9Y
Content
{"kind": "coding_drills", "role_id": "role_1780c0b732874f6cb2152ba6b0fe4db4", "source": "leetcode_graphql", "generated_at": "2026-06-29T16:57:16.800268+00:00", "difficulty_mix": {"Easy": 3, "Medium": 5, "Hard": 2}, "topics_filter": [], "questions": [{"index": 0, "category": "coding_hash_table", "question": "[Easy] LC #13 \u00b7 Roman to Integer \u2014 solve on leetcode.com", "why": "Topic tags: hash-table, math, string. AC rate 66.6%. Open the editor at https://leetcode.com/problems/roman-to-integer/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "roman-to-integer", "frontend_id": "13", "difficulty": "Easy", "ac_rate": 66.6294901822322, "topics": ["hash-table", "math", "string"], "url": "https://leetcode.com/problems/roman-to-integer/", "problem_html": "<p>Roman numerals are represented by seven different symbols: <code>I</code>, <code>V</code>, <code>X</code>, <code>L</code>, <code>C</code>, <code>D</code> and <code>M</code>.</p>\n\n<pre>\n<strong>Symbol</strong> <strong>Value</strong>\nI 1\nV 5\nX 10\nL 50\nC 100\nD 500\nM 1000</pre>\n\n<p>For example, <code>2</code> is written as <code>II</code> in Roman numeral, just two ones added together. <code>12</code> is written as <code>XII</code>, which is simply <code>X + II</code>. The number <code>27</code> is written as <code>XXVII</code>, which is <code>XX + V + II</code>.</p>\n\n<p>Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not <code>IIII</code>. Instead, the number four is written as <code>IV</code>. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as <code>IX</code>. There are six instances where subtraction is used:</p>\n\n<ul>\n\t<li><code>I</code> can be placed before <code>V</code> (5) and <code>X</code> (10) to make 4 and 9. </li>\n\t<li><code>X</code> can be placed before <code>L</code> (50) and <code>C</code> (100) to make 40 and 90. </li>\n\t<li><code>C</code> can be placed before <code>D</code> (500) and <code>M</code> (1000) to make 400 and 900.</li>\n</ul>\n\n<p>Given a roman numeral, convert it to an integer.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> s = "III"\n<strong>Output:</strong> 3\n<strong>Explanation:</strong> III = 3.\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> s = "LVIII"\n<strong>Output:</strong> 58\n<strong>Explanation:</strong> L = 50, V= 5, III = 3.\n</pre>\n\n<p><strong class=\"example\">Example 3:</strong></p>\n\n<pre>\n<strong>Input:</strong> s = "MCMXCIV"\n<strong>Output:</strong> 1994\n<strong>Explanation:</strong> M = 1000, CM = 900, XC = 90 and IV = 4.\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>1 <= s.length <= 15</code></li>\n\t<li><code>s</code> contains only the characters <code>('I', 'V', 'X', 'L', 'C', 'D', 'M')</code>.</li>\n\t<li>It is <strong>guaranteed</strong> that <code>s</code> is a valid roman numeral in the range <code>[1, 3999]</code>.</li>\n</ul>\n", "hints": ["Problem is simpler to solve by working the string from back to front and using a map."]}}, {"index": 1, "category": "coding_math", "question": "[Easy] LC #9 \u00b7 Palindrome Number \u2014 solve on leetcode.com", "why": "Topic tags: math. AC rate 60.6%. Open the editor at https://leetcode.com/problems/palindrome-number/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "palindrome-number", "frontend_id": "9", "difficulty": "Easy", "ac_rate": 60.558116308243, "topics": ["math"], "url": "https://leetcode.com/problems/palindrome-number/", "problem_html": "<p>Given an integer <code>x</code>, return <code>true</code><em> if </em><code>x</code><em> is a </em><span data-keyword=\"palindrome-integer\"><em><strong>palindrome</strong></em></span><em>, and </em><code>false</code><em> otherwise</em>.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> x = 121\n<strong>Output:</strong> true\n<strong>Explanation:</strong> 121 reads as 121 from left to right and from right to left.\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> x = -121\n<strong>Output:</strong> false\n<strong>Explanation:</strong> From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.\n</pre>\n\n<p><strong class=\"example\">Example 3:</strong></p>\n\n<pre>\n<strong>Input:</strong> x = 10\n<strong>Output:</strong> false\n<strong>Explanation:</strong> Reads 01 from right to left. Therefore it is not a palindrome.\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>-2<sup>31</sup> <= x <= 2<sup>31</sup> - 1</code></li>\n</ul>\n\n<p> </p>\n<strong>Follow up:</strong> Could you solve it without converting the integer to a string?", "hints": ["Beware of overflow when you reverse the integer."]}}, {"index": 2, "category": "coding_array", "question": "[Easy] LC #27 \u00b7 Remove Element \u2014 solve on leetcode.com", "why": "Topic tags: array, two-pointers. AC rate 61.8%. Open the editor at https://leetcode.com/problems/remove-element/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "remove-element", "frontend_id": "27", "difficulty": "Easy", "ac_rate": 61.7901135225882, "topics": ["array", "two-pointers"], "url": "https://leetcode.com/problems/remove-element/", "problem_html": "<p>Given an integer array <code>nums</code> and an integer <code>val</code>, remove all occurrences of <code>val</code> in <code>nums</code> <a href=\"https://en.wikipedia.org/wiki/In-place_algorithm\" target=\"_blank\"><strong>in-place</strong></a>. The order of the elements may be changed. Then return <em>the number of elements in </em><code>nums</code><em> which are not equal to </em><code>val</code>.</p>\n\n<p>Consider the number of elements in <code>nums</code> which are not equal to <code>val</code> be <code>k</code>, to get accepted, you need to do the following things:</p>\n\n<ul>\n\t<li>Change the array <code>nums</code> such that the first <code>k</code> elements of <code>nums</code> contain the elements which are not equal to <code>val</code>. The remaining elements of <code>nums</code> are not important as well as the size of <code>nums</code>.</li>\n\t<li>Return <code>k</code>.</li>\n</ul>\n\n<p><strong>Custom Judge:</strong></p>\n\n<p>The judge will test your solution with the following code:</p>\n\n<pre>\nint[] nums = [...]; // Input array\nint val = ...; // Value to remove\nint[] expectedNums = [...]; // The expected answer with correct length.\n // It is sorted with no values equaling val.\n\nint k = removeElement(nums, val); // Calls your implementation\n\nassert k == expectedNums.length;\nsort(nums, 0, k); // Sort the first k elements of nums\nfor (int i = 0; i < actualLength; i++) {\n assert nums[i] == expectedNums[i];\n}\n</pre>\n\n<p>If all assertions pass, then your solution will be <strong>accepted</strong>.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [3,2,2,3], val = 3\n<strong>Output:</strong> 2, nums = [2,2,_,_]\n<strong>Explanation:</strong> Your function should return k = 2, with the first two elements of nums being 2.\nIt does not matter what you leave beyond the returned k (hence they are underscores).\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [0,1,2,2,3,0,4,2], val = 2\n<strong>Output:</strong> 5, nums = [0,1,4,0,3,_,_,_]\n<strong>Explanation:</strong> Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.\nNote that the five elements can be returned in any order.\nIt does not matter what you leave beyond the returned k (hence they are underscores).\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>0 <= nums.length <= 100</code></li>\n\t<li><code>0 <= nums[i] <= 50</code></li>\n\t<li><code>0 <= val <= 100</code></li>\n</ul>\n", "hints": ["The problem statement clearly asks us to modify the array in-place and it also says that the element beyond the new length of the array can be anything. Given an element, we need to remove all the occurrences of it from the array. We don't technically need to <b>remove</b> that element per se, right?", "We can move all the occurrences of this element to the end of the array. Use two pointers!\r\n<br><img src=\"https://assets.leetcode.com/uploads/2019/10/20/hint_remove_element.png\" width=\"500\"/>", "Yet another direction of thought is to consider the elements to be removed as non-existent. In a single pass, if we keep copying the visible elements in-place, that should also solve this problem for us."]}}, {"index": 3, "category": "coding_linked_list", "question": "[Medium] LC #24 \u00b7 Swap Nodes in Pairs \u2014 solve on leetcode.com", "why": "Topic tags: linked-list, recursion. AC rate 69.5%. Open the editor at https://leetcode.com/problems/swap-nodes-in-pairs/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "swap-nodes-in-pairs", "frontend_id": "24", "difficulty": "Medium", "ac_rate": 69.51098943979446, "topics": ["linked-list", "recursion"], "url": "https://leetcode.com/problems/swap-nodes-in-pairs/", "problem_html": "<p>Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<div class=\"example-block\">\n<p><strong>Input:</strong> <span class=\"example-io\">head = [1,2,3,4]</span></p>\n\n<p><strong>Output:</strong> <span class=\"example-io\">[2,1,4,3]</span></p>\n\n<p><strong>Explanation:</strong></p>\n\n<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg\" style=\"width: 422px; height: 222px;\" /></p>\n</div>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<div class=\"example-block\">\n<p><strong>Input:</strong> <span class=\"example-io\">head = []</span></p>\n\n<p><strong>Output:</strong> <span class=\"example-io\">[]</span></p>\n</div>\n\n<p><strong class=\"example\">Example 3:</strong></p>\n\n<div class=\"example-block\">\n<p><strong>Input:</strong> <span class=\"example-io\">head = [1]</span></p>\n\n<p><strong>Output:</strong> <span class=\"example-io\">[1]</span></p>\n</div>\n\n<p><strong class=\"example\">Example 4:</strong></p>\n\n<div class=\"example-block\">\n<p><strong>Input:</strong> <span class=\"example-io\">head = [1,2,3]</span></p>\n\n<p><strong>Output:</strong> <span class=\"example-io\">[2,1,3]</span></p>\n</div>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li>The number of nodes in the list is in the range <code>[0, 100]</code>.</li>\n\t<li><code>0 <= Node.val <= 100</code></li>\n</ul>\n", "hints": []}}, {"index": 4, "category": "coding_array", "question": "[Medium] LC #33 \u00b7 Search in Rotated Sorted Array \u2014 solve on leetcode.com", "why": "Topic tags: array, binary-search. AC rate 44.5%. Open the editor at https://leetcode.com/problems/search-in-rotated-sorted-array/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "search-in-rotated-sorted-array", "frontend_id": "33", "difficulty": "Medium", "ac_rate": 44.5466822595173, "topics": ["array", "binary-search"], "url": "https://leetcode.com/problems/search-in-rotated-sorted-array/", "problem_html": "<p>There is an integer array <code>nums</code> sorted in ascending order (with <strong>distinct</strong> values).</p>\n\n<p>Prior to being passed to your function, <code>nums</code> is <strong>possibly left rotated</strong> at an unknown index <code>k</code> (<code>1 <= k < nums.length</code>) such that the resulting array is <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code> (<strong>0-indexed</strong>). For example, <code>[0,1,2,4,5,6,7]</code> might be left rotated by <code>3</code> indices and become <code>[4,5,6,7,0,1,2]</code>.</p>\n\n<p>Given the array <code>nums</code> <strong>after</strong> the possible rotation and an integer <code>target</code>, return <em>the index of </em><code>target</code><em> if it is in </em><code>nums</code><em>, or </em><code>-1</code><em> if it is not in </em><code>nums</code>.</p>\n\n<p>You must write an algorithm with <code>O(log n)</code> runtime complexity.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n<pre><strong>Input:</strong> nums = [4,5,6,7,0,1,2], target = 0\n<strong>Output:</strong> 4\n</pre><p><strong class=\"example\">Example 2:</strong></p>\n<pre><strong>Input:</strong> nums = [4,5,6,7,0,1,2], target = 3\n<strong>Output:</strong> -1\n</pre><p><strong class=\"example\">Example 3:</strong></p>\n<pre><strong>Input:</strong> nums = [1], target = 0\n<strong>Output:</strong> -1\n</pre>\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>1 <= nums.length <= 5000</code></li>\n\t<li><code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code></li>\n\t<li>All values of <code>nums</code> are <strong>unique</strong>.</li>\n\t<li><code>nums</code> is an ascending array that is possibly rotated.</li>\n\t<li><code>-10<sup>4</sup> <= target <= 10<sup>4</sup></code></li>\n</ul>\n", "hints": []}}, {"index": 5, "category": "coding_array", "question": "[Medium] LC #45 \u00b7 Jump Game II \u2014 solve on leetcode.com", "why": "Topic tags: array, dynamic-programming, greedy. AC rate 42.9%. Open the editor at https://leetcode.com/problems/jump-game-ii/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "jump-game-ii", "frontend_id": "45", "difficulty": "Medium", "ac_rate": 42.87065640212856, "topics": ["array", "dynamic-programming", "greedy"], "url": "https://leetcode.com/problems/jump-game-ii/", "problem_html": "<p>You are given a <strong>0-indexed</strong> array of integers <code>nums</code> of length <code>n</code>. You are initially positioned at index 0.</p>\n\n<p>Each element <code>nums[i]</code> represents the maximum length of a forward jump from index <code>i</code>. In other words, if you are at index <code>i</code>, you can jump to any index <code>(i + j)</code> where:</p>\n\n<ul>\n\t<li><code>0 <= j <= nums[i]</code> and</li>\n\t<li><code>i + j < n</code></li>\n</ul>\n\n<p>Return <em>the minimum number of jumps to reach index </em><code>n - 1</code>. The test cases are generated such that you can reach index <code>n - 1</code>.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [2,3,1,1,4]\n<strong>Output:</strong> 2\n<strong>Explanation:</strong> The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [2,3,0,1,4]\n<strong>Output:</strong> 2\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>1 <= nums.length <= 10<sup>4</sup></code></li>\n\t<li><code>0 <= nums[i] <= 1000</code></li>\n\t<li>It's guaranteed that you can reach <code>nums[n - 1]</code>.</li>\n</ul>\n", "hints": []}}, {"index": 6, "category": "coding_hash_table", "question": "[Medium] LC #3 \u00b7 Longest Substring Without Repeating Characters \u2014 solve on leetcode.com", "why": "Topic tags: hash-table, string, sliding-window. AC rate 39.1%. Open the editor at https://leetcode.com/problems/longest-substring-without-repeating-characters/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "longest-substring-without-repeating-characters", "frontend_id": "3", "difficulty": "Medium", "ac_rate": 39.05112220358377, "topics": ["hash-table", "string", "sliding-window"], "url": "https://leetcode.com/problems/longest-substring-without-repeating-characters/", "problem_html": "<p>Given a string <code>s</code>, find the length of the <strong>longest</strong> <span data-keyword=\"substring-nonempty\"><strong>substring</strong></span> without duplicate characters.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> s = "abcabcbb"\n<strong>Output:</strong> 3\n<strong>Explanation:</strong> The answer is "abc", with the length of 3. Note that <code>"bca"</code> and <code>"cab"</code> are also correct answers.\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> s = "bbbbb"\n<strong>Output:</strong> 1\n<strong>Explanation:</strong> The answer is "b", with the length of 1.\n</pre>\n\n<p><strong class=\"example\">Example 3:</strong></p>\n\n<pre>\n<strong>Input:</strong> s = "pwwkew"\n<strong>Output:</strong> 3\n<strong>Explanation:</strong> The answer is "wke", with the length of 3.\nNotice that the answer must be a substring, "pwke" is a subsequence and not a substring.\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>0 <= s.length <= 5 * 10<sup>4</sup></code></li>\n\t<li><code>s</code> consists of English letters, digits, symbols and spaces.</li>\n</ul>\n", "hints": ["Since maximum string size is at most 26, generate and check all possible substrings with length at most 26."]}}, {"index": 7, "category": "coding_array", "question": "[Medium] LC #15 \u00b7 3Sum \u2014 solve on leetcode.com", "why": "Topic tags: array, two-pointers, sorting. AC rate 39.1%. Open the editor at https://leetcode.com/problems/3sum/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "3sum", "frontend_id": "15", "difficulty": "Medium", "ac_rate": 39.07790477521536, "topics": ["array", "two-pointers", "sorting"], "url": "https://leetcode.com/problems/3sum/", "problem_html": "<p>Given an integer array nums, return all the triplets <code>[nums[i], nums[j], nums[k]]</code> such that <code>i != j</code>, <code>i != k</code>, and <code>j != k</code>, and <code>nums[i] + nums[j] + nums[k] == 0</code>.</p>\n\n<p>Notice that the solution set must not contain duplicate triplets.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [-1,0,1,2,-1,-4]\n<strong>Output:</strong> [[-1,-1,2],[-1,0,1]]\n<strong>Explanation:</strong> \nnums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.\nnums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.\nnums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.\nThe distinct triplets are [-1,0,1] and [-1,-1,2].\nNotice that the order of the output and the order of the triplets does not matter.\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [0,1,1]\n<strong>Output:</strong> []\n<strong>Explanation:</strong> The only possible triplet does not sum up to 0.\n</pre>\n\n<p><strong class=\"example\">Example 3:</strong></p>\n\n<pre>\n<strong>Input:</strong> nums = [0,0,0]\n<strong>Output:</strong> [[0,0,0]]\n<strong>Explanation:</strong> The only possible triplet sums up to 0.\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>3 <= nums.length <= 3000</code></li>\n\t<li><code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code></li>\n</ul>\n", "hints": ["So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!", "For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?", "The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?"]}}, {"index": 8, "category": "coding_array", "question": "[Hard] LC #42 \u00b7 Trapping Rain Water \u2014 solve on leetcode.com", "why": "Topic tags: array, two-pointers, dynamic-programming, stack, monotonic-stack. AC rate 67.3%. Open the editor at https://leetcode.com/problems/trapping-rain-water/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "trapping-rain-water", "frontend_id": "42", "difficulty": "Hard", "ac_rate": 67.34977527551528, "topics": ["array", "two-pointers", "dynamic-programming", "stack", "monotonic-stack"], "url": "https://leetcode.com/problems/trapping-rain-water/", "problem_html": "<p>Given <code>n</code> non-negative integers representing an elevation map where the width of each bar is <code>1</code>, compute how much water it can trap after raining.</p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n<img src=\"https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png\" style=\"width: 412px; height: 161px;\" />\n<pre>\n<strong>Input:</strong> height = [0,1,0,2,1,0,1,3,2,1,2,1]\n<strong>Output:</strong> 6\n<strong>Explanation:</strong> The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> height = [4,2,0,3,2,5]\n<strong>Output:</strong> 9\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>n == height.length</code></li>\n\t<li><code>1 <= n <= 2 * 10<sup>4</sup></code></li>\n\t<li><code>0 <= height[i] <= 10<sup>5</sup></code></li>\n</ul>\n", "hints": []}}, {"index": 9, "category": "coding_linked_list", "question": "[Hard] LC #23 \u00b7 Merge k Sorted Lists \u2014 solve on leetcode.com", "why": "Topic tags: linked-list, divide-and-conquer, heap-priority-queue, merge-sort. AC rate 59.6%. Open the editor at https://leetcode.com/problems/merge-k-sorted-lists/, talk through your approach, then sketch the algorithm here (whiteboard) or write a plain-English solution (typed).", "how_to_prepare": "Clarify constraints, propose a brute-force, refine to an optimal time/space, walk through 2 example inputs (including an edge case), then trace your final code by hand.", "leetcode": {"title_slug": "merge-k-sorted-lists", "frontend_id": "23", "difficulty": "Hard", "ac_rate": 59.55631686860603, "topics": ["linked-list", "divide-and-conquer", "heap-priority-queue", "merge-sort"], "url": "https://leetcode.com/problems/merge-k-sorted-lists/", "problem_html": "<p>You are given an array of <code>k</code> linked-lists <code>lists</code>, each linked-list is sorted in ascending order.</p>\n\n<p><em>Merge all the linked-lists into one sorted linked-list and return it.</em></p>\n\n<p> </p>\n<p><strong class=\"example\">Example 1:</strong></p>\n\n<pre>\n<strong>Input:</strong> lists = [[1,4,5],[1,3,4],[2,6]]\n<strong>Output:</strong> [1,1,2,3,4,4,5,6]\n<strong>Explanation:</strong> The linked-lists are:\n[\n 1->4->5,\n 1->3->4,\n 2->6\n]\nmerging them into one sorted linked list:\n1->1->2->3->4->4->5->6\n</pre>\n\n<p><strong class=\"example\">Example 2:</strong></p>\n\n<pre>\n<strong>Input:</strong> lists = []\n<strong>Output:</strong> []\n</pre>\n\n<p><strong class=\"example\">Example 3:</strong></p>\n\n<pre>\n<strong>Input:</strong> lists = [[]]\n<strong>Output:</strong> []\n</pre>\n\n<p> </p>\n<p><strong>Constraints:</strong></p>\n\n<ul>\n\t<li><code>k == lists.length</code></li>\n\t<li><code>0 <= k <= 10<sup>4</sup></code></li>\n\t<li><code>0 <= lists[i].length <= 500</code></li>\n\t<li><code>-10<sup>4</sup> <= lists[i][j] <= 10<sup>4</sup></code></li>\n\t<li><code>lists[i]</code> is sorted in <strong>ascending order</strong>.</li>\n\t<li>The sum of <code>lists[i].length</code> will not exceed <code>10<sup>4</sup></code>.</li>\n</ul>\n", "hints": []}}]}