CodeWithClarity

 You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.   Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0. class Solution {     public int maxProfit ( int [] prices ) {                       int maxprofix = 0 ;         int minimum =prices[ 0 ];                 f...

 You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.   Example 1: Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4. Example 3: Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0. Using math- class Solution {     public int maxProfit ( int [] prices ...

 Given string str, find the length of the longest repeating subsequence such that it can be found twice in the given string. The two identified subsequences A and B can use the same ith character from string s if and only if that ith character has different indices in A and B. For example, A = "xax" and B = "xax" then the index of the first "x" must be different in the original string for A and B. Examples : Input: s = "axxzxy" Output: 2 Explanation: The given array with indexes looks like a x x z x y  0 1 2 3 4 5 The longest subsequence is "xx". It appears twice as explained below. subsequence A x x 0 1  <-- index of subsequence A ------ 1 2  <-- index of s subsequence B x x 0 1  <-- index of subsequence B ------ 2 4  <-- index of s We are able to use character 'x' (at index 2 in s) in both subsequences as it appears on index 1 in subsequence A and index 0 in subsequence B. Input: s = "axxxy" Output: 2 Exp...

 Given a string s, find the longest palindromic subsequence's length in s. 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.   Example 1: Input: s = "bbbab" Output: 4 Explanation: One possible longest palindromic subsequence is "bbbb". Example 2: Input: s = "cbbd" Output: 2 Explanation: One possible longest palindromic subsequence is "bb".   Constraints: 1 <= s.length <= 1000 s consists only of lowercase English letters. Approach 1: 💡 Concept: We reverse the string and apply the LCS concept: If s = "bbabcbcab" , then: rev = "bacbcbabb" Find LCS(s, rev) → that will be the longest palindromic subsequence It look like Longest string subsequence question class Solution {     public int lcs ( String s1 , String s2 , int i , int j , int [][] dp ) {         if (i == s1 . length () || j == s2 . leng...

 Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence that is common to both strings.   Example 1: Input: text1 = "abcde", text2 = "ace"  Output: 3   Explanation: The longest common subsequence is "ace" and its length is 3. Example 2: Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3. Example 3: Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.   Constraints: 1 <= text1.length, text2.length ...

 Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character   Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation:  horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation:  intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')   Constraints: 0 <= word1.length, word2.length <= 500 word1 and word2 consist of lowercase English letters. 🧠 Key Idea: Recursion with Choices At each c...

 You are given an integer array nums. You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that: All elements in the subarray are unique. The sum of the elements in the subarray is maximized. Return the maximum sum of such a subarray.   Example 1: Input: nums = [1,2,3,4,5] Output: 15 Explanation: Select the entire array without deleting any element to obtain the maximum sum. Example 2: Input: nums = [1,1,0,1,1] Output: 1 Explanation: Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum. Example 3: Input: nums = [1,2,-1,-2,1,0,-1] Output: 3 Explanation: Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum. class Solution {     public int maxSum ( int [] nums ) {           Set < Integer ...

 You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping: "1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z' However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25"). For example, "11106" can be decoded into: "AAJF" with the grouping (1, 1, 10, 6) "KJF" with the grouping (11, 10, 6) The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid). Note: there may be strings that are impossible to decode. Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0. The test cases are generated so that the answer fits in a 32-bit integ...

 You are given an integer array cost where cost[i] is the cost of ith 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.   Example 1: Input: cost = [10,15,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15. Example 2: Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.   Constraints: 2 <= cost.length <= 1000 0 <= cost[i] <= 999 class Solution {     public int minCostClimbingStairs ( int [...

 Given an array arr[] of rope lengths, connect all ropes into a single rope with the minimum total cost. The cost to connect two ropes is the sum of their lengths. Input: arr[] = [4, 3, 2, 6] Output: 29 Explanation: We can connect the ropes in following ways. 1) First connect ropes of lengths 2 and 3. Which makes the array [4, 5, 6]. Cost of this operation 2 + 3 = 5.  2) Now connect ropes of lengths 4 and 5. Which makes the array [9, 6]. Cost of this operation 4 + 5 = 9. 3) Finally connect the two ropes and all ropes have connected. Cost of this operation 9 + 6 =15. Total cost is 5 + 9 + 15 = 29. This is the optimized cost for connecting ropes.  Other ways of connecting ropes would always have same or more cost. For example, if we connect 4 and 6 first (we get three rope of 3, 2 and 10), then connect 10 and 3 (we get two rope of 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38. [Expected Approach] Greedy with Heap - O(n*log(n)) Time and ...

 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.   Example 1: Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum. Example 2: Input: grid = [[1,2,3],[4,5,6]] Output: 12   Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 200 class Solution {         public int solve ( int i , int j , int m , int n , int [][] dp , int [][] Grid ){         if (i==m- 1 && j==n- 1 )         {             return Grid [i][j];         }                         if (dp[i][j] !=- 1 )         {       ...

 You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle. Return the number of possible unique paths that the robot can take to reach the bottom-right corner. The testcases are generated so that the answer will be less than or equal to 2 * 109.   Example 1: Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right Example 2: Input: obstacleGrid = [[0,1],[0,0]] Output: 1   Constraints: m == obstacleGrid.length n == obstacl...

 There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to 2 * 109.   Input: m = 3, n = 7 Output: 28 Example 2: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down class Solution {     public int solve ( int i , int j , int m , int n , int [][] dp )     {         if (i==m- 1 && j==n- 1 )         {          ...

 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 = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.   Constraints: 1 <= nums.length <= 100 0 <= nums[i] <= 400 🔁 Dry Run: Input: nums = [2, 1, 4, 9] rob() → calls solve(nums, 0, dp) ...