From Brute Force to Ultra-Optimized: Maximum Rectangle Area Problem

🚀 Day 61 of #100DaysOfLeetCodeHard — LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers (Hard) My Submission:https://lnkd.in/gdAy6ski Today’s problem was a 5D Dynamic Programming challenge that tested both spatial intuition and state management in recursion. The task was to minimize the total distance required to type a given string on a 2D keyboard using two fingers. Each key has a coordinate on a 6-column grid, and each finger can independently move across the board. 💡 Approach: I defined the state as: dp[ind][x1][y1][x2][y2] → the minimum cost to type from index ind when first finger is at (x1, y1) second finger is at (x2, y2) At each step, I explored both possibilities: Typing the next letter with the first finger, Typing it with the second finger, and recursively computed the minimal total cost. 📘 Key Concepts: Multi-dimensional DP with recursion + memoization Manhattan distance calculation Handling base conditions and free initial finger placement ⏱️ Time Complexity: ~O(n × 6⁴) (optimized with memoization) 💾 Space Complexity: O(n × 6⁴) This problem was one of the most state-heavy DP problems I’ve done so far — but once the transitions clicked, it turned out to be a very elegant solution! 💪 #LeetCode #DynamicProgramming #Recursion #ProblemSolving #C++ #100DaysOfCode #LearningEveryday #CodingChallenge

🚀 Day 74 – 75 Days DSA Challenge 💻 # Today, I focused on strengthening one of the most important problem-solving techniques in algorithms - Dynamic Programming (DP). # I revised all core DP concepts and successfully solved a classic LeetCode problem: Fibonacci Number. 📘 Concepts Covered: 🔹 What is Dynamic Programming? # A technique to solve problems by breaking them into overlapping subproblems. # Uses optimal substructure and memoization/tabulation to avoid repeated work. # Helps convert exponential solutions into polynomial-time ones. 🔹 DP Approaches I Practiced: # Recursive (Top-Down) with memoization # Iterative (Bottom-Up) tabulation # Space-Optimized DP for efficient memory usage # Understanding when DP is applicable by identifying patterns and recurrence relations 🔹 Problem Solved – Fibonacci Number: # Implemented the Fibonacci series using space-optimized DP (O(n) time, O(1) space). # Observed how DP transforms a slow exponential solution into an efficient linear one. # Reinforced my understanding of subproblems, transitions, and base cases. 💡 Key Takeaway: # Dynamic Programming is not just a technique - it’s a mindset. # Today’s practice helped me become more comfortable recognizing DP patterns and building efficient solutions for complex problems. #Day74 #75DaysDSAChallenge #DynamicProgramming #DP #LeetCode #Fibonacci #Algorithms #DataStructures #ProblemSolving #CodingJourney #TechLearning #Programming

📅 October 22, 2025 🧩 Problem Solved: 🔹 Count Square Submatrices with All Ones | Array · Dynamic Programming · Medium Core Idea: We aim to count all square submatrices that contain only 1s. This can be efficiently done using a bottom-up DP approach, where each cell in the DP table represents the size of the largest square ending at that position. Approach: Create an m × n DP array initialized with zeros. For each cell (i, j) in the matrix: If matrix[i][j] == 1, then dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) his ensures that a cell contributes to a larger square only if all three neighboring squares can form a smaller one. Add dp[i][j] to the result since it represents all possible squares ending at that cell. Edge cells (first row and first column) are directly taken from the input matrix since they can only form 1×1 squares. Complexity: ⏱️ Time: O(M × N) 📦 Space: O(M × N) (or O(N) with optimization) https://lnkd.in/dJ5VcnTN 💡 Key Takeaways: The value at each DP cell is not just 0 or 1 — it represents the number of distinct squares ending there. Always think of DP[i][j] as an answer to a sub-question — here, “What’s the largest square ending at (i, j)?” This problem shows how 2D prefix relationships can simplify submatrix counting drastically. #LeetCode #100DaysOfCode #DSA #CodingJourney #Cplusplus #ProblemSolving #DynamicProgramming #TechPrep #Arrays

