Max Product Subarray on LeetCode with Dynamic Programming

Day 36 of My DSA Journey Today I solved LeetCode 150 – Evaluate Reverse Polish Notation (RPN) on LeetCode. 📌 Problem Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are: +, -, *, / Each operand may be an integer. Example: Input: ["2","1","+","3","*"] Output: 9 Explanation: (2 + 1) * 3 = 9 🧠 Approach – Stack This problem is a perfect application of the Stack data structure. Steps I followed: • Traverse the tokens array. • If the element is a number → push it onto the stack. • If it is an operator: Pop the top two elements (a and b) Perform the operation (a operator b) Push the result back into the stack • At the end, the stack contains the final result. ⏱ Time Complexity: O(n) — We process each token once 📦 Space Complexity: O(n) — Stack to store operands 💡 Key Learnings ✔ Understanding Reverse Polish Notation (Postfix Expression) ✔ Applying stack for expression evaluation ✔ Handling operator precedence implicitly using stack This problem connects DSA with compiler/interpreter concepts, which makes it even more interesting 🚀 Consistency continues — improving every day 💪 #100DaysOfCode #DSA #Stack #LeetCode #Java #ProblemSolving #CodingJourney #DeveloperJourney #Programming #SoftwareEngineering

🚀 Day 88 – DSA Journey | Binary Tree Postorder Traversal Continuing my daily DSA practice, today I tackled one of the trickier tree traversals using an iterative approach. 📌 Problem Practiced: Binary Tree Postorder Traversal (LeetCode 145) 🔍 Problem Idea: Traverse a binary tree in postorder — Left → Right → Root — and return the node values. 💡 Key Insight: Postorder traversal is not straightforward iteratively. A clever trick is to reverse a modified preorder traversal (Root → Right → Left) to achieve the correct order. 📌 Approach Used: • Use a stack to process nodes • Traverse in Root → Right → Left order • Insert elements at the beginning of the result list • This effectively reverses the order to get Left → Right → Root 📌 Concepts Strengthened: • Tree traversal (Postorder) • Stack usage • Iterative traversal tricks • Reversing traversal logic ⏱️ Time Complexity: O(n) 📦 Space Complexity: O(n) 🔥 Today’s takeaway: Sometimes solving a problem becomes easier when you reverse the perspective — small tricks can simplify complex logic. On to Day 89! 🚀 #Day88 #DSAJourney #LeetCode #BinaryTree #Stack #Java #ProblemSolving #Coding #LearningInPublic #Consistency

Day 32/50 – LeetCode Challenge 🧩 Problem #416 – Partition Equal Subset Sum Today’s problem focused on determining whether an array can be divided into two subsets with equal sum, which is a classic Dynamic Programming (Subset Sum) problem. 📌 Problem Summary: Given an array of integers, check if it can be partitioned into two subsets such that their sums are equal. 🔍 Approach Used ✔ First calculated the total sum of the array ✔ If the sum is odd → not possible to divide equally ✔ Converted the problem into: Can we find a subset with sum = total / 2 ? ✔ Used a set (DP approach) to store all possible sums ✔ Iteratively built new sums by adding each number ✔ Checked if the target sum exists ⏱ Time Complexity: O(n × target) 📦 Space Complexity: O(target) 💡 Key Learning ✔ Converting problems into Subset Sum pattern ✔ Using Dynamic Programming with sets ✔ Thinking in terms of possibility instead of brute force ✔ Recognizing important DP patterns This problem helped me understand how to simplify complex problems into familiar patterns. Consistency builds strong problem-solving intuition 🚀 🔗 Problem Link: https://lnkd.in/gCRhSyaz #50DaysOfLeetCode #LeetCode #DSA #DynamicProgramming #SubsetSum #ProblemSolving #CodingJourney #FutureAIEngineer #Consistency

