Rotating an n x n Matrix in Place Without Extra Space

Day 28 of my #30DayCodeChallenge: The Art of Navigation! The Problem: Spiral Matrix. Given an m x n matrix, return all elements in a spiral order-starting from the top-left, moving right, then down, then left, and then up, repeating until every cell is visited. The Logic: This problem is a classic exercise in Simulation and Boundary Management. While there are several ways to track boundaries, I opted for a clean Directional Array approach: 1. Directional Vectors: I defined a direction array dirs = {0, 1, 0, -1, 0} to cycle through the four possible movements: Right → Down → Left → Up. 2. Boundary & Collision Detection: Using a visited boolean matrix, the algorithm "drives" forward until it hits a wall (the edge of the matrix) or a cell it has already seen. 3. The Pivot: Whenever collision is detected, the logic increments the direction index k using the formula:k = (k +1) (mod4) This ensures the traversal always turns 90 degrees at the right moment, perfectly maintaining the spiral pattern. 4. The Termination: The loop runs exactly m x n times, ensuring every single element is collected without redundant checks. One step closer to mastery. Onward to Day 29! #Java #Algorithms #DataStructures #Matrix #ProblemSolving #150DaysOfCode

Day 27 of my #30DayCodeChallenge: The Efficiency of Binary Exponentiation! The Problem: Pow(x, n). Implementing the power function to calculate x". While it sounds simple, the challenge lies in handling large exponents (up to 231 - 1) and negative powers without hitting time limits or overflow. The Logic: This problem is a classic example of Divide and Conquer optimized through Binary Exponentiation (also known as Exponentiation by Squaring): 1. Bitwise Breakdown: Instead of multiplying x by itself n times (O(n)), we decompose n into powers of 2. For example, x13 is x8. x4. x¹. This brings our complexity down to O(log n). 2. The Iterative Jump: In every iteration of the loop, we square the current base (x = x x). If the current bit of n is 1 (checked via n & 1), we multiply our result by the current base. 3. Handling the Edge Cases: * Negative Exponents: If n is negative, we calculate xI" and then take the reciprocal (1/result). Overflow: We use a long for n during calculation to avoid overflow when converting -2, 147, 483, 648 to a positive value. The Calculation: By halving the power at each step, we transform a task that could take 2 billion operations into one that takes just 31. One step closer to mastery. Onward to Day 28! #Java #Algorithms #DataStructures #BinaryExponentiation #ProblemSolving #150DaysOfCode #SoftwareEngineer

🚀 Day 55 of #100DaysOfCode – Rotate Image Today I worked on an interesting matrix problem: Rotate Image (90° clockwise) 🔄 💡 Key Learning: Instead of using extra space, the challenge is to rotate the matrix in-place. 🧠 Approach I used: 1️⃣ Transpose the matrix (convert rows → columns) 2️⃣ Reverse each row This combination effectively rotates the matrix by 90° clockwise without using extra memory. 📌 Example: Input: [[1,2,3], [4,5,6], [7,8,9]] Output: [[7,4,1], [8,5,2], [9,6,3]] ⚡ Complexity: Time: O(n²) Space: O(1) (in-place) 💻 Implemented in Java and successfully passed all test cases ✅ This problem really helped me strengthen my understanding of matrix manipulation and in-place algorithms. #LeetCode #DataStructures #Java #CodingPractice #ProblemSolving #Algorithms #100DaysOfCode

🚀 Day 557 of #750DaysOfCode 🚀 🔥 Solved: XOR After Range Multiplication Queries II (Hard) Today’s problem really pushed my understanding of optimization and patterns in arrays. At first glance, it looks like a simple simulation—but with constraints up to 10⁵, a brute-force approach quickly breaks down. 💡 Key Learnings: Handling range updates efficiently is crucial Observed how step-based traversal (k jumps) affects time complexity Importance of modular arithmetic in large computations XOR properties helped in deriving the final result efficiently ⚡ Challenge: Each query updates elements at intervals, making it tricky to optimize without directly iterating every time. 🧠 Takeaway: Hard problems are less about coding and more about recognizing patterns and optimizing smartly. Consistency is the real game 💯 #LeetCode #DataStructures #Algorithms #CodingJourney #ProblemSolving #Java #100DaysOfCode #KeepGrinding

🚀 Day 8/100 — #100DaysOfLeetCode Another day, another concept unlocked 💻🔥 ✅ Problem Solved: 🔹 LeetCode 73 — Set Matrix Zeroes 💡 Problem Idea: If any element in a matrix is 0, its entire row and column must be converted to 0 — and the challenge is to do this in-place without using extra space. 🧠 Algorithm & Tricks Learned: Instead of using extra arrays, we can use the first row and first column as markers. First pass → mark rows and columns that should become zero. Second pass → update the matrix based on those markers. Carefully handle the first row and first column separately to avoid losing information. ⚡ Key Insight: The matrix itself can act as storage, reducing extra memory usage. 📊 Complexity Analysis: Time Complexity: O(m × n) → traverse matrix twice Space Complexity: O(1) → solved in-place without extra data structures This problem taught me how small optimizations can significantly improve space efficiency. Learning to think beyond brute force every day 🚀 #100DaysOfLeetCode #LeetCode #DSA #MatrixProblems #Algorithms #Java #ProblemSolving #CodingJourney #LearningInPublic