🚀 Day 60 of #100DaysOfLeetCodeHard — LeetCode 3725: Count Ways to Choose Coprime Integers from Rows (Hard) My Submission:https://lnkd.in/gFY6Yg_f Today’s problem was a Dynamic Programming + GCD challenge — a great exercise in combining mathematical reasoning with state-based recursion. The task was to count the number of ways to select exactly one integer from each row of a given matrix such that the GCD of all chosen integers equals 1, with results taken modulo 109+710^9 + 7109+7. 💡 Approach: I used recursive DP with memoization where each state represents: ind: current row index gcdNum: current running GCD value At each step, we iterate through all numbers in the current row and recursively compute the number of valid combinations leading to a final GCD of 1. A 2D DP array dp[ind][gcdNum] stores intermediate results to avoid recomputation. 📘 Key Concepts Used: Dynamic Programming over GCD states Modulo arithmetic for large result handling Efficient bottom-up recursion with pruning ⏱️ Time Complexity: O(n × m × log(maxValue)) 💾 Space Complexity: O(n × maxValue) This problem beautifully highlights how mathematical insight (GCD) and DP optimization come together to handle complex combinatorial counting problems. 💪 #LeetCode #DynamicProgramming #Math #GCD #ProblemSolving #C++ #100DaysOfCode #LearningEveryday #CodingChallenge

🎯 LeetCode Daily – Triangle (Day 113) Today’s problem deepened my understanding of Dynamic Programming on Triangular Grids, focusing on minimizing path sums efficiently. ✅ My Approach: 🔹 Problem – Triangle: • The goal was to find the minimum path sum from the top to the bottom of a triangle array. • Used Memoization (Top-Down DP) to recursively explore all paths while storing intermediate results to avoid redundant computations. • Implemented Tabulation (Bottom-Up DP) to build the solution iteratively starting from the last row and moving upward, computing the minimum path for each position using values from the row below. 🧠 Key Insight: This problem beautifully demonstrates the power of Dynamic Programming in optimizing recursive solutions. By transitioning from memoization to tabulation, the problem transforms from exponential recursion to an elegant linear-time solution. Recognizing overlapping subproblems and optimal substructure patterns is key to mastering DP on grids and triangles. 📊 Time Complexity: O(N²) 📦 Space Complexity: O(N²) #LeetCode #DSA #DynamicProgramming #ProblemSolving #DailyCoding #LearningInPublic #Day113

🧠 𝐔𝐧𝐝𝐞𝐫𝐬𝐭𝐚𝐧𝐝𝐢𝐧𝐠 𝐈𝐧𝐭𝐞𝐠𝐞𝐫 𝐎𝐯𝐞𝐫𝐟𝐥𝐨𝐰 𝐢𝐧 𝐂 I learned about integer overflow in C in theory, but now I’m experiencing it on a deeper level as I experiment with values that exceed the limits of short. In C, a short variable usually stores signed 16-bit integers. That means it can only represent values within a specific range. If you try to store something outside that range, it overflows. When a number gets too big to fit in memory, it “wraps around” and starts again from the lowest value, following how two’s complement works internally. So if you assign a value just beyond the maximum that a short can hold, it becomes a negative number instead of a larger positive one. This happens because of how binary arithmetic works at the bit level: ➢ The most significant bit (the highest-order bit) acts as the sign bit, and once that bit flips, the value is interpreted as negative. 𝐊𝐞𝐲 𝐭𝐚𝐤𝐞𝐚𝐰𝐚𝐲: ➢ Know the size and limits of each integer type you’re using. ➢ Use larger types (int, long, or long long) when your values might exceed the range. ➢ Consider fixed-width types like int16_t or int32_t from <stdint.h> for consistent behavior across platforms. Integer overflow isn’t just a classroom concept, it can cause real bugs and even security issues in production code if you’re not careful. #CProgramming #SoftwareEngineering #SystemsProgramming #CodingTips #ComputerScience #JuniorDeveloper #LearningInPublic

