Optimized Matrix Traversal for Special Positions

#100DaysOfLeetcode journey 🚀 Day 26/100 — Contiguous Logic & String Invariants! Today’s Problem: 1784. Check if Binary String Has at Most One Segment of Ones 🔹 The Goal: Determine if a binary string, which notably contains no leading zeros, has at most one contiguous block of ones. 🔹 The Insight: Most string problems tempt you to build complex counters or state machines. However, the constraint "no leading zeros" is the secret key. If the string starts with '1', then a second segment of ones can only exist if we see a '0' followed by a '1' later in the sequence. 🔹 The Efficiency: Instead of manual iteration or regex, the most optimized solution is a simple check for the substring "01". If "01" exists, it marks the start of a non-contiguous second segment. If it doesn't, the ones are either all at the start or the string is all zeros. This reduces the problem to a single linear scan with $O(1)$ auxiliary space. ✨ Achievement: Implemented a high-performance one-liner $O(n)$ solution that achieved 100% efficiency in runtime! It’s a perfect example of how reading the constraints carefully can simplify the logic from a "counting" problem to a "pattern detection" problem. 🔍 Steps followed: ✔ Constraint Analysis: Leveraged the "no leading zeros" rule to establish the starting state. ✔ Pattern Identification: Isolated the "01" transition as the sole indicator of multiple segments. ✔ Boolean Logic: Returned the negation of the pattern existence. 🔧 Complexity Analysis: Time Complexity: $O(n)$ Space Complexity: $O(1)$ 26 days in! Sometimes the most robust code is the code you don't have to write because you found a better mathematical invariant. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #StringAlgorithms #CleanCode #Optimization

#100DaysOfLeetcode journey 🚀 Day 48/100 — Reversing LCP Matrices! Today’s Problem: 2573. Find the String with LCP (Hard) 🔹 The Goal: Given an $n \times n$ matrix representing the Longest Common Prefix (LCP) for every possible pair of suffixes, reconstruct the lexicographically smallest string that generates this exact matrix. 🔹 The Insight: This problem is a beautiful mix of Greedy Construction and Dynamic Programming. The "lexicographically smallest" constraint tells us exactly how to group indices. If lcp[i][j] > 0, indices $i$ and $j$ must share the same character. By processing indices from left to right and assigning the smallest available letter ('a' through 'z'), we build our candidate string. 🔹 The Logic: Grouping: We use the matrix to cluster indices that are forced to be identical. Transitivity Check: The matrix might be a "trap"—it could define relationships that are logically impossible. Verification: The only way to be sure is a full $O(n^2)$ verification. We use the DP relation LCP[i][j] = (s[i] == s[j]) ? LCP[i+1][j+1] + 1 : 0 to regenerate the matrix from our candidate string and compare it to the input. ✨ Achievement: Day 48! Tackled a Hard-level string reconstruction problem. It’s a fantastic exercise in understanding the internal properties of LCP arrays and how to use greedy logic to satisfy lexicographical requirements. 🔍 Steps followed: ✔ Greedy Character Assignment: Clustered indices based on positive LCP values. ✔ Alphabetical Minimization: Prioritized 'a' for the earliest possible unassigned groups. ✔ $O(n^2)$ Consistency Validation: Verified every single cell in the matrix using DP to ensure the matrix was valid. 🔧 Complexity Analysis: Time Complexity: $O(n^2)$ Space Complexity: $O(n)$ 48 days down! The intersection of string algorithms and mathematical consistency is where the most rewarding challenges live. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #StringAlgorithms #DP #LCP #Day48

#100DaysOfLeetcode journey 🚀 Day 41/100 — Spatial Matrix Transformations! Today’s Problem: Vertical Flip of a Square Submatrix 🔹 The Goal: Given a large grid, target a specific $k \times k$ square submatrix and flip it vertically (reverse the row order) without affecting the rest of the grid. 🔹 The Insight: This is a classic in-place transformation problem. Instead of creating a copy of the submatrix (which would cost $O(k^2)$ space), we can use the Two-Pointer technique applied to the rows. By swapping the top-most row of the submatrix with the bottom-most, and moving inward, we achieve the flip with zero extra memory. 🔹 The Logic: Boundary Anchoring: We focus strictly on the window defined by the top-left corner $(x, y)$ and the side length $k$. Symmetric Swapping: For every column in the submatrix, we swap elements at grid[top][j] and grid[bottom][j]. In-Place Efficiency: Since we are modifying the grid directly, the auxiliary space remains $O(1)$. ✨ Achievement: Day 41! Starting the second half of the challenge by mastering in-place grid manipulations. It’s a reminder that even complex-sounding geometric transformations often boil down to simple pointer logic. 🔍 Steps followed: ✔ Coordinate Mapping: Correctly identified the range of indices for the submatrix. ✔ Two-Pointer Iteration: Implemented row-swapping logic to handle the vertical flip. ✔ Constant Space: Ensured no auxiliary arrays were used during the process. 🔧 Complexity Analysis: Time Complexity: $O(k^2)$ Space Complexity: $O(1)$ The journey continues into the second half! Let's keep building. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #MatrixAlgorithms #Optimization #Algorithms #Day41

