Problem Statement: # Given a m x n grid filled with non-negative integers, find a path from the top left corner to the bottom right corner which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Return the minimum path sum. Example: # Input: grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] Output: 7 Explanation: The path that minimizes the sum is 1→3→1→1→1, which sums to 7. ...
Question # Given an integer array nums of n elements, partition it into two non-empty subsets, S1 and S2, such that the absolute difference between the sum of elements in S1 and the sum of elements in S2 is minimized. Return the minimum absolute difference. Example # Input: nums = [1, 2, 3, 4] Output: 0 Explanation: Partitioning the array into subsets [1, 4] and [2, 3] gives two subsets with equal sums of 5, so the minimum absolute difference is 0. ...
Problem Statement: # You are given a list of n servers, where each server has a certain load represented by an integer. Your task is to partition this list into two sublists such that: The absolute difference between the sums of the loads of the two sublists is minimized. Each server belongs to exactly one sublist. The order of servers in the sublists does not matter. Return the minimum possible absolute difference. ...
Problem Statement # Given a grid of dimensions m x n, each cell in the grid can be either land (1) or water (0). You start at the top-left corner of the grid (0, 0) and can move either down or right at any point in time, but you can’t move through water. Find the number of unique paths from the top-left corner to the bottom-right corner (m-1, n-1). ...
Problem Statement # Given a m x n grid filled with non-negative numbers, find a path from the top left to the bottom right corner, which maximizes the sum of the numbers along its path. You can only move either down or right at any point in time. Example: Input: grid = [[1,3,1], [1,5,1], [4,2,1]] Output: 12 Explanation: The path 1 -> 3 -> 5 -> 1 -> 1 -> 1 maximizes the sum. ...
Problem # Given an array nums and an integer k, find the maximum sum of non-overlapping subarrays, each of size k. Example: Input: nums = [1, 2, 3, 4, 5, 6, 1], k = 2 Output: 15 Explanation: The maximum sum is obtained by taking subarrays [5, 6] and [3, 4], which sum to 11 and 4 respectively. The total is 15. Solution Approach # The solution involves using a sliding window approach to find the maximum sum of each subarray of size k, and dynamic programming to ensure non-overlapping. ...
Problem # You are given an array arr of positive integers, representing the maximum number of jumps you can make from each index. You start from the first index and must reach the last index. Find the minimum number of jumps required to reach the end of the array. Solution # To solve this problem, we can use dynamic programming (DP). We will create a new DP array dp and initialize it with infinity except for the first element, which is set to 0. ...
Problem # Given an array of positive integers, find the maximum sum of non-adjacent elements in the array. Example: # Input: nums = [3, 2, 7, 10] Output: 13 Explanation: The maximum sum is obtained by taking elements 3 and 10. Input: nums = [3, 2, 5, 10, 7] Output: 15 Explanation: The maximum sum is obtained by taking elements 3, 5, and 7. Solution Approach # This problem can be solved using dynamic programming. ...
Problem # You are given n jobs where each job consists of a start time, end time, and a profit. You can choose to perform these jobs such that no two jobs overlap. Find the maximum profit you can achieve by scheduling these jobs. Example: # Input: jobs = [(1, 3, 50), (2, 5, 20), (4, 6, 70), (6, 7, 30)] Output: 120 Explanation: The optimal job schedule is to do the job from 1 to 3 and then the job from 4 to 6. ...
Problem # You are given an array nums of integers. Write a function to determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is the same. Example: # Input: nums = [1, 5, 11, 5] Output: True Explanation: The array can be partitioned as [1, 5, 5] and [11]. Solution # The problem is a variation of the “Subset Sum” problem, which is a classic dynamic programming issue. ...
Problem # Given a m x n grid filled with non-negative numbers, find a path from the top left corner to the bottom right corner which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Some cells might be obstacles where the robot cannot enter. These cells are marked with a -1. Other cells contain integers representing the cost of passing through them. ...
Problem # Given a string containing only digits, find the minimum number of characters to be inserted to make it a palindrome. Solution # To solve this problem, we need to find the longest palindromic subsequence in the given string. The minimum number of characters to be inserted to make the string a palindrome is equal to the length of the string minus the length of the longest palindromic subsequence. ...
Problem # Given a string s, find the longest palindromic substring in s. Example: Input: s = "babad" Output: One of "bab" or "aba" (since both are valid longest palindromic substrings). Solution # Algorithm Used: # Dynamic Programming Solution Approach: # The approach is to build a table that represents substrings of the given string. The table will be filled in a way that table[i][j] will be true if the substring from index i to j is a palindrome. ...
Problem # Given an integer array nums, find the contiguous subarray within the array which has the largest product, and return its product. The subarray must contain at least one number. Example: Input: nums = [2, 3, -2, 4] Output: 6 Explanation: The subarray [2, 3] has the largest product = 6. Solution # Algorithm: Dynamic Programming The key to this problem is to handle the negative numbers. A product of two negative numbers turns positive, and this could potentially be larger than a currently known maximum product. ...
Problem # Given two DNA strings, strand1 and strand2, return the minimum number of genetic mutations needed to change strand1 into strand2. A genetic mutation is defined as changing one character (i.e., ‘A’, ‘T’, ‘C’, or ‘G’) into another character. Solution # If the lengths of strand1 and strand2 can be different, the problem becomes a bit more complex. We need to consider not only mutations (changing one character into another) but also insertions and deletions to transform one strand into the other. ...
Problem # Given two sequences, find the length of their longest common subsequence (LCS). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Solution # Here is the Python code for finding the length of the longest common subsequence (LCS) between two sequences: def lcs_length(X, Y): m = len(X) n = len(Y) # Create a 2D array to store lengths of LCS of subproblems L = [[0] * (n + 1) for i in range(m + 1)] # Fill L[m+1][n+1] in bottom up fashion for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: L[i][j] = 0 elif X[i - 1] == Y[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) # L[m][n] contains the length of LCS for X[0. ...
Problem # Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null. Integers can appear more than once in the list. You may assume all numbers in the list are positive. Solution 1 # Here is a Python solution using recursion and backtracking: def find_subset(candidates, target): def _find_subset(idx, target, path): if target == 0: return [path] if idx == len(candidates) or target < 0: return [] # Without the current number. ...
Problem # You are given a grid filled with non-negative numbers. Find a path from the top left to the bottom right, which minimizes the sum of all numbers along its path. Solution # To solve this problem, a typical approach is to use dynamic programming. The idea is to create a 2D array (or modify the given grid in place, if mutation is acceptable) where each cell contains the minimum sum required to reach that cell from the top-left corner. ...
Problem # Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Solution # Here’s the Python code for finding the minimum number of coins needed to make a target amount, given a set of coin denominations: def min_coins(coins, amount): # Create a table to store the minimum number of coins for each amount dp = [float('inf')] * (amount + 1) dp[0] = 0 # Base case: 0 coins are needed to make amount 0 for i in range(1, amount + 1): for coin in coins: if i - coin >= 0: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] ! ...
Problem # Given an integer n, find the nth Fibonacci number using dynamic programming. The first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two. Solution # The Python code to find the nth Fibonacci number using dynamic programming is as follows: def fibonacci(n): # Initialize a list to store the Fibonacci numbers up to n fib_sequence = [0, 1] # Dynamic programming approach for i in range(2, n + 1): next_fib = fib_sequence[i - 1] + fib_sequence[i - 2] fib_sequence. ...
Problem # Given a string s and a dictionary of words, determine if it’s possible to break s into one or more words from the dictionary. Return true if such a break is possible, false otherwise Solution # The Python function word_break successfully determines if a given string s can be segmented into one or more words from the provided dictionary. The function returns True if such a segmentation is possible, and False otherwise. ...
Problem # Given a string s, partition the string into k non-empty substrings such that every substring is a palindrome. Return the minimum number of cuts needed to make this possible. Solution # Here’s the Python code for the problem statement: def is_palindrome(s): """Check if the given string is a palindrome.""" return s == s[::-1] def min_cuts_for_palindromes(s, k): """ Function to find the minimum number of cuts needed to partition the string into k palindromic substrings. ...
Problem # Given an array of integers, find the minimum cost to reach the top of the stairs. Each step costs some amount as described in the input array. You can either climb one or two steps at a time. Solution # To solve the problem “Given an array of integers, find the minimum cost to reach the top of the stairs, where each step costs a certain amount and you can climb one or two steps at a time,” we can use dynamic programming. ...
Problem # Find the longest increasing subsequence in a given sequence of numbers. Solution # def longest_increasing_subsequence(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # Test the function with an example print(longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80])) In this code, the longest_increasing_subsequence function takes a list of integers as input and returns the length of the longest increasing subsequence in that list. ...
Problem # Given a set of distinct positive integers, find the largest subset such that every pair of elements in the subset (i, j) satisfies either i % j = 0 or j % i = 0. For example, given the set [3, 5, 10, 20, 21], you should return [5, 10, 20]. Given [1, 3, 6, 24], return [1, 3, 6, 24]. Solution # To solve this problem, we can use a dynamic programming approach. ...