LeetCode

Today, let’s look at LeetCode problem 435: Non-overlapping intervals. The instructions are as follows: Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping. Let’s dive in! Interval scheduling reformulation Interval scheduling is a class of problems that involve a set of tasks, represented by their start and end times. The interval scheduling maximization problem (ISMP) is about finding the largest set of non-overlapping tasks. This is highly related to our interval removal problem. In fact, the following statements are equivalent: ...

Hi, everyone! Today, we’ll be looking at LeetCode problem 399. In this problem, we are given a bunch of reference equations of the form \(a_i / b_i = c_i\) for \(i = 1 , \dots, n\). The symbols \(a_i, b_i\) are given as strings, while \(c_i\) are given as floating point numbers. We’re then asked to compute the value of a query equation \(q_1 / q_2\). If \(q_1 / q_2\) is one of the reference equations, we can return that value. Otherwise, we can follow a kind of chain-rule strategy. Suppose we are given "a" / "b" with value 2.0 and "b" / "c" with value 3.0, then we can compute "a" / "c" by the product: "a" / "c" = "a" / "b" * "b" / "c", which is equal to 2.0 * 3.0 = 6.0. If there’s no way to find a solution, we return -1. ...

Very quick post about finding the peak element in an array. This is LeetCode problem 162. We have an array nums with \(n\) integers and want to find the index of one of its peaks in \(O(\log n)\) time. The important detail is this: no two neighboring elements have the same value. Let’s dive in! Solution To solve this in logarithmic time, we will use binary search. We start with a left index and a right index. We then compute a mid point mid = (left + right) / 2. Now we investigate what the local behavior around mid is. If nums[mid] > nums[mid + 1], it means that there’s no point searching for the peak at mid + 1 or to its right, so we set right = mid. Otherwise, there’s no point in searching for the peak at mid or to its left, so we set left = mid + 1. ...

Welcome back to another LeetCode walkthrough! Let’s look at LeetCode problem 714. We’re given an array of stock prices. Each day, we can either buy a stock if we have none or sell a stock we own (but not both). When we sell a stock, we have to pay a transaction fee. We want to find the maximum profit we can achieve. We approach this using dynamic programming. Let’s dive in! ...

Welcome back to another LeetCode walkthrough! This time, we’ll be tackling LeetCode problem 1268. We’re given an array of strings called products, as well as a string searchWord. Our goal is to suggest three products after typing each character of searchWord. This is a tiny autocompletion method! We could solve this problem with a Trie, like the one we implemented to solve LeetCode problem 208. Check it out! But today, I felt like solving this without writing hyper-optimized or over-engineered code. Our solution will be simple and straightforward… but still efficient! Let’s dive in. ...