Greedy

Let’s solve LeetCode problem 55: Jump Game. The instructions are as follows: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Constraints: 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 I solved this in two ways: a less efficient approach using dynamic programming, and a very fast greedy method. Let’s dive in! ...

Let’s solve LeetCode problem 122: Best Time to Buy and Sell Stock II. The instructions are as follows: You are given an integer array prices where prices[i] is the price of a given stock on the \(i\)-th day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock. Find and return the maximum profit you can achieve. ...

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. ...

Today, let’s look at LeetCode problem 746: Min Cost Climbing Stairs. The instructions are as follows: You are given an integer array cost where cost[i] is the cost of \(i\)-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor. ...

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: ...