Posts

Today, let’s look at LeetCode problem 80: Remove Duplicates from Sorted Array II. The instructions are as follows: Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are \(k\) elements after removing the duplicates, then the first \(k\) elements of nums should hold the final result. It does not matter what you leave beyond the first \(k\) elements. ...

Today, let’s look at LeetCode problem 2462: Total Cost to Hire K Workers. The instructions are as follows: You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the \(i\)-th worker. You are also given two integers \(k\) and candidates. We want to hire exactly \(k\) workers according to the following rules: You will run \(k\) sessions and hire exactly one worker in each session. In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index. For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,**1**,2]. In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,**2**,7,7,2]. Please note that the indexing may be changed in the process. If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index. A worker can only be chosen once. Return the total cost to hire exactly \(k\) workers. ...

Let’s solve LeetCode problem 88: Merge Sorted Array. This problem is quite short and straightforward. The instructions are as follows: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers \(m\) and \(n\), representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of \(m\) + \(n\), where the first \(m\) elements denote the elements that should be merged, and the last \(n\) elements are set to 0 and should be ignored. nums2 has a length of \(n\). ...

Today, let’s look at LeetCode problem 216: Combination Sum III. The instructions are as follows: Find all valid combinations of \(k\) numbers that sum up to \(n\) such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order. ...

Today, let’s look at LeetCode problem 790: Domino and Tromino Tiling. The instructions are as follows: You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. Given an integer \(n\), return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7. In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile. ...