Maximizing Matrix Product with Dual DP Tables

#100DaysOfLeetcode journey 🚀 Day 45/100 — Tracking Extremes in Matrix Paths! Today’s Problem: 1594. Maximum Non-negative Product in a Matrix 🔹 The Goal: Find the path from the top-left to the bottom-right of a grid that maximizes the product of all visited cells. If the max product is negative, return -1. 🔹 The Insight: This isn't your typical "Maximum Path Sum" problem. Because negative numbers exist in the grid, the "minimum" product at one step could become the "maximum" product at the next (e.g., $-10 \times -2 = 20$). To solve this, you must maintain dual states at every cell: the highest possible product and the lowest possible product. 🔹 The Logic: Dual DP Tables: I maintained two matrices to track the max and min values encountered so far. Sign Awareness: When multiplying by a negative number, the previous minimum becomes the candidate for the new maximum. Precision Management: With path lengths up to 30, products can exceed $10^{18}$. I used long to keep calculations accurate and only applied the modulo at the very end to ensure the mathematical integrity of the maximum search. ✨ Achievement: Day 45! Successfully applied multi-state Dynamic Programming to a multiplicative path problem. It’s a great reminder that "optimal substructure" sometimes requires tracking more than just the current best answer. 🔍 Steps followed: ✔ Boundary Initialization: Set up cumulative products for the first row and column. ✔ State Propagation: Used a single pass to update both max and min boundaries. ✔ Negative Capping: Implemented the return requirement for paths that only result in negative values. 🔧 Complexity Analysis: Time Complexity: $O(M \times N)$ Space Complexity: $O(M \times N)$ 53 days down! Every problem is a lesson in how to manage state transitions more effectively. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #DynamicProgramming #MatrixAlgorithms #Optimization #Day45

#100DaysOfLeetcode journey 🚀 🚀 Day 68/100 — Numerical Symmetry & Mirror Distances! Today’s Problem: Mirror Distance of an Integer 🔹 The Goal: Define the "Mirror Distance" of a number $n$ as the absolute difference between the number and its digit-reversal. For example, if $n = 123$, the mirror is $321$, and the distance is $|123 - 321| = 198$. 🔹 The Insight: This is a fundamental exercise in Digit Manipulation. Reversing a number isn't just a string operation; it’s an arithmetic process. By using the modulo operator (% 10) to extract the last digit and integer division (/ 10) to shift the decimal place, we can reconstruct the mirror image in a single pass. 🔹 The Logic: Arithmetic Reversal: I used a while-loop to peel off digits and build the reversed integer. This naturally handles the "omit leading zeros" rule (e.g., reversing $120$ results in $21$ because $0 \times 10 + 2 \times 1 + 1$ arithmetic logic). Absolute Variance: The final result is simply the absolute magnitude of the gap between the two values. Negative Handling: I ensured the logic remains robust for negative integers by reversing the absolute value and reapplying the sign. ✨ Achievement: Day 68! We are well into the second half of the challenge. Today’s solution highlights how core arithmetic can replace heavy string parsing for better performance and lower memory overhead. 🔍 Steps followed: ✔ Digit Extraction: Peeling digits using remainder operations. ✔ Numerical Reconstruction: Building the reversed value through decimal shifting. ✔ Error Guarding: Managed potential sign issues to ensure a valid absolute distance. 🔧 The Stats: Time Complexity: $O(\log_{10} n)$ Space Complexity: $O(1)$ 68 days down! The journey into algorithmic mastery continues. Let's keep the momentum! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #MathAlgorithms #Logic #Optimization #Day68