🚀 LeetCode Challenge 16/50 💡 Approach: Dynamic Programming (Bottom-Up) A pure recursion approach explodes to O(2ⁿ) — exponential! By storing subproblem results in a DP array, we decode the entire string in a single linear pass. 🔍 Key Insight: → dp[i] = number of ways to decode first i characters → Single digit (1-9): dp[i] += dp[i-1] → Two digits (10-26): dp[i] += dp[i-2] → '0' alone is always invalid — handle carefully! → Build up the answer from base cases 📈 Complexity: ❌ Recursion (no memo) → O(2ⁿ) Time ✅ Dynamic Programming → O(n) Time, O(n) Space 🚀 Optimized DP → O(n) Time, O(1) Space (only 2 variables needed!) DP is not just an algorithm — it's a mindset. Break the problem, store the result, build the solution! 🧩 #LeetCode #DSA #DynamicProgramming #Java #ADA #PBL2 #LeetCodeChallenge #Day16of50 #CodingJourney #ComputerEngineering #AlgorithmDesign #DecodeWays

🚀 Day 14 / 50 – Wild Coding Kickoff Today’s focus was on computing the square root of a number without using built-in functions, and understanding how precision and data types impact the solution. 💡 Key Insight: Integer Division in Java int result = 9 / 2; System.out.println(result); // Output: 4 Java performs integer division when both operands are integers The fractional part is discarded, not rounded To get accurate results in calculations: double result = (double) 9 / 2; // 4.5 ⚡ Approach Used: Newton’s Method Instead of brute force or binary search, I implemented Newton’s Method, which converges faster to the square root. 🧠 Idea: Start with an initial guess Continuously improve it using an average-based formula Stop when the value stabilizes 🔍 Why this works Uses integer-safe division (n / x) to avoid overflow Each iteration brings the guess closer to the actual square root Efficient and avoids floating-point inaccuracies ⏱ Complexity Time: ~ O(log n) (fast convergence) Space: O(1) 🎯 Takeaway Understanding fundamentals like integer division combined with applying efficient algorithms like Newton’s Method leads to both correct and optimized solutions. #Day14 #50DaysOfCode #WildCodingKickoff #Java #DSA #SoftwareEngineering #CodingJourney #ProblemSolving #Algorithms

🚀 Day 76 – DSA Journey | Remove Adjacent Duplicates using Stack Continuing my daily DSA practice, today I solved a problem that highlights how stacks can simplify string manipulation. 📌 Problem Practiced: Remove All Adjacent Duplicates in String (LeetCode 1047) 🔍 Problem Idea: Given a string, repeatedly remove adjacent duplicate characters until no more duplicates remain. The final result is guaranteed to be unique. 💡 Key Insight: A stack helps efficiently track characters and remove duplicates instantly when the current character matches the top of the stack. 📌 Approach Used: • Traverse the string from left to right • Push characters onto the stack • If the current character matches the top → pop (remove duplicate) • Continue this process until the string is fully processed • Build the final string from the stack 📌 Concepts Strengthened: • Stack data structure • String manipulation • Pattern removal problems • Efficient traversal techniques ⏱️ Time Complexity: O(n) 📦 Space Complexity: O(n) 🔥 Today’s takeaway: Stacks are powerful for handling adjacent comparisons and undo-type operations in strings. On to Day 77! 🚀 #Day76 #DSAJourney #LeetCode #Stack #Java #ProblemSolving #Coding #LearningInPublic #Consistency

Day 100: Consistency, Growth, and a Milestone 💯 Problem 3740: Minimum Distance Between Three Equal Elements I Today marks 100 days of continuous problem-solving. While the number is just a marker, the real value has been the daily discipline of opening the IDE and tackling whatever challenge LeetCode throws my way. The Strategy: • Frequency Grouping: I used a HashMap to store a list of indices for every unique number in the array. This allowed me to isolate potential triplets instantly. • Sliding Window Logic: For any number appearing three or more times, I looked at a sliding window of three consecutive indices (i,i+1,i+2). • The Formula: Through testing, I identified that the minimum distance between three equal elements can be derived from the span between the first and third occurrence: (index of 3rd - index of 1st) * 2. • Optimization: By iterating through the pre-grouped index lists, I kept the solution efficient and clean. Reflecting on these 100 days, I’ve moved from basic simulations to complex optimizations like Square Root Decomposition and 3D DP. The goal isn't to stop here—it's to keep building, keep optimizing, and keep growing. 🚀 #LeetCode #Java #Algorithms #DataStructures #100DaysOfCode #Consistency #ProblemSolving #DailyCode

