DSA

Problem Statement: Maximum Product Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest product and return its product. Example Example 1: Input:nums = [2, 3, -2, 4]Output:6Explanation: The subarray [2, 3] has the largest product 6. Example 2: Input:nums = [-2, 0, -1]Output:0Explanation: The subarray [0] has the largest product 0. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <limits.h>int maxProduct(int* nums, int numsSize) { if (numsSize == 0) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < numsSize; i++) { if (nums[i] < 0) { // Swap maxProd and minProd when nums[i] is negative int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = (nums[i] > nums[i] * maxProd) ? nums[i] : nums[i] * maxProd; minProd = (nums[i] < nums[i] * minProd) ? nums[i] : nums[i] * minProd; result = (result > maxProd) ? result : maxProd; } return result;}int main() { int nums[] = {2, 3, -2, 4}; int size = sizeof(nums) / sizeof(nums[0]); printf(“Maximum product subarray: %d\n”, maxProduct(nums, size)); // Output: 6 return 0;} C++ #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProduct(vector<int>& nums) { if (nums.empty()) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.size(); i++) { if (nums[i] < 0) { swap(maxProd, minProd); } maxProd = max(nums[i], nums[i] * maxProd); minProd = min(nums[i], nums[i] * minProd); result = max(result, maxProd); } return result;}int main() { vector<int> nums = {2, 3, -2, 4}; cout << “Maximum product subarray: ” << maxProduct(nums) << endl; // Output: 6 return 0;} Java public class MaximumProductSubarray { public static int maxProduct(int[] nums) { if (nums.length == 0) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = Math.max(nums[i], nums[i] * maxProd); minProd = Math.min(nums[i], nums[i] * minProd); result = Math.max(result, maxProd); } return result; } public static void main(String[] args) { int[] nums = {2, 3, -2, 4}; System.out.println(“Maximum product subarray: ” + maxProduct(nums)); // Output: 6 }} Python def maxProduct(nums): if not nums: return 0 maxProd = minProd = result = nums[0] for num in nums[1:]: if num < 0: maxProd, minProd = minProd, maxProd maxProd = max(num, num * maxProd) minProd = min(num, num * minProd) result = max(result, maxProd) return result# Examplenums = [2, 3, -2, 4]print(“Maximum product subarray:”, maxProduct(nums)) # Output: 6 C# using System;public class MaximumProductSubarray { public static int MaxProduct(int[] nums) { if (nums.Length == 0) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.Length; i++) { if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = Math.Max(nums[i], nums[i] * maxProd); minProd = Math.Min(nums[i], nums[i] * minProd); result = Math.Max(result, maxProd); } return result; } public static void Main() { int[] nums = {2, 3, -2, 4}; Console.WriteLine(“Maximum product subarray: ” + MaxProduct(nums)); // Output: 6 }} JavaScript function maxProduct(nums) { if (nums.length === 0) return 0; let maxProd = nums[0], minProd = nums[0], result = nums[0]; for (let i = 1; i < nums.length; i++) { if (nums[i] < 0) { [maxProd, minProd] = [minProd, maxProd]; } maxProd = Math.max(nums[i], nums[i] * maxProd); minProd = Math.min(nums[i], nums[i] * minProd); result = Math.max(result, maxProd); } return result;}console.log(“Maximum product subarray:”, maxProduct([2, 3, -2, 4])); // Output: 6 Summary

Problem Statement: Word Break II Given a string s and a list of words wordDict, return all possible sentence(s) where each sentence is a valid segmentation of s into words from wordDict. The solution should return a list of all possible sentences. Note: Example Example 1: Input:”catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] Output:[“cats and dog”, “cat sand dog”] Example 2: Input:”pineapplepenapple”wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”] Output:[“pine apple pen apple”, “pineapple pen apple”, “pine applepen apple”] Example 3: Input:”catsandog”wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] Output:[] Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#define MAX 1000void findWordBreaks(char* s, int start, char** wordDict, int wordDictSize, bool* dp, char*** result, int* returnSize) { if (start == strlen(s)) { result[*returnSize] = malloc(sizeof(char*) * 2); result[*returnSize][0] = strdup(“”); (*returnSize)++; return; } if (!dp[start]) return; // Skip if this position cannot be reached for (int i = 0; i < wordDictSize; i++) { int len = strlen(wordDict[i]); if (start + len <= strlen(s) && strncmp(s + start, wordDict[i], len) == 0) { char** tempResult; int tempSize = 0; findWordBreaks(s, start + len, wordDict, wordDictSize, dp, &tempResult, &tempSize); for (int j = 0; j < tempSize; j++) { int newSize = tempSize + 1; result[*returnSize] = realloc(result[*returnSize], sizeof(char*) * newSize); char* newSentence = malloc(strlen(wordDict[i]) + strlen(tempResult[j]) + 2); sprintf(newSentence, “%s %s”, wordDict[i], tempResult[j]); result[*returnSize][newSize – 1] = newSentence; } } }}int main() { char* s = “catsanddog”; char* wordDict[] = {“cat”, “cats”, “and”, “sand”, “dog”}; int wordDictSize = 5; bool dp[MAX]; memset(dp, 0, sizeof(dp)); char*** result = malloc(sizeof(char**) * MAX); int returnSize = 0; findWordBreaks(s, 0, wordDict, wordDictSize, dp, result, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i][0]); } return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>#include <algorithm>using namespace std;void dfs(string s, unordered_set<string>& wordSet, vector<string>& currentSentence, vector<string>& result, vector<bool>& dp) { if (s.empty()) { string sentence = “”; for (int i = 0; i < currentSentence.size(); i++) { sentence += currentSentence[i]; if (i != currentSentence.size() – 1) sentence += ” “; } result.push_back(sentence); return; } if (!dp[s.size()]) return; for (int i = 1; i <= s.size(); i++) { string word = s.substr(0, i); if (wordSet.find(word) != wordSet.end()) { currentSentence.push_back(word); dfs(s.substr(i), wordSet, currentSentence, result, dp); currentSentence.pop_back(); } }}vector<string> wordBreak(string s, unordered_set<string>& wordSet) { int n = s.length(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } vector<string> result; vector<string> currentSentence; if (dp[n]) dfs(s, wordSet, currentSentence, result, dp); sort(result.begin(), result.end()); return result;}int main() { unordered_set<string> wordSet = {“cat”, “cats”, “and”, “sand”, “dog”}; string s = “catsanddog”; vector<string> result = wordBreak(s, wordSet); for (const auto& sentence : result) { cout << sentence << endl; } return 0;} Java import java.util.*;public class WordBreakII { public static void dfs(String s, Set<String> wordSet, List<String> currentSentence, List<String> result, boolean[] dp) { if (s.isEmpty()) { result.add(String.join(” “, currentSentence)); return; } if (!dp[s.length()]) return; for (int i = 1; i <= s.length(); i++) { String word = s.substring(0, i); if (wordSet.contains(word)) { currentSentence.add(word); dfs(s.substring(i), wordSet, currentSentence, result, dp); currentSentence.remove(currentSentence.size() – 1); } } } public static List<String> wordBreak(String s, Set<String> wordSet) { int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } List<String> result = new ArrayList<>(); if (dp[n]) { List<String> currentSentence = new ArrayList<>(); dfs(s, wordSet, currentSentence, result, dp); } Collections.sort(result); return result; } public static void main(String[] args) { Set<String> wordSet = new HashSet<>(Arrays.asList(“cat”, “cats”, “and”, “sand”, “dog”)); String s = “catsanddog”; List<String> result = wordBreak(s, wordSet); for (String sentence : result) { System.out.println(sentence); } }} Python pythonCopy codedef dfs(s, wordSet, currentSentence, result, dp): if not s: result.append(” “.join(currentSentence)) return if not dp[len(s)]: return for i in range(1, len(s) + 1): word = s[:i] if word in wordSet: currentSentence.append(word) dfs(s[i:], wordSet, currentSentence, result, dp) currentSentence.pop() def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break result = [] if dp[n]: currentSentence = [] dfs(s, wordSet, currentSentence, result, dp) result.sort() return result # Example s = “catsanddog” wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] print(wordBreak(s, wordDict)) # Output: [“cats and dog”, “cat sand dog”] C# using System;using System.Collections.Generic;public class WordBreakII { public static void Dfs(string s, HashSet<string> wordSet, List<string> currentSentence, List<string> result, bool[] dp) { if (s.Length == 0) { result.Add(string.Join(” “, currentSentence)); return; } if (!dp[s.Length]) return; for (int i = 1; i <= s.Length; i++) { string word = s.Substring(0, i); if (wordSet.Contains(word)) { currentSentence.Add(word); Dfs(s.Substring(i), wordSet, currentSentence, result, dp); currentSentence.RemoveAt(currentSentence.Count – 1); } } } public static List<string> WordBreak(string s, HashSet<string> wordSet) { int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.Contains(s.Substring(j, i – j))) { dp[i] = true; break; } } } List<string> result = new List<string>(); if (dp[n]) { List<string> currentSentence = new List<string>(); Dfs(s, wordSet, currentSentence, result, dp); } result.Sort(); return result; } public static void Main() { HashSet<string> wordSet = new HashSet<string> { “cat”, “cats”, “and”, “sand”, “dog” }; string s = “catsanddog”; List<string> result = WordBreak(s, wordSet); foreach (var sentence in result) { Console.WriteLine(sentence); } }} JavaScript function dfs(s, wordSet, currentSentence, result, dp) { if (s === “”) { result.push(currentSentence.join(” “)); return; } if (!dp[s.length]) return; for (let i = 1; i <= s.length; i++) { const word = s.slice(0, i); if (wordSet.has(word)) { currentSentence.push(word); dfs(s.slice(i), wordSet, currentSentence, result, dp); currentSentence.pop(); } }}function wordBreak(s, wordDict) { const wordSet = new Set(wordDict);

Problem Statement: Word Break Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: Example Example 1: Input: s = “leetcode”, wordDict = [“leet”, “code”]Output: trueExplanation: Return true because “leetcode” can be segmented as “leet code”. Example 2: Input: s = “applepenapple”, wordDict = [“apple”, “pen”]Output: trueExplanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Example 3: Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]Output: falseExplanation: Return false because “catsandog” cannot be segmented into words from the dictionary. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>bool wordBreak(char* s, char** wordDict, int wordDictSize) { int n = strlen(s); bool dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < wordDictSize; j++) { int len = strlen(wordDict[j]); if (i >= len && dp[i – len] && strncmp(s + i – len, wordDict[j], len) == 0) { dp[i] = true; break; } } } return dp[n];}int main() { char* wordDict[] = {“leet”, “code”}; int wordDictSize = sizeof(wordDict) / sizeof(wordDict[0]); char s[] = “leetcode”; printf(“%d\n”, wordBreak(s, wordDict, wordDictSize)); // Output: 1 (true) return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>using namespace std;bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } return dp[n];}int main() { vector<string> wordDict = {“leet”, “code”}; string s = “leetcode”; cout << wordBreak(s, wordDict) << endl; // Output: 1 (true) return 0;} Java import java.util.*;public class WordBreak { public static boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } public static void main(String[] args) { List<String> wordDict = Arrays.asList(“leet”, “code”); String s = “leetcode”; System.out.println(wordBreak(s, wordDict)); // Output: true }} Python def wordBreak(s: str, wordDict: list) -> bool: wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[n]# Examples = “leetcode”wordDict = [“leet”, “code”]print(wordBreak(s, wordDict)) # Output: True C# using System;using System.Collections.Generic;public class WordBreak { public static bool WordBreak(string s, IList<string> wordDict) { HashSet<string> wordSet = new HashSet<string>(wordDict); int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.Contains(s.Substring(j, i – j))) { dp[i] = true; break; } } } return dp[n]; } public static void Main() { List<string> wordDict = new List<string> { “leet”, “code” }; string s = “leetcode”; Console.WriteLine(WordBreak(s, wordDict)); // Output: True }} JavaScript function wordBreak(s, wordDict) { const wordSet = new Set(wordDict); const n = s.length; const dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { if (dp[j] && wordSet.has(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n];}console.log(wordBreak(“leetcode”, [“leet”, “code”])); // Output: true Summary

Problem Statement: Palindrome Partitioning II Given a string s, you need to partition it such that every substring of the partition is a palindrome. Return the minimum number of cuts required to partition s such that every substring is a palindrome. Example Example 1: Input: s = “aab” Output: 1Explanation: The palindrome partitioning [“aa”, “b”] could be made with 1 cut. Example 2: Input: s = “a” Output: 0Explanation: The string is already a palindrome, so no cuts are needed. Example 3: Input: s = “abac” Output: 1Explanation: The palindrome partitioning [“aba”, “c”] could be made with 1 cut. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>#define MAX 1000int minCut(char* s) { int n = strlen(s); bool palindrome[n][n]; int dp[n+1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; memset(palindrome, 0, sizeof(palindrome)); for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = (dp[i] < dp[j] + 1) ? dp[i] : dp[j] + 1; } } } return dp[n – 1];}int main() { char s[] = “aab”; printf(“%d\n”, minCut(s)); return 0;} C++ #include <iostream>#include <vector>#include <cstring>using namespace std;int minCut(string s) { int n = s.length(); vector<vector<bool>> palindrome(n, vector<bool>(n, false)); vector<int> dp(n + 1, n); dp[0] = -1; // no cut needed for empty string for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1); } } } return dp[n – 1];}int main() { string s = “aab”; cout << minCut(s) << endl; return 0;} Java public class PalindromePartitioning { public static int minCut(String s) { int n = s.length(); boolean[][] palindrome = new boolean[n][n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s.charAt(i) == s.charAt(j)) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void main(String[] args) { String s = “aab”; System.out.println(minCut(s)); }} Python def minCut(s: str) -> int: n = len(s) palindrome = [[False] * n for _ in range(n)] dp = [i for i in range(-1, n)] for i in range(n – 1, -1, -1): for j in range(i, n): palindrome[i][j] = (s[i] == s[j]) and (j – i <= 2 or palindrome[i + 1][j – 1]) for i in range(n): if palindrome[0][i]: dp[i] = 0 else: for j in range(i): if palindrome[j + 1][i]: dp[i] = min(dp[i], dp[j] + 1) return dp[n – 1]# Examples = “aab”print(minCut(s)) # Output: 1 C# using System;public class PalindromePartitioning { public static int MinCut(string s) { int n = s.Length; bool[,] palindrome = new bool[n, n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i, j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1, j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0, i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1, i]) dp[i] = Math.Min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void Main() { string s = “aab”; Console.WriteLine(MinCut(s)); // Output: 1 }} JavaScript function minCut(s) { const n = s.length; const palindrome = Array.from(Array(n), () => Array(n).fill(false)); const dp = Array.from({ length: n + 1 }, (_, i) => i – 1); for (let i = n – 1; i >= 0; i–) { for (let j = i; j < n; j++) { palindrome[i][j] = (s[i] === s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (let i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (let j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1];}console.log(minCut(“aab”)); // Output: 1 Summary

Problem Statement: Palindrome Partitioning Given a string s, partition the string such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Definition: Example: Example 1: Input: plaintextCopy code”aab” Output: plaintextCopy code[[“a”, “a”, “b”], [“aa”, “b”]] Explanation: The string “aab” can be split in two ways where each substring is a palindrome: Example 2: Input: plaintextCopy code”efe” Output: plaintextCopy code[[“e”, “f”, “e”], [“efe”]] Explanation: The string “efe” can be split into: Approach: We can solve this problem using backtracking and dynamic programming. Backtracking Approach: Algorithm: Code Implementation: 1. C++: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: bool isPalindrome(const string& s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) { if (start == s.length()) { result.push_back(current); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.push_back(s.substr(start, end – start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); // backtrack } } } vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> current; backtrack(s, 0, current, result); return result; }};int main() { Solution sol; string s = “aab”; vector<vector<string>> result = sol.partition(s); for (const auto& partition : result) { for (const auto& str : partition) { cout << str << ” “; } cout << endl; } return 0;} 2. Java: import java.util.ArrayList;import java.util.List;public class Solution { public boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start) != s.charAt(end)) return false; start++; end–; } return true; } public void backtrack(String s, int start, List<String> current, List<List<String>> result) { if (start == s.length()) { result.add(new ArrayList<>(current)); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.add(s.substring(start, end + 1)); backtrack(s, end + 1, current, result); current.remove(current.size() – 1); // backtrack } } } public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); List<String> current = new ArrayList<>(); backtrack(s, 0, current, result); return result; } public static void main(String[] args) { Solution sol = new Solution(); String s = “aab”; List<List<String>> result = sol.partition(s); for (List<String> partition : result) { for (String str : partition) { System.out.print(str + ” “); } System.out.println(); } }} 3. Python: class Solution: def isPalindrome(self, s, start, end): while start < end: if s[start] != s[end]: return False start += 1 end -= 1 return True def backtrack(self, s, start, current, result): if start == len(s): result.append(list(current)) return for end in range(start, len(s)): if self.isPalindrome(s, start, end): current.append(s[start:end+1]) self.backtrack(s, end+1, current, result) current.pop() # backtrack def partition(self, s): result = [] self.backtrack(s, 0, [], result) return result# Example usagesol = Solution()s = “aab”result = sol.partition(s)for partition in result: print(partition) 4. C#: using System;using System.Collections.Generic;public class Solution { public bool IsPalindrome(string s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } public void Backtrack(string s, int start, List<string> current, List<List<string>> result) { if (start == s.Length) { result.Add(new List<string>(current)); return; } for (int end = start; end < s.Length; ++end) { if (IsPalindrome(s, start, end)) { current.Add(s.Substring(start, end – start + 1)); Backtrack(s, end + 1, current, result); current.RemoveAt(current.Count – 1); // backtrack } } } public List<List<string>> Partition(string s) { List<List<string>> result = new List<List<string>>(); List<string> current = new List<string>(); Backtrack(s, 0, current, result); return result; } public static void Main() { Solution sol = new Solution(); string s = “aab”; List<List<string>> result = sol.Partition(s); foreach (var partition in result) { Console.WriteLine(string.Join(” “, partition)); } }} 5. JavaScript: class Solution { isPalindrome(s, start, end) { while (start < end) { if (s[start] !== s[end]) return false; start++; end–; } return true; } backtrack(s, start, current, result) { if (start === s.length) { result.push([…current]); return; } for (let end = start; end < s.length; ++end) { if (this.isPalindrome(s, start, end)) { current.push(s.substring(start, end + 1)); this.backtrack(s, end + 1, current, result); current.pop(); // backtrack } } } partition(s) { let result = []; this.backtrack(s, 0, [], result); return result; }}// Example usage:let sol = new Solution();let s = “aab”;let result = sol.partition(s);result.forEach(partition => { console.log(partition.join(” “));}); Time and Space Complexity:

Problem Statement: Binary Tree Maximum Path Sum Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree, and you are allowed to move from a node to its left or right child but not upwards to its parent. Path Definition: A path is a sequence of nodes in the tree where each pair of adjacent nodes in the sequence has an edge connecting them. The sum of the path is the sum of the node values along the path. Example: Example 1: Input: -10 / \ 9 20 / \ 15 7 Output: 42 Explanation: The path with the maximum sum is 15 -> 20 -> 7, which sums to 15 + 20 + 7 = 42. Example 2: Input: 1 / \ 2 3 Output: 6 Explanation: The path with the maximum sum is 2 -> 1 -> 3, which sums to 2 + 1 + 3 = 6. Approach: Algorithm: Code Implementation: 1. C: #include <stdio.h>#include <limits.h>struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;};int maxPathSumHelper(struct TreeNode* root, int* globalMax) { if (root == NULL) { return 0; } int left = maxPathSumHelper(root->left, globalMax); int right = maxPathSumHelper(root->right, globalMax); int maxSingle = (left > right) ? left : right; maxSingle = (maxSingle > 0) ? maxSingle + root->val : root->val; int maxTop = left + right + root->val; *globalMax = (*globalMax > maxTop) ? *globalMax : maxTop; return maxSingle;}int maxPathSum(struct TreeNode* root) { int globalMax = INT_MIN; maxPathSumHelper(root, &globalMax); return globalMax;}int main() { struct TreeNode n1 = { -10, NULL, NULL }; struct TreeNode n2 = { 9, NULL, NULL }; struct TreeNode n3 = { 20, NULL, NULL }; struct TreeNode n4 = { 15, NULL, NULL }; struct TreeNode n5 = { 7, NULL, NULL }; n1.left = &n2; n1.right = &n3; n3.left = &n4; n3.right = &n5; printf(“Maximum Path Sum: %d\n”, maxPathSum(&n1)); return 0;} 2. C++: #include <iostream>#include <climits>using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public: int maxPathSumHelper(TreeNode* root, int& globalMax) { if (!root) return 0; int left = max(0, maxPathSumHelper(root->left, globalMax)); int right = max(0, maxPathSumHelper(root->right, globalMax)); int localMax = left + right + root->val; globalMax = max(globalMax, localMax); return max(left, right) + root->val; } int maxPathSum(TreeNode* root) { int globalMax = INT_MIN; maxPathSumHelper(root, globalMax); return globalMax; }};int main() { TreeNode n1(-10), n2(9), n3(20), n4(15), n5(7); n1.left = &n2; n1.right = &n3; n3.left = &n4; n3.right = &n5; Solution sol; cout << “Maximum Path Sum: ” << sol.maxPathSum(&n1) << endl; return 0;} 3. Java: class Solution { int maxPathSumHelper(TreeNode root, int[] globalMax) { if (root == null) return 0; int left = Math.max(0, maxPathSumHelper(root.left, globalMax)); int right = Math.max(0, maxPathSumHelper(root.right, globalMax)); int localMax = left + right + root.val; globalMax[0] = Math.max(globalMax[0], localMax); return Math.max(left, right) + root.val; } public int maxPathSum(TreeNode root) { int[] globalMax = { Integer.MIN_VALUE }; maxPathSumHelper(root, globalMax); return globalMax[0]; }}class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; }}public class Main { public static void main(String[] args) { TreeNode n1 = new TreeNode(-10); TreeNode n2 = new TreeNode(9); TreeNode n3 = new TreeNode(20); TreeNode n4 = new TreeNode(15); TreeNode n5 = new TreeNode(7); n1.left = n2; n1.right = n3; n3.left = n4; n3.right = n5; Solution sol = new Solution(); System.out.println(“Maximum Path Sum: ” + sol.maxPathSum(n1)); }} 4. Python: class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def maxPathSumHelper(self, root, globalMax): if not root: return 0 left = max(0, self.maxPathSumHelper(root.left, globalMax)) right = max(0, self.maxPathSumHelper(root.right, globalMax)) localMax = left + right + root.val globalMax[0] = max(globalMax[0], localMax) return max(left, right) + root.val def maxPathSum(self, root: TreeNode) -> int: globalMax = [float(‘-inf’)] self.maxPathSumHelper(root, globalMax) return globalMax[0]# Example usageif __name__ == “__main__”: n1 = TreeNode(-10) n2 = TreeNode(9) n3 = TreeNode(20) n4 = TreeNode(15) n5 = TreeNode(7) n1.left = n2 n1.right = n3 n3.left = n4 n3.right = n5 sol = Solution() print(“Maximum Path Sum:”, sol.maxPathSum(n1)) 5. C#: public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; }}public class Solution { public int MaxPathSumHelper(TreeNode root, ref int globalMax) { if (root == null) return 0; int left = Math.Max(0, MaxPathSumHelper(root.left, ref globalMax)); int right = Math.Max(0, MaxPathSumHelper(root.right, ref globalMax)); int localMax = left + right + root.val; globalMax = Math.Max(globalMax, localMax); return Math.Max(left, right) + root.val; } public int MaxPathSum(TreeNode root) { int globalMax = int.MinValue; MaxPathSumHelper(root, ref globalMax); return globalMax; }}// Example usage:class Program { static void Main(string[] args) { TreeNode n1 = new TreeNode(-10); TreeNode n2 = new TreeNode(9); TreeNode n3 = new TreeNode(20); TreeNode n4 = new TreeNode(15); TreeNode n5 = new TreeNode(7); n1.left = n2; n1.right = n3; n3.left = n4; n3.right = n5; Solution sol = new Solution(); Console.WriteLine(“Maximum Path Sum: ” + sol.MaxPathSum(n1)); }} 6. JavaScript: class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}class Solution { maxPathSumHelper(root, globalMax) { if (!root) return 0; let left = Math.max(0, this.maxPathSumHelper(root.left, globalMax)); let right = Math.max(0, this.maxPathSumHelper(root.right, globalMax)); let localMax = left + right + root.val; globalMax[0] = Math.max(globalMax[0], localMax); return Math.max(left, right) + root.val; } maxPathSum(root) { let globalMax = [Number.NEGATIVE_INFINITY]; this.maxPathSumHelper(root, globalMax); return globalMax[0]; }}// Example usagelet n1 = new TreeNode(-10);let n2 = new TreeNode(9);let n3 = new TreeNode(20);let n4 = new TreeNode(15);let n5 = new TreeNode(7);n1.left = n2;n1.right = n3;n3.left = n4;n3.right = n5;let sol = new Solution();console.log(“Maximum Path Sum:”, sol.maxPathSum(n1)); Summary:

Problem Statement: Best Time to Buy and Sell Stock III You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. You can complete at most two transactions. In other words, you can make at most two buy-sell pairs. Each transaction consists of buying one stock and then selling it. You cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Return the maximum profit you can achieve. Example: Approach To solve this problem, we can use Dynamic Programming (DP) to track the maximum profit we can make with at most two transactions. The key idea is to break the problem into two subproblems: Dynamic Programming Approach: Steps: Code Implementation C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { if (pricesSize == 0) return 0; int first[pricesSize], second[pricesSize]; int minPrice = prices[0]; first[0] = 0; // no profit on the first day // Calculate maximum profit with at most one transaction up to day i for (int i = 1; i < pricesSize; i++) { first[i] = (prices[i] – minPrice > first[i – 1]) ? prices[i] – minPrice : first[i – 1]; minPrice = (prices[i] < minPrice) ? prices[i] : minPrice; } int maxPrice = prices[pricesSize – 1]; second[pricesSize – 1] = 0; // no profit on the last day // Calculate maximum profit with at most one transaction from day i to end for (int i = pricesSize – 2; i >= 0; i–) { second[i] = (maxPrice – prices[i] > second[i + 1]) ? maxPrice – prices[i] : second[i + 1]; maxPrice = (prices[i] > maxPrice) ? prices[i] : maxPrice; } int maxProfit = 0; for (int i = 0; i < pricesSize; i++) { maxProfit = (first[i] + second[i] > maxProfit) ? first[i] + second[i] : maxProfit; } return maxProfit;}int main() { int prices[] = {3,2,6,5,0,3}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 7 return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; vector<int> first(n, 0), second(n, 0); int minPrice = prices[0]; // Calculate maximum profit for the first transaction up to each day for (int i = 1; i < n; i++) { first[i] = max(first[i – 1], prices[i] – minPrice); minPrice = min(minPrice, prices[i]); } int maxPrice = prices[n – 1]; // Calculate maximum profit for the second transaction from each day for (int i = n – 2; i >= 0; i–) { second[i] = max(second[i + 1], maxPrice – prices[i]); maxPrice = max(maxPrice, prices[i]); } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = max(maxProfit, first[i] + second[i]); } return maxProfit;}int main() { vector<int> prices = {3,2,6,5,0,3}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 7 return 0;} Java: public class BestTimeToBuyAndSellStockIII { public static int maxProfit(int[] prices) { int n = prices.length; if (n == 0) return 0; int[] first = new int[n]; int[] second = new int[n]; // First transaction: calculate max profit up to each day int minPrice = prices[0]; for (int i = 1; i < n; i++) { first[i] = Math.max(first[i – 1], prices[i] – minPrice); minPrice = Math.min(minPrice, prices[i]); } // Second transaction: calculate max profit from each day to the end int maxPrice = prices[n – 1]; for (int i = n – 2; i >= 0; i–) { second[i] = Math.max(second[i + 1], maxPrice – prices[i]); maxPrice = Math.max(maxPrice, prices[i]); } // Max profit by combining both transactions int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, first[i] + second[i]); } return maxProfit; } public static void main(String[] args) { int[] prices = {3, 2, 6, 5, 0, 3}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 7 }} Python: def maxProfit(prices): n = len(prices) if n == 0: return 0 first = [0] * n second = [0] * n # First transaction: calculate max profit up to each day min_price = prices[0] for i in range(1, n): first[i] = max(first[i – 1], prices[i] – min_price) min_price = min(min_price, prices[i]) # Second transaction: calculate max profit from each day to the end max_price = prices[-1] for i in range(n – 2, -1, -1): second[i] = max(second[i + 1], max_price – prices[i]) max_price = max(max_price, prices[i]) # Max profit by combining both transactions max_profit = 0 for i in range(n): max_profit = max(max_profit, first[i] + second[i]) return max_profit# Example usageprices = [3, 2, 6, 5, 0, 3]print(“Max profit:”, maxProfit(prices)) # Output: 7 C#: using System;public class BestTimeToBuyAndSellStockIII { public static int MaxProfit(int[] prices) { int n = prices.Length; if (n == 0) return 0; int[] first = new int[n]; int[] second = new int[n]; // First transaction: calculate max profit up to each day int minPrice = prices[0]; for (int i = 1; i < n; i++) { first[i] = Math.Max(first[i – 1], prices[i] – minPrice); minPrice = Math.Min(minPrice, prices[i]); } // Second transaction: calculate max profit from each day to the end int maxPrice = prices[n – 1]; for (int i = n – 2; i >= 0; i–) { second[i] = Math.Max(second[i + 1], maxPrice – prices[i]); maxPrice = Math.Max(maxPrice, prices[i]); } // Max profit by combining both transactions int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.Max(maxProfit, first[i] + second[i]); } return maxProfit; } static void Main() { int[] prices = {3, 2, 6, 5, 0, 3}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 7 }} JavaScript: function maxProfit(prices) { const n = prices.length; if (n === 0) return 0; let first = Array(n).fill(0); let second = Array(n).fill(0); // First transaction: calculate max profit up to each day let minPrice = prices[0]; for (let i = 1; i < n; i++) { first[i] = Math.max(first[i – 1], prices[i] – minPrice); minPrice = Math.min(minPrice, prices[i]); } // Second transaction: calculate max profit from each

Problem Statement: Best Time to Buy and Sell Stock II You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. You can buy and sell the stock as many times as you like (i.e., multiple transactions are allowed). However, you must sell the stock before you buy again. Return the maximum profit you can achieve. Example: Approach In this case, multiple transactions are allowed. A straightforward solution is to buy and sell the stock whenever there is a price increase, since each increase provides an opportunity for profit. Code Implementation C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { int max_profit = 0; for (int i = 1; i < pricesSize; i++) { if (prices[i] > prices[i – 1]) { max_profit += prices[i] – prices[i – 1]; // add the profit from price increase } } return max_profit;}int main() { int prices[] = {7, 1, 5, 3, 6, 4}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 7 return 0;} C++: #include <iostream>#include <vector>using namespace std;int maxProfit(vector<int>& prices) { int max_profit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] > prices[i – 1]) { max_profit += prices[i] – prices[i – 1]; // add the profit from price increase } } return max_profit;}int main() { vector<int> prices = {7, 1, 5, 3, 6, 4}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 7 return 0;} Java: public class BestTimeToBuyAndSellStockII { public static int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i – 1]) { maxProfit += prices[i] – prices[i – 1]; // add the profit from price increase } } return maxProfit; } public static void main(String[] args) { int[] prices = {7, 1, 5, 3, 6, 4}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 7 }} Python: def maxProfit(prices): max_profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i – 1]: max_profit += prices[i] – prices[i – 1] # add the profit from price increase return max_profit# Example usageprices = [7, 1, 5, 3, 6, 4]print(“Max profit:”, maxProfit(prices)) # Output: 7 C#: using System;public class BestTimeToBuyAndSellStockII { public static int MaxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.Length; i++) { if (prices[i] > prices[i – 1]) { maxProfit += prices[i] – prices[i – 1]; // add the profit from price increase } } return maxProfit; } static void Main() { int[] prices = {7, 1, 5, 3, 6, 4}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 7 }} JavaScript: function maxProfit(prices) { let maxProfit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i – 1]) { maxProfit += prices[i] – prices[i – 1]; // add the profit from price increase } } return maxProfit;}// Example usagelet prices = [7, 1, 5, 3, 6, 4];console.log(“Max profit:”, maxProfit(prices)); // Output: 7 Explanation: Summary: This problem can be efficiently solved using a greedy approach, where we accumulate profits from each price increase. This approach runs in O(n) time and uses O(1) space, making it optimal for this problem. It works well when multiple transactions are allowed, as we can capture all upward price movements.

Problem Statement: Best Time to Buy and Sell Stock You are given an array of integers where each element represents the price of a stock on a given day. You need to find the maximum profit you can achieve by buying and selling the stock exactly once. You can assume that you can only make one buy and one sell. The buying must happen before the selling. Example: Approach Steps: Code Implementations C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { int min_price = prices[0]; int max_profit = 0; for (int i = 1; i < pricesSize; i++) { if (prices[i] < min_price) { min_price = prices[i]; // update min price } else { int profit = prices[i] – min_price; if (profit > max_profit) { max_profit = profit; // update max profit } } } return max_profit;}int main() { int prices[] = {7, 1, 5, 3, 6, 4}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 5 return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProfit(vector<int>& prices) { int min_price = prices[0]; int max_profit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] < min_price) { min_price = prices[i]; // update min price } else { int profit = prices[i] – min_price; max_profit = max(max_profit, profit); // update max profit } } return max_profit;}int main() { vector<int> prices = {7, 1, 5, 3, 6, 4}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 5 return 0;} Java: public class BestTimeToBuyAndSellStock { public static int maxProfit(int[] prices) { int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; // update min price } else { int profit = prices[i] – minPrice; maxProfit = Math.max(maxProfit, profit); // update max profit } } return maxProfit; } public static void main(String[] args) { int[] prices = {7, 1, 5, 3, 6, 4}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 5 }} Python: def maxProfit(prices): min_price = prices[0] max_profit = 0 for price in prices[1:]: if price < min_price: min_price = price # update min price else: profit = price – min_price max_profit = max(max_profit, profit) # update max profit return max_profit# Example usageprices = [7, 1, 5, 3, 6, 4]print(“Max profit:”, maxProfit(prices)) # Output: 5 C#: using System;public class BestTimeToBuyAndSellStock { public static int MaxProfit(int[] prices) { int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.Length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; // update min price } else { int profit = prices[i] – minPrice; maxProfit = Math.Max(maxProfit, profit); // update max profit } } return maxProfit; } static void Main() { int[] prices = {7, 1, 5, 3, 6, 4}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 5 }} JavaScript: function maxProfit(prices) { let minPrice = prices[0]; let maxProfit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; // update min price } else { let profit = prices[i] – minPrice; maxProfit = Math.max(maxProfit, profit); // update max profit } } return maxProfit;}// Example usagelet prices = [7, 1, 5, 3, 6, 4];console.log(“Max profit:”, maxProfit(prices)); // Output: 5 Explanation of Approach: Time Complexity: Space Complexity: Edge Cases: Summary: This problem can be efficiently solved using a greedy approach, tracking the minimum price and calculating the potential profit at each step. The solution runs in linear time and constant space, making it highly optimal.

Problem Statement: Triangle Given a triangle represented as a 2D array of integers, where each row in the triangle contains one more number than the previous row, find the minimum path sum from the top to the bottom. Each step you may move to an adjacent number in the row directly below, i.e., from triangle[i][j] to triangle[i+1][j] or triangle[i+1][j+1]. For example: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Approach This problem can be solved using Dynamic Programming. The key idea is to start from the bottom of the triangle and work upwards, updating each element in the triangle with the minimum path sum from that element to the bottom. Example For the triangle: 2 3 4 6 5 7 4 1 8 3 We start from the bottom: Thus, the minimum path sum is 11. Code Implementations C: #include <stdio.h>int minimumTotal(int** triangle, int numRows) { // Start from the second last row and work upwards for (int row = numRows – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += (triangle[row + 1][col] < triangle[row + 1][col + 1]) ? triangle[row + 1][col] : triangle[row + 1][col + 1]; } } // The top element now contains the minimum path sum return triangle[0][0];}int main() { int numRows = 4; int triangle[4][4] = { {2, 0, 0, 0}, {3, 4, 0, 0}, {6, 5, 7, 0}, {4, 1, 8, 3} }; // Converting static 2D array to dynamic 2D array for passing to function int* trianglePointers[4]; for (int i = 0; i < 4; i++) { trianglePointers[i] = triangle[i]; } printf(“Minimum Total: %d\n”, minimumTotal(trianglePointers, numRows)); // Output: 11 return 0;} C++: #include <iostream>#include <vector>using namespace std;int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); // Start from the second last row and work upwards for (int row = n – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]); } } // The top element now contains the minimum path sum return triangle[0][0];}int main() { vector<vector<int>> triangle = { {2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3} }; cout << “Minimum Total: ” << minimumTotal(triangle) << endl; // Output: 11 return 0;} Java: import java.util.List;import java.util.ArrayList;public class Triangle { public static int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); // Start from the second last row and work upwards for (int row = n – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it int minPathSum = Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1)); triangle.get(row).set(col, triangle.get(row).get(col) + minPathSum); } } // The top element now contains the minimum path sum return triangle.get(0).get(0); } public static void main(String[] args) { List<List<Integer>> triangle = new ArrayList<>(); triangle.add(List.of(2)); triangle.add(List.of(3, 4)); triangle.add(List.of(6, 5, 7)); triangle.add(List.of(4, 1, 8, 3)); System.out.println(“Minimum Total: ” + minimumTotal(triangle)); // Output: 11 }} Python: def minimumTotal(triangle): n = len(triangle) # Start from the second last row and work upwards for row in range(n – 2, -1, -1): for col in range(row + 1): # Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]) # The top element now contains the minimum path sum return triangle[0][0]# Example usagetriangle = [ [2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]print(“Minimum Total:”, minimumTotal(triangle)) # Output: 11 C#: using System;using System.Collections.Generic;class Triangle { public static int MinimumTotal(List<List<int>> triangle) { int n = triangle.Count; // Start from the second last row and work upwards for (int row = n – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it int minPathSum = Math.Min(triangle[row + 1][col], triangle[row + 1][col + 1]); triangle[row][col] += minPathSum; } } // The top element now contains the minimum path sum return triangle[0][0]; } static void Main() { var triangle = new List<List<int>> { new List<int> { 2 }, new List<int> { 3, 4 }, new List<int> { 6, 5, 7 }, new List<int> { 4, 1, 8, 3 } }; Console.WriteLine(“Minimum Total: ” + MinimumTotal(triangle)); // Output: 11 }} JavaScript: function minimumTotal(triangle) { const n = triangle.length; // Start from the second last row and work upwards for (let row = n – 2; row >= 0; row–) { for (let col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]); } } // The top element now contains the minimum path sum return triangle[0][0];}// Example usageconst triangle = [ [2], [3, 4], [6, 5, 7], [4, 1, 8, 3]];console.log(“Minimum Total:”, minimumTotal(triangle)); // Output: 11 Explanation: Time Complexity: Space Complexity: Summary: The problem of finding the minimum path sum in a triangle can be efficiently solved using dynamic programming with a bottom-up approach. This approach minimizes the space complexity by modifying the triangle in place.