#100DaysOfLeetcode journey 🚀 Day 29/100 — Optimizing DP with Subtraction Logic! Today’s Problem: 3129. Find the Number of Stable Binary Arrays I 🔹 The Goal: Count the number of binary arrays with a fixed number of 0s and 1s where no contiguous segment of the same digit exceeds a given limit. 🔹 The Insight: This is a sophisticated Dynamic Programming problem. While a naive DP would involve a third loop to count the current block length (resulting in $O(N^2 \cdot \text{limit})$), we can optimize this to $O(N^2)$ using a "prefix-sum" style subtraction. 🔹 The Logic: To calculate the number of ways to end with a 0, we look at all ways to form the previous state. If we exceed the limit, we subtract the specific configuration that would have resulted in an invalid block (a sequence that already had limit zeros preceded by a 1). This mathematical trick removes the need for the third loop, turning an expensive search into a constant-time update. ✨ Achievement: Successfully implemented an $O(\text{zero} \times \text{one})$ solution with 100% accuracy and efficiency. Handling the modulo arithmetic for subtractions was a great refresher on modular invariants! 🔍 Steps followed: ✔ State Optimization: Reduced a 3D state transition into a 2D optimized update. ✔ Boundary Management: Handled base cases for pure 0/1 strings up to the limit. ✔ Mathematical Pruning: Used the subtraction method to maintain the "Stable" property in $O(1)$ per cell. 🔧 Complexity Analysis: Time Complexity: $O(\text{zero} \times \text{one})$ Space Complexity: $O(\text{zero} \times \text{one})$ 29 days in! The transition from basic DP to optimized state transitions is where the true power of algorithm design lies. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #DynamicProgramming #Combinatorics #Algorithms #Day29

#100DaysOfLeetcode journey 🚀 Day 37/100 — Rearranging for Maximum Impact! Today’s Problem: 1727. Largest Submatrix With Rearrangements 🔹 The Goal: Find the largest rectangular submatrix of 1s in a grid where you are allowed to shuffle the columns into any order. 🔹 The Insight: This is a brilliant take on the "Largest Rectangle in Histogram" problem. Usually, the order of bars in a histogram is fixed. But here, because we can rearrange columns, we can always choose to put the tallest bars next to each other. This turns the problem into a simple sorting exercise for every row of the matrix. 🔹 The Logic: Vertical Accumulation: We track the number of consecutive 1s ending at each row to build a virtual histogram. Greedy Sorting: By sorting the heights at each row, we ensure that we check the largest possible rectangles by matching height with the maximum available width. Linear Scan: Once sorted, calculating the area for each possible height takes only $O(N)$ time. ✨ Achievement: Day 37! Implemented an optimized $O(M \cdot N \log N)$ solution. It’s a great example of how changing a single constraint (allowing reordering) can simplify the data structures needed for an optimal solution. 🔍 Steps followed: ✔ Dynamic Height Tracking: Maintained a 1D state array to represent vertical column heights. ✔ Sorted Row Analysis: Used Arrays.sort() at each row to find the optimal width-height configuration. ✔ Memory Efficiency: Achieved $O(N)$ space complexity by processing the matrix row-by-row. 🔧 Complexity Analysis: Time Complexity: $O(M \times N \log N)$ Space Complexity: $O(N)$ 46 days down! The journey to 100 continues, one optimized matrix at a time. 🛠️ #Java #DSA #LeetCode #CodingJourney #100DaysOfCode #SoftwareEngineer #InternshipBound #Programming #MatrixAlgorithms #Greedy #Optimization #Day37