🚀 Day 563 of #750DaysOfCode 🚀 📌 Problem Solved: Shortest Distance to Target String in a Circular Array Today I explored a clean and optimized approach to solving a circular array problem 🔄 💡 Key Insight: Instead of checking all indices, we can expand from the start index in both directions simultaneously 👉 At each step i, we check: Forward → (start + i) % n Backward → (start - i + n) % n ⏱️ The moment we find the target, we return i → which is guaranteed to be the minimum distance 🧠 Why this works: We are exploring layer by layer (like BFS on array) First match = shortest path ✅ No need to scan entire array unnecessarily 🔥 What I Learned: Circular problems can often be solved using modulo arithmetic Expanding outward is more efficient than brute force Think in terms of minimum steps, not positions Consistency is the real game changer 💯 On to Day 564 🚀 #LeetCode #Java #Algorithms #DataStructures #CodingJourney #ProblemSolving #Consistency

Day 99: Square Root Decomposition & Prefix Multiplications ⚡ Problem 3655: XOR After Range Multiplication Queries II Yesterday’s brute force approach hit a wall today with a TLE (Time Limit Exceeded). The constraints were significantly tighter, requiring a more sophisticated optimization. The Strategy: Square Root Decomposition To handle the queries efficiently, I split the problem based on the step size k: • Large Steps (k ≥ √N): For large gaps, the number of updates is small enough that direct simulation still works within time limits. • Small Steps (k < √N): This is where the magic happens. For small k, I used a Difference Array technique modified for multiplications. • Modular Inverse & Prefix Products: Instead of updating every index, I marked the start (L) and end (R) of the range. I used modInverse to "cancel out" the multiplication after the range ended. A final prefix product pass (jumping by k) applied all updates in O(N) time. Technical Highlights: • Fermat's Little Theorem: Used modPow(x, MOD - 2) to calculate the modular inverse for division. • Complexity: Reduced the worst-case runtime from O(Q⋅N) to O((Q+N)√N). One day away from 100, but the focus remains on the problem in front of me. Consistency isn't about the destination; it's about the quality of the journey. 🚀 #LeetCode #Java #Algorithms #DataStructures #SquareRootDecomposition #DailyCode

🚀 Day 566 of #750DaysOfCode 🚀 🔍 Problem Solved: Mirror Distance of an Integer Today’s problem was simple but a great reminder of how powerful basic number manipulation can be. 💡 Problem Insight: We define the mirror distance of a number as: 👉 abs(n - reverse(n)) So the task is: Reverse the digits of the number Compute the absolute difference 🧠 Approach: Extract digits using % 10 Build the reversed number Compute absolute difference 📊 Complexity: Time: O(d) → where d = number of digits Space: O(1) 🔥 Key Takeaway: Even the easiest problems reinforce fundamentals like digit extraction, reversal, and absolute difference — building blocks for more complex algorithms. #Day566 #750DaysOfCode #LeetCode #Java #CodingJourney #ProblemSolving #Algorithms #BeginnerFriendly

🚀 LeetCode Challenge 22/50 💡 Approach: Space-Optimized Dynamic Programming A robot moves only RIGHT or DOWN on an m×n grid. How many unique paths reach the bottom-right corner? Recursion explodes exponentially — DP solves it beautifully, and we can do even better by ditching the full 2D grid! 🔍 Key Insight: → Every cell's paths = paths from ABOVE + paths from LEFT → First row & first column always have exactly 1 path each → We only ever need the CURRENT and PREVIOUS row → So one 1D array updated in-place is enough! 📈 Complexity: ❌ Recursion → O(2^(m+n)) Time ❌ 2D DP → O(m×n) Time, O(m×n) Space ✅ 1D DP → O(m×n) Time, O(n) Space   Same speed, fraction of the memory! DP teaches us to build solutions from the ground up — one step, one row, one decision at a time. 🤖 #LeetCode #DSA #DynamicProgramming #Java #ADA #PBL2 #LeetCodeChallenge #Day22of50 #CodingJourney #ComputerEngineering #AlgorithmDesign #UniquePaths

Day 20 of my #30DayCodeChallenge: Efficiency through Pruning! Today's challenge was Word Search II-a complex puzzle that tests how you manage massive search spaces. The Logic: 1. Trie Integration: I stored the dictionary in a Trie to check prefixes in O(1) time. 2. DFS & Backtracking: Explored the grid cell by cell, but with a twist... 3. Intelligent Pruning: If a path doesn't match a Trie prefix, the search stops immediately. This turns an exponential problem into something much more manageable. Coding isn't just about finding the answer; it's about finding it before your timer runs out! #Java #DataStructures #Backtracking #Trie #Algorithms #CleanCode #150DaysOfCode