✨ Day 49 of 50 Days Challenge ✨ Solved LeetCode 115: Distinct Subsequences (Hard) 👉 Problem Statement: Given two strings s and t, return the number of distinct subsequences of s that equal t. A subsequence is formed by deleting some (or none) characters without changing the relative order of the remaining characters. 📌 Examples: Input: s = "rabbbit", t = "rabbit" Output: 3 There are 3 ways to form “rabbit” from “rabbbit”. Input: s = "babgbag", t = "bag" Output: 5 There are 5 ways to form “bag” from “babgbag”. 🔎 Approach Used: ➡️ Dynamic Programming (DP) — Space Optimized 1. Create two arrays (prev and curr) to store the count of subsequences. 2. Initialize base cases — there’s always one way to form an empty string. 3. For each character in s, compare it with each character in t: If characters match → add ways from both including and excluding it. If not → carry over the previous count. 4. Continue iterating and swap arrays to save space. ✅ Complexity Analysis: Time Complexity: O(n × m) Space Complexity: O(m) → Optimized 1D DP #50DaysChallenge #LeetCode #C++ #DynamicProgramming #Strings #Subsequences #DSA #CodingChallenge #Algorithms

🚀 Day 6 | LeetCode #152 – Maximum Product Subarray | DSA Problem Solving (Array) 💡 Problem Statement: Given an integer array nums, find the contiguous subarray that has the largest product, and return that product. This question tests your understanding of dynamic programming concepts and how to handle negative numbers effectively in array problems. --- 🧠 Example 1: Input: nums = [2,3,-2,4] Output: 6 Explanation: The subarray [2,3] gives the maximum product = 6. Example 2: Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not contiguous after the zero. --- ⚙️ Approach (Dynamic Programming): 1. Maintain two values at every index: maxProd: maximum product so far minProd: minimum product so far 2. When the current number is negative → swap maxProd and minProd. 3. Update both: maxProd = max(nums[i], maxProd * nums[i]) minProd = min(nums[i], minProd * nums[i]) 4. Keep updating the global result with maxProd.

📅 October 26, 2025 🧩 Problems Solved: 🔹 Minimum ASCII Sum for Two Strings | String, Dynamic Programming | Medium This problem is similar to LCS, but instead of length, we track the minimum ASCII cost to make the two strings equal. Recurrence: If characters match (s1[i] == s2[j]), move both indices forward; no cost is added. If characters differ, we have two options: Remove s1[i] → add ASCII(s1[i]) Remove s2[j] → add ASCII(s2[j]) Take the minimum of the two choices and store it in dp[i][j]. Bottom-up tabulation or memoization optimizes overlapping subproblems efficiently. ⏱️ Time Complexity: O(m × n) 💾 Space Complexity: O(m × n) / O(n) (optimized) https://lnkd.in/ds3PBijq 💡 Key Takeaways: • DP problems like LCS can be adapted to cost-based variations by replacing “length” with “sum” or “value.” • Always consider all removal or addition choices at each step and store minimum/maximum for memoization. #LeetCode #100DaysOfCode #DSA #CodingJourney #Cplusplus #ProblemSolving #TechPrep #Arrays #DynamicProgramming #Strings

🔄 Which Loop Runs Faster? A Performance Deep-Dive 🧩 The Puzzle Code A: for (int i = 0; i < 100; i++) for (int j = 0; j < 10; j++) Code B: for (int j = 0; j < 10; j++) for (int i = 0; i < 100; i++) Which one runs faster? ✅ The Answer: Code B Even though both run 1000 iterations, Code B is faster. Why? 💡 Key Insight: Loop Overhead Matters Code A Outer loop runs 100 times Inner loop setup happens 100 times More condition checks Code B Outer loop runs 10 times Inner loop setup occurs only 10 times Fewer condition checks 👉 Rule of Thumb: Put the loop with fewer iterations outside to reduce setup overhead. ⚠️ Real-World Twist: Arrays Flip the Story When working with arrays like int arr[100][10];, the faster version is: for (int i = 0; i < 100; i++) for (int j = 0; j < 10; j++) arr[i][j] = value; ✅ Why? Cache locality! Accessing memory sequentially (row-wise) is 10–100x faster than jumping around. 🎯 The Takeaway 🟢 Empty loops → Focus on reducing loop setup overhead ✅ Fewer outer iterations = faster execution 🟡 Array operations → Prioritize memory access patterns ✅ Row-wise (sequential) access = better cache performance 🔁 Smart Looping = Smart Programming Knowing when to optimize for overhead vs cache locality makes your code lean and lightning-fast! 💬 What optimization trick surprised you the most? 👇 Drop your thoughts below! #Programming #CProgramming #CodeOptimization #PerformanceTuning #SoftwareEngineering #TechTips #Coding #ComputerScience #AlgorithmOptimization