Day 59 of My DSA Journey Today I solved LeetCode 762 – Prime Number of Set Bits in Binary Representation on . 📌 Problem Given two integers "left" and "right", count how many numbers in this range have a prime number of set bits (1s) in their binary representation. Example: Input: "left = 6, right = 10" Output: "4" --- 🧠 Approach – Bit Manipulation + Prime Check Steps I followed: • For each number in range "[left, right]": - Count number of set bits (1s) using bit manipulation ("n & 1", "n >> 1") • Check if the count is a prime number - Used a predefined list of primes: "{2,3,5,7,11,13,17,19}" • If yes → increment the answer --- ⏱ Time Complexity: "O(n * log n)" Where "n = right - left + 1" (each number takes log n for bit counting) 📦 Space Complexity: "O(1)" — Constant extra space --- 💡 Key Learnings ✔ Practicing Bit Manipulation concepts ✔ Efficiently counting set bits ✔ Combining multiple concepts (bits + prime check) 👉 This problem shows how combining simple ideas can solve interesting problems 🚀 --- Consistency continues — learning something new every day 💪🔥 #100DaysOfCode #DSA #BitManipulation #Math #LeetCode #Java #ProblemSolving #CodingJourney #DeveloperJourney #Programming #SoftwareEngineering

🚀 Day 87 – DSA Journey | Binary Tree Preorder Traversal Continuing my daily DSA practice, today I explored another important tree traversal technique using an iterative approach. 📌 Problem Practiced: Binary Tree Preorder Traversal (LeetCode 144) 🔍 Problem Idea: Traverse a binary tree in preorder — Root → Left → Right — and return the sequence of node values. 💡 Key Insight: Using a stack, we can simulate recursion and control the traversal order. By pushing the right child before the left, we ensure the left subtree is processed first. 📌 Approach Used: • Use a stack and start with the root node • Pop node, process (add to result) • Push right child first, then left child • Repeat until stack is empty 📌 Concepts Strengthened: • Tree traversal (Preorder) • Stack usage • Iterative vs recursive approach • Order control in traversal ⏱️ Time Complexity: O(n) 📦 Space Complexity: O(n) 🔥 Today’s takeaway: Understanding traversal order and stack behavior makes it easier to convert recursive tree problems into iterative ones. On to Day 88! 🚀 #Day87 #DSAJourney #LeetCode #BinaryTree #Stack #Java #ProblemSolving #Coding #LearningInPublic #Consistency

Day 24 of #100DaysOfCode I stared at this problem for 40 minutes trying every possible target value. Then one insight — borrowed from basic statistics — made it click instantly. 🧩 The Problem: Minimum Operations to Make a Uni-Value Grid (LeetCode 2033 — Medium) Given a 2D grid and a fixed step value x, transform every element to the same value using the minimum number of add/subtract operations. My first instinct? Try every possible target. Loop through everything. Classic overthinking. 😅 💡 The Key Insight — Why the Median? The median minimizes the sum of absolute differences. This is a well-known statistics fact — and it maps perfectly to this problem. Instead of brute-forcing every target, the strategy is simple: → Flatten the 2D grid into a 1D array → Sort it → Pick the middle element (median) as the target → Count total operations using the absolute difference divided by x No guessing. No unnecessary loops. Just math doing the heavy lifting. ⚠️ The Constraint Check Nobody Talks About Before applying any operations — check if all elements share the same remainder when divided by x. If they don't, it's mathematically impossible to make the grid uni-value. Return -1 immediately and save the computation entirely. This "fail fast" mindset is just as important as the algorithm itself. 📈 Complexity Breakdown → Flatten + Sort → O(n log n) → Single pass to count operations → O(n) → Space → O(n) for the flattened array Simple, clean, and efficient. 🧠 What This Problem Reinforced ✅ Greedy thinking with median optimization ✅ Handle impossible cases before computation — fail fast ✅ Transform 2D problems into simpler 1D forms ✅ Let math do the heavy lifting before writing a single loop The best solutions often come from asking: "What does math already know about this?" On to the next challenge 💪 👇 What's a problem where a simple insight saved you from overcomplicating things? Drop it in the comments — would love to learn from your experience! #100DaysOfCode #LeetCode #DSA #Java #ProblemSolving #CodingJourney #SoftwareEngineering #Programming