#100DaysOfLeetcode journey 🚀 Day 44/100 — Avoiding Division in Modular Arithmetic! Today’s Problem: 2906. Construct Product Matrix 🔹 The Goal: Construct a matrix where each element is the product of every other element in the grid, all under a specific modulo (12345). 🔹 The Insight: Usually, a product-except-self problem is solved by dividing the total product by the current element. However, when working with a non-prime modulo like 12345, division is risky—if the divisor and modulo share a common factor, the modular inverse doesn't exist! 🔹 The Logic: Prefix/Suffix Strategy: To bypass division, we use two passes. First Pass (Prefixes): We calculate the cumulative product of all elements encountered before the current cell. Second Pass (Suffixes): We sweep backward, multiplying our prefixes by the cumulative product of all elements appearing after the current cell. Efficiency: This allows us to calculate the result in $O(N \cdot M)$ time while keeping memory usage at $O(1)$ auxiliary space. ✨ Achievement: Day 44! Successfully implemented a robust product-array algorithm that respects the limitations of modular arithmetic. It’s a great reminder that "division" in the world of remainders is often more complex than it looks! 🔍 Steps followed: ✔ Two-Pass Scan: Implemented forward and backward accumulation to avoid the $O(N^2)$ brute force. ✔ Modular Precision: Applied the modulo at every multiplication step to prevent overflow. ✔ Space Optimization: Reused the output matrix to store intermediate prefix results. 🔧 Complexity Analysis: Time Complexity: $O(n \times m)$ Space Complexity: $O(1)$ (Auxiliary) 54 days in! Understanding when to replace standard operators with modular-safe patterns is a major step in numerical algorithm design. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #MatrixAlgorithms #PrefixSum #Optimization #Day44

#100DaysOfLeetcode journey 🚀 Day 67/100 — Optimizing Circular Proximity! Today’s Problem: Minimum Circular Distance to Matching Elements 🔹 The Goal: Given an array that "wraps around," find the shortest path from a specific index to any other occurrence of the same value. 🔹 The Insight: A naive search for every query would be $O(Q \times N)$, which is catastrophic for large datasets. The breakthrough here is Spatial Indexing. By pre-grouping the indices of every value and keeping them sorted, we transform a global search into a localized neighbor check. 🔹 The Logic: Value-to-Index Mapping: I used a HashMap to store sorted lists of indices for each unique number. Logarithmic Search: Using binarySearch, I instantly located the query index within its value-group. The "Circular Sandwich": Because the indices are sorted, the closest matching elements are always the immediate neighbors in the list. By checking the left, the right, and the wrap-around (first/last) elements, we guarantee the global minimum in $O(\log N)$ time. ✨ Achievement: Day 67! Successfully applied pre-computation and binary search to optimize a spatial query problem. Understanding that the "closest" element in a circular topology is always an adjacent neighbor in the sorted index space is a powerful shortcut for range-based problems. 🔍 Steps followed: ✔ Map Pre-processing: Clustered indices for constant-time value lookups. ✔ Binary Search Integration: Optimized neighbor identification to logarithmic time. ✔ Modular Distance Logic: Correctly handled the $N - \text{linearDist}$ calculation for circular boundaries. 🔧 Complexity Analysis: Time Complexity: $O(N + Q \log N)$ Space Complexity: $O(N)$ 67 days down! The logic is getting faster, and the problems are getting more interesting. Let's keep the streak alive! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #ArrayAlgorithms #BinarySearch #Optimization #Day67

#100DaysOfLeetcode journey 🚀 Day 64/100 — Linear Search & Absolute Minimization! Today’s Problem: 1848. Minimum Distance to the Target Element 🔹 The Goal: Given an array, a target value, and a starting index, find the index $i$ where $nums[i] == target$ such that the absolute distance $|i - start|$ is minimized. 🔹 The Insight: While many distance-based problems involve complex sorting or two-pointer strategies, this one is beautifully straightforward. Because we need to find the absolute minimum distance, a single linear scan is all it takes to evaluate every potential candidate and keep track of the closest one. 🔹 The Logic: Exhaustive Search: We iterate through the entire array to ensure we don't miss any occurrences of the target. Distance Tracking: For every match, we calculate the absolute difference between the current index and our start point. Running Minimum: We maintain a minDistance variable that gets updated whenever a "closer" target is discovered. ✨ Achievement: Day 64! Only 36 days remaining until the century mark. Today was a great reminder that not every "Hard" problem requires a complex data structure—sometimes, the most robust solution is a clean, well-implemented linear scan. 🔍 Steps followed: ✔ Single-Pass Scan: Maintained a strictly $O(N)$ runtime. ✔ Distance Logic: Used Math.abs to handle indices on both the left and right sides of the start point. ✔ Constant Space: Kept the memory footprint at $O(1)$. 🔧 Complexity Analysis: Time Complexity: $O(N)$ Space Complexity: $O(1)$ 97 days down! The finish line is officially in sight. Let's finish these final three days with the same consistency that got us here! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #LinearSearch #Optimization #Algorithms #Day64

#100DaysOfLeetcode journey 🚀 Day 66/100 — Optimizing Circular Proximity! Today’s Problem: Minimum Circular Distance to Matching Elements 🔹 The Goal: Given an array that "wraps around," find the shortest path from a specific index to any other occurrence of the same value. 🔹 The Insight: A naive search for every query would be $O(Q \times N)$, which is catastrophic for large datasets. The breakthrough here is Spatial Indexing. By pre-grouping the indices of every value and keeping them sorted, we transform a global search into a localized neighbor check. 🔹 The Logic: Value-to-Index Mapping: I used a HashMap to store sorted lists of indices for each unique number. Logarithmic Search: Using binarySearch, I instantly located the query index within its value-group. The "Circular Sandwich": Because the indices are sorted, the closest matching elements are always the immediate neighbors in the list. By checking the left, the right, and the wrap-around (first/last) elements, we guarantee the global minimum in $O(\log N)$ time. ✨ Achievement: Day 66! Successfully applied pre-computation and binary search to optimize a spatial query problem. Understanding that the "closest" element in a circular topology is always an adjacent neighbor in the sorted index space is a powerful shortcut for range-based problems. 🔍 Steps followed: ✔ Map Pre-processing: Clustered indices for constant-time value lookups. ✔ Binary Search Integration: Optimized neighbor identification to logarithmic time. ✔ Modular Distance Logic: Correctly handled the $N - \text{linearDist}$ calculation for circular boundaries. 🔧 Complexity Analysis: Time Complexity: $O(N + Q \log N)$ Space Complexity: $O(N)$ 67 days down! The logic is getting faster, and the problems are getting more interesting. Let's keep the streak alive! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #ArrayAlgorithms #BinarySearch #Optimization #Day66

#100DaysOfLeetcode journey 🚀 Day 66/100 — Thinking in Circles! Today’s Problem: 2515. Shortest Distance to Target String in a Circular Array 🔹 The Goal: Find the shortest path between a starting index and a target string in an array that "wraps around" at the ends. You can move either clockwise or counter-clockwise. 🔹 The Insight: This is a beautiful exercise in Radial Geometry applied to a 1D structure. When you connect the ends of an array, the distance between any two points $i$ and $j$ isn't just $|i - j|$. There's a hidden path that goes through the "boundary" of the array. The shortest path is always the minimum of the direct linear distance and the "complement" distance ($N - \text{Linear Distance}$). 🔹 The Logic: Single Pass Scan: Instead of complex BFS, we just need to identify where the target lives. Dual-Distance Logic: For every match found, we evaluate the two possible routes: The "Standard" route (staying within the array bounds). The "Circular" route (jumping from index 0 to $N-1$ or vice versa). Constant Space: The entire check happens in $O(N)$ time with $O(1)$ memory. ✨ Achievement: Day 66! Moving from complex bitwise validation and string parsing into circular array logic. It’s a great reminder that understanding the topology of your data structure (whether it's a line, a circle, or a grid) is the first step toward optimization. 🔍 Steps followed: ✔ Linear Traversal: Evaluated every potential target location. ✔ Modular Arithmetic: Simplified circular transitions using absolute differences. ✔ Optimal Minimum: Tracked the global minimum across all valid occurrences. 🔧 Complexity Analysis: Time Complexity: $O(n)$ Space Complexity: $O(1)$ 66 days down! The finish line is coming into focus. Let’s keep the momentum! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #ArrayAlgorithms #CircularArrays #Optimization #Day66

#100DaysOfLeetcode journey 🚀 Day 50/100 — The 50% Milestone & Parity Invariants! Today’s Problem: 2840. Check if Strings Can be Made Equal With Operations II 🔹 The Goal: I’ve officially reached the halfway point of the 100-day challenge! Today’s task was to determine if two strings of length $n$ can be made identical by swapping characters whose indices have the same parity (even with even, odd with odd). 🔹 The Insight: This is a classic "Track-Based" permutation problem. When you can only swap indices with an even difference ($j - i = 2, 4, \dots$), you aren't really dealing with one string—you're dealing with two independent character sets living in parallel. Characters at even positions can never migrate to odd positions, no matter how many swaps you perform. 🔹 The Logic: Decoupling: I split the character counts into two tracks: Even and Odd. Frequency Matching: Instead of simulating swaps (which would be $O(n^2)$), I used frequency arrays to verify if the "ingredients" for each track were identical between both strings. Efficiency: This reduction turns a permutation problem into a single-pass $O(n)$ validation with constant $O(1)$ auxiliary space. ✨ Achievement: Day 50! Crossing the halfway mark with a 100% efficient solution. It’s a powerful reminder that identifying what cannot change (invariants) is often the fastest way to solve what can change (permutations). 🔍 Steps followed: ✔ Parity Isolation: Used modulo logic to bin characters into even and odd frequency maps. ✔ Linear Synchronization: Processed both strings in a single loop to minimize cache misses. ✔ Array Comparison: Used Arrays.equals for a constant-time check against the 26-character alphabet. 🔧 Complexity Analysis: Time Complexity: $O(n)$ Space Complexity: $O(1)$ 50 days down, 50 to go. The momentum is undeniable. Let's finish the second half! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #StringAlgorithms #Parity #Optimization #Day50 #HalfwayMark

#100DaysOfLeetcode journey 🚀 Day 47/100 — Mathematical Symmetry in Matrix Rotations! Today’s Problem: 48. Rotate Image 🔹 The Goal: Rotate an $n \times n$ 2D matrix (representing an image) 90 degrees clockwise. The catch? It must be done in-place, meaning we can't allocate a second matrix to simplify the move. 🔹 The Insight: At first glance, moving every element to its new $(x, y)$ coordinate feels like a complex mapping nightmare. However, there is a beautiful geometric shortcut. A 90-degree clockwise rotation is equivalent to two simple operations: Transpose: Flip the matrix over its main diagonal. Reverse: Flip each row horizontally. 🔹 The Logic: In-Place Transpose: By swapping matrix[i][j] with matrix[j][i], we turn rows into columns. Row Reversal: Once transposed, reversing the elements in each row completes the clockwise shift. Efficiency: This approach uses $O(1)$ auxiliary space and $O(n^2)$ time, touching each element only twice. ✨ Achievement: Day 47! Successfully replaced a complex coordinate-mapping problem with a clean, two-step symmetry transformation. It’s a perfect example of how breaking a large problem into two fundamental geometric steps makes the code much more readable and easier to debug. 🔍 Steps followed: ✔ Diagonal Swapping: Implemented the transpose logic using nested loops with a j = i starting constraint. ✔ Symmetric Row Reversal: Used the two-pointer approach to flip rows in-place. ✔ Zero-Memory Footprint: Verified that no extra arrays were used, maintaining strict space efficiency. 🔧 Complexity Analysis: Time Complexity: $O(n^2)$ Space Complexity: $O(1)$ 47 days in! Sometimes the shortest path to a solution isn't a straight line—it's a flip and a reverse. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #MatrixAlgorithms #Geometry #Optimization #Day47

#100DaysOfLeetcode journey 🚀 Day 55/100 — Reversing Diagonal Transpositions! Today’s Problem: 2075. Decode the Slanted Ciphertext 🔹 The Goal: Decipher a string that was written diagonally into a matrix but read out row-by-row. We need to extract the original message and handle any padding spaces correctly. 🔹 The Insight: This is a classic "Coordinate Mapping" problem. When data is transformed from one traversal order (diagonal) to another (row-major), the key is to find the mathematical relationship between the indices. If a character is at row $i$ and starts at diagonal $j$, its column index is always $i + j$. 🔹 The Logic: Grid Mapping: By calculating cols = length / rows, we can treat the flat string as a 2D matrix without actually allocating any extra 2D space. Diagonal Scanning: I used a nested loop where the outer loop selects the starting "offset" (top-row column) and the inner loop moves down the diagonal. Precision Trimming: Since the cipher pads the matrix with spaces, the final step requires a backward-pass to remove trailing blanks while preserving spaces that were part of the original message. ✨ Achievement: Day 55! Successfully implemented a linear-time $O(N)$ decoding algorithm. Moving from backtracking and combinatorial searches into geometric string manipulation is a great way to maintain a diverse problem-solving toolkit. 🔍 Steps followed: ✔ Dimension Derivation: Computed the matrix footprint based on the input constraints. ✔ Index Calculation: Leveraged i * cols + (j + i) to access characters directly from the 1D string. ✔ In-Place Cleanup: Managed result trimming to ensure accuracy against the problem's whitespace rules. 🔧 Complexity Analysis: Time Complexity: $O(n)$ Space Complexity: $O(n)$ 83 days in! Only 17 more to go. The finish line is closer than ever! 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #StringAlgorithms #MatrixManipulation #Algorithms #Day55