Author: devangini123

🌙 Fibonacci Numbers using DP Prerequisite: Recursion N = 4 This recursion has exponential time complexity, as the recursion tree grows significantly when n increases. For example, if n = 6. Overlapping Subproblems: As you can see, some subproblems repeat. If you encounter the same subproblems again and again, this is known as overlapping subproblems. Optimal Substructure: When solving smaller subproblems helps in solving the bigger problem, the problem is said to have an optimal substructure. Note: If any problem satisfies these two properties (overlapping subproblems and optimal substructure), it is an ideal candidate for Dynamic Programming (DP). Time Complexity:…

🌙 Dynamic Programming Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s. It is an optimisation technique use along with data structures. Applied in mathematics and optimisation. Dynamic Programming = Intelligent Laziness Dynamic Programming (DP) can be thought of as intelligent laziness. The idea is simple: We want to solve a problem efficiently, without doing the same hard work again and again. In a brute-force approach, we try to solve a problem by breaking it down into smaller subproblems. However, many of these subproblems turn out to…

🌙 Problem Statement: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3…

🌙 Problem Statement: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money…

🌙 Problem Statement: There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children. Example 1: Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false Return the minimum number of candies you need to have to distribute the candies to the children.…

🌙 Problem Statement: There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children. Example 1: Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false Return the minimum number of candies you need to have to distribute the candies to the children.…

🌙 Problem Statement: There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west). You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car’s initial location. Return true if it is possible to pick up and drop off all passengers for all the given trips, or…

🌙 Problem Statement: There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is…

🌙 Problem Statement: You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there’s a constraint: there has to be a gap of at least n intervals between two tasks with the same label. Return the minimum number of CPU intervals required to complete all tasks. Example 1: Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2 Output: 8 Explanation: A possible sequence is: A -> B -> idle ->…

🌙 Problem Statement: Given an array of intervalsintervals where intervals[i] = [starti, endi], 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. Example 1: Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. Example 2: Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. Example 3: Input: intervals =…