🔹 Day 3 of My DSA Journey 🔹 Solved a classic array problem today — Rotate Array (LeetCode - Medium) 💻 📌 Problem Understanding: Given an integer array nums, the task is to rotate the array to the right by k steps. Example: Input: [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] 💡 Brute Force Approach (My First Approach): Initially, I solved this problem by rotating the array one step at a time (k times). 👉 Steps: Store the last element in a variable Shift all elements one position to the right Place the stored last element at the first position Repeat this process k times ⏱ Time Complexity: O(k × n) ➡️ Works fine but inefficient for large inputs. 🚀 Optimized Approach (Reverse Technique): Then I improved my solution using the array reversal concept. 👉 Steps: Reverse first part → elements before rotation Reverse second part → elements to be rotated Reverse the entire array 📌 Example: Input: [1,2,3,4,5,6,7], k = 3 Step 1: Reverse first part (0 to n-k-1) → [4,3,2,1,5,6,7] Step 2: Reverse second part (n-k to n-1) → [4,3,2,1,7,6,5] Step 3: Reverse whole array → [5,6,7,1,2,3,4] ✅ ✔ Time Complexity: O(n) ✔ Space Complexity: O(1) (In-place) 📚 Key Learning: Understanding patterns like array reversal helps in optimizing solutions significantly. The real improvement comes from converting a brute force approach into an optimal one. 🙏 Thanks to my mentor for guiding me and helping me improve my approach. 📈 Consistency is the key — learning something new every day. #DSA #LeetCode #ProblemSolving #Java #CodingJourney #LearningInPublic #100DaysOfCode

🚀 Day 40 of My 100 Days Coding Challenge Not every problem is about finding an element — sometimes, it's about finding where it should be. Today’s problem, Search Insert Position, reinforced a key concept in algorithm design: 👉 Efficiency is not just about solving the problem, but solving it the right way. Instead of a linear approach, I implemented an optimal Binary Search solution (O(log n)), ensuring scalability and performance. 💡 What I Focused On Writing an efficient solution rather than a brute-force approach Understanding how boundary conditions impact the result Realizing that the final pointer position can represent the answer 📊 Outcome ✅ All test cases passed ⚡ Runtime: 0 ms (Beats 100%) 💾 Memory Usage: Optimized 🧠 Takeaway Small problems often carry big lessons. Today’s learning reminded me that mastering fundamentals like binary search is crucial for tackling complex challenges ahead. 🔁 Consistency 40 days in — and still going strong 💪 Discipline and consistency are slowly turning into confidence. #100DaysOfCode #Day40 #Java #BinarySearch #LeetCode #DSA #ProblemSolving #SoftwareEngineering #CodingJourney 🚀

Day 74 - LeetCode Journey Solved LeetCode 234: Palindrome Linked List (Easy) today — a problem that combines multiple concepts like two pointers + reversing a linked list. The goal is to check whether the linked list reads the same forward and backward. 💡 Core Idea: Instead of using extra space, we optimize by working directly on the list: Find the middle of the list using slow & fast pointers Reverse the second half of the list Compare both halves node by node If all values match → it’s a palindrome ✔️ ⚡ Key Learning Points: • Using slow & fast pointers to find the middle • Reversing half of the linked list efficiently • Comparing two linked list halves • Achieving O(n) time and O(1) space This problem is a perfect example of combining multiple patterns into one clean solution. It’s not just about solving — it’s about recognizing how previously learned concepts fit together 💯 ✅ Better understanding of linked list traversal ✅ Stronger grip on combining multiple techniques ✅ Improved optimization mindset (space efficiency) These are the kinds of problems that build real confidence in DSA 🚀 #LeetCode #DSA #Java #LinkedList #Algorithms #ProblemSolving #CodingJourney #Consistency #100DaysOfCode #InterviewPreparation #DeveloperGrowth #KeepCoding

#100DaysOfLeetcode journey 🚀 Day 43/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 43! 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 #Day43

🚀 Day 26/60 — LeetCode Discipline Problem Solved: Remove Element (Revision) Difficulty: Easy Today’s practice focused on revisiting a fundamental array problem involving in-place modification. The task was to remove all occurrences of a given value without using extra space, while efficiently maintaining the remaining elements. The solution leverages a simple yet powerful approach of iterating through the array and overwriting unwanted elements. Problems like this reinforce the importance of space optimization and clean in-place operations, which are often crucial in real-world scenarios. 💡 Focus Areas: • Strengthened in-place array manipulation • Practiced efficient element filtering • Reinforced two-pointer style iteration • Improved understanding of space optimization • Focused on writing concise and readable code ⚡ Performance Highlight: Achieved 0 ms runtime (100% performance) on submission. Simple problems, when practiced with discipline, continue to sharpen the core of problem-solving ability. #LeetCode #60DaysOfCode #100DaysOfCode #DSA #Arrays #TwoPointers #Algorithms #DataStructures #ProblemSolving #CodingJourney #SoftwareEngineering #Programming #Developers #TechCareers #Java