Max Product Subarray Problem Solution with Dynamic Programming

🚀 Day 47 | LeetCode Medium 🟩 Set Matrix Zeroes Today’s problem focused on matrix traversal + space trade-offs, and it was a great reminder that clarity beats complexity. 🧠 Core Idea If any cell in the matrix is 0, then its entire row and column must be set to 0. Instead of modifying the matrix immediately (which can break logic), I used an auxiliary tracking approach. 🛠️ Approach Used Traverse the matrix once Mark affected rows and columns using helper arrays Traverse again and update cells based on these markers This avoids incorrect cascading zeros and keeps the logic clean. ⚡ Why this works Separation of detection and update No accidental overwrites Easy to reason and debug ⏱️ Complexity Time: O(m × n) Space: O(m + n) 🔗 Code on GitHub 👉 https://lnkd.in/g-zxCztf 💡 Key Learning In matrix problems, when you update is just as important as what you update. 🔥 Consistency > Speed Another step forward in my daily DSA journey 🚀 #LeetCode #LeetCodeDailyProblem #SetMatrixZeroes #DSA #Java #Arrays #Matrix #ProblemSolving #CodingJourney #100DaysOfCode #TechCommunity

🚀 Day 488 of #500DaysOfCode 📌 LeetCode Problem: 2976. Minimum Cost to Convert String I Today’s challenge was about minimizing the cost to convert one string into another using a set of given character transformation rules — each with an associated cost. 💡 Key Idea: Model this as a graph problem where each lowercase character is a node, and every transformation is a directed edge with a cost. Then use Floyd–Warshall to compute the minimum conversion cost between all pairs of characters. 🔍 Approach Summary: ✔ Build a 26×26 cost matrix for all character conversions ✔ Use Floyd–Warshall to find the cheapest paths ✔ For each position in the string, sum the cost of converting source[i] → target[i] ✔ Return the total cost — or -1 if impossible ⚙️ Time Complexity: 26³ for preprocessing + O(n) for string traversal, which is efficient even for large inputs. 💬 What I learned today: Graph applications go beyond nodes and edges — even string transformations can be mapped beautifully as a shortest path problem! 🔁 Keep coding. Keep growing. #java #leetcode #codingchallenge #graphalgorithms #floydwarshall

𝗗𝗮𝘆 𝟯𝟲/𝟭𝟬𝟬 | 𝗠𝗲𝗿𝗴𝗲 𝗧𝘄𝗼 𝗦𝗼𝗿𝘁𝗲𝗱 𝗟𝗶𝘀𝘁𝘀 Day 36 ✅ — Recursion over iteration. 𝗧𝗼𝗱𝗮𝘆'𝘀 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: ✅ 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 #𝟮𝟭: Merge Two Sorted Lists (Easy) 𝗪𝗵𝗮𝘁 𝗖𝗹𝗶𝗰𝗸𝗲𝗱: Merge two sorted linked lists. Instead of the iterative dummy node approach, I used 𝗿𝗲𝗰𝘂𝗿𝘀𝗶𝗼𝗻. Compare the heads. Attach the smaller one, then recursively merge the rest. Base case: if one list is empty, return the other. Elegant. Three lines of logic. 𝗠𝘆 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵: 👉 Base cases: if l1 is null, return l2 (and vice versa) 👉 Compare l1.val and l2.val 👉 Attach smaller node and recurse with remaining lists Time: O(n + m), Space: O(n + m) for recursion stack 𝗠𝘆 𝗥𝗲𝗮𝗹𝗶𝘇𝗮𝘁𝗶𝗼𝗻: Seven linked list problems, and recursion just made this one cleaner than iteration. Sometimes the simplest code is the most powerful. 𝗖𝗼𝗱𝗲:🔗 https://lnkd.in/g4f4_B69 𝗗𝗮𝘆 𝟯𝟲/𝟭𝟬𝟬 ✅ | 𝟲𝟰 𝗺𝗼𝗿𝗲 𝘁𝗼 𝗴𝗼! #100DaysOfCode #LeetCode #LinkedList #Recursion #DataStructures #CodingInterview #SoftwareEngineer #Java #Algorithms #Programming

🚀 Day 57 of #100DaysOfCode Today’s problem was a clean and classic two-pointer exercise — 🔁 LeetCode 344: Reverse String Simple on the surface, but a great reminder of in-place algorithms and pointer manipulation. 📌 Problem Summary You’re given a character array s. Your task is to reverse the array in-place, using O(1) extra space. 🧠 Approach Used: Two Pointers ✔️ Initialize: left = 0 right = s.length - 1 ✔️ Swap characters while left < right, then move pointers inward. This ensures: No extra memory Linear traversal Clean and readable logic ⚙️ Complexity Analysis ⏱ Time Complexity: O(n) 💾 Space Complexity: O(1) (in-place) ✔️ 477 / 477 test cases passed 🚀 Runtime: 0 ms (Beats 100%) 🔥 Key Learning Even the simplest problems reinforce core fundamentals: Two-pointer technique In-place operations Space optimization Mastering basics = dominating harder problems later 💪 Onward to Day 58 🚀 #100DaysOfCode #LeetCode #ReverseString #TwoPointers #Java #DSA #ProblemSolving #CodingJourney #Consistency

🔥 Day 305 – Daily DSA Challenge! 🔥 Problem: 📦 Subsets (Power Set) Given an integer array nums of unique elements, return all possible subsets (the power set). 💡 Key Insights: 🔹 Every element has two choices → include it or exclude it. 🔹 The total number of subsets for n elements is 2ⁿ. 🔹 Backtracking helps explore all possibilities in a clean, structured way. 🔹 Add the current subset to the result at every recursion level. 🔹 Move forward using i + 1 to avoid reusing elements. ⚡ Optimized Plan: ✅ Start with an empty subset ✅ Use backtracking to build subsets incrementally ✅ Add the current subset to results before branching further ✅ Try including each remaining element one by one ✅ Backtrack after exploring each choice ✅ Time Complexity: O(2ⁿ) ✅ Space Complexity: O(n) (recursion depth) 💬 Challenge for you: 1️⃣ How would this change if nums contained duplicate elements? 2️⃣ Can you solve this using bit masking instead of recursion? 3️⃣ How would you generate subsets of exactly k elements? #DSA #Day305 #LeetCode #Backtracking #Recursion #PowerSet #Java #ProblemSolving #KeepCoding #100DaysOfCode

Day 7 of Daily DSA 🚀 Solved LeetCode 238: Product of Array Except Self ✅ 🔍 Approach: Built the solution using prefix and suffix products. First pass stores left-side products in the result array Second pass multiplies them with right-side products using a single variable No division used, and handled edge cases like zeros efficiently. ⏱ Complexity: • Time: O(n) • Space: O(1) extra space (output array excluded) 📊 LeetCode Stats: • Runtime: 2 ms (Beats 94.19%) • Memory: 72.23 MB This problem is a great example of how space optimization + traversal logic can turn a seemingly tricky problem into a clean, interview-ready solution. #DSA #LeetCode #Java #Arrays #PrefixSum #ProblemSolving #Consistency

Day 49/100 – LeetCode Challenge ✅ Problem: Maximum Sum Triconic Array Difficulty: Hard Language: Java Approach: Three-Pointer Expansion with Prefix/Suffix Optimization Time Complexity: O(n²) in worst case Space Complexity: O(n) Key Insight: Find trionic subarray with maximum sum: increasing → decreasing → increasing. For each middle peak a, expand left for decreasing segment and right for second increasing segment. Track maximum sum across all possible trionic subarrays. Solution Brief: Used nested loops to try each possible peak position. For each peak, expanded left while decreasing, right while increasing. Tracked maximum sum with proper handling of edge cases and large numbers (used long). Optimizing sum calculation for complex array patterns #LeetCode #Day49 #100DaysOfCode #Array #Java #Algorithm #CodingChallenge #ProblemSolving #MaxSumTriconicArray #HardProblem #ThreePointer #Subarray #Optimization #DSA

Day 9 – DSA Journey | Arrays 🚀 Today’s problem helped me understand backtracking with re-use of elements 🔁 and how recursion explores all valid combinations. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • ➕ Combination Sum 🔹 Combination Sum 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • 🔁 Used backtracking to build combinations • 🎯 Reduced the remaining target at each step • ♻️ Reused the same element by passing the current index again • 📌 Stored a valid path only when the remaining target becomes zero 𝐇𝐨𝐰 𝐢𝐭 𝐖𝐨𝐫𝐤𝐬 • ➡️ Start from a given index to avoid duplicate combinations • ➕ Add the current number to the path • 🔽 Recurse with reduced remaining sum • ⏪ Backtrack by removing the last added number 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • 🧠 Backtracking explores all valid paths systematically • ♻️ Passing the same index allows unlimited reuse of elements • 🎯 Base conditions control recursion flow • 🧹 Clean backtracking keeps the solution correct 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • ⏱ Time: Exponential (depends on number of combinations) • 📦 Space: O(target) (recursion depth + path) 🧠 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Backtracking isn’t about speed — It’s about exploring all possibilities correctly 🔍 On to Day 10 🔁🚀 #DSA #Arrays #Backtracking #Recursion #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

🚀 Day 11/30 – Working with Numbers Without Converting to Strings Today’s problem involved checking whether a given integer is a palindrome. While one straightforward approach would be converting the number into a string and reversing it, I chose to solve it mathematically — by reversing the digits of the number itself. 💡 Approach Immediately return false for negative numbers Store the original number Reverse the digits using modulo (% 10) and division (/ 10) Compare the reversed number with the original This avoids unnecessary string conversion and keeps the logic purely numerical. 📊 Performance ✅ All test cases passed ⚡ Efficient runtime ⏱ O(log₁₀ n) time complexity 📦 O(1) space complexity 📚 Key Takeaway Sometimes the better solution isn’t the easiest one — it’s the one that respects constraints and demonstrates deeper understanding of number manipulation. Day 11 complete. Building stronger fundamentals, one problem at a time. #Day11 #30DaysOfCode #LeetCode #Java #Algorithms #ProblemSolving #CodingJourney #SoftwareEngineering #Consistency #TechGrowth

𝗗𝗮𝘆 𝟯𝟵/𝟭𝟬𝟬 | 𝗥𝗲𝘃𝗲𝗿𝘀𝗲 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁 𝗜𝗜 Day 39 ✅ — Reverse with precision. 𝗧𝗼𝗱𝗮𝘆'𝘀 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: ✅ 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 #𝟵𝟮: Reverse Linked List II (Medium) 𝗪𝗵𝗮𝘁 𝗖𝗹𝗶𝗰𝗸𝗲𝗱: Reverse a linked list between positions left and right. Not the entire list—just a specific portion. Day 31: Reversed entire list. Day 39: Reverse only a section, in one pass. The trick? Dummy node + careful pointer manipulation. Navigate to position left-1, then reverse nodes in-place by repeatedly moving the next node to the front. 𝗠𝘆 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵: 👉 Use dummy node to handle edge cases 👉 Navigate to node before left position 👉 Reverse nodes from left to right using pointer manipulation 👉 Reconnect the reversed section Time: O(n), Space: O(1) 𝗠𝘆 𝗥𝗲𝗮𝗹𝗶𝘇𝗮𝘁𝗶𝗼𝗻: Ten linked list problems. This one built directly on Day 31's reversal logic but added precision control. The dummy node pattern keeps proving its value—simplifies edge cases every time. 𝗖𝗼𝗱𝗲:🔗 https://lnkd.in/gpYMzgJT 𝗗𝗮𝘆 𝟯𝟵/𝟭𝟬𝟬 ✅ | 𝟲𝟭 𝗺𝗼𝗿𝗲 𝘁𝗼 𝗴𝗼! #100DaysOfCode #LeetCode #LinkedList #PointerManipulation #DataStructures #CodingInterview #SoftwareEngineer #Java #Algorithms #MediumLevel #Programming #InPlaceAlgorithm