Square Root Decomposition & Prefix Multiplications for LeetCode Problem 3655

🚀 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 35 of #100DaysOfCode✳️ 📌 Cracking the "Redundant Connection" Problem with DSU! 🛠️ My Approach: The DSU Strategy The Disjoint Set Union (or Union-Find) algorithm is perfect here because it allows us to track connected components efficiently as we iterate through the edges. ✨The Steps in my Code: 1️⃣Initialization: Created a parent array where every node is initially its own parent (representing n independent sets). 2️⃣Iterative Union: For every edge (u, v) in the input: Find the root (representative) of u. Find the root (representative) of v. Cycle Detection: * If find(u) == find(v), it means u and v are already part of the same connected component. Adding this edge would create a cycle. 🚩 Since the problem asks for the last edge that causes the cycle, I return this edge immediately. 3️⃣Union: If they are in different sets, I perform a union by setting the parent of one root to the other. 4️⃣Optimization: I used Path Compression in the find function to keep the tree flat, ensuring almost constant time complexity. 💡 When should you use DSU? 🔅DSU is a powerhouse for specific graph scenarios. Reach for it when: Cycle Detection: You need to check if adding an edge creates a cycle in an undirected graph. 🔅Connected Components: You need to count or manage groups of connected nodes dynamically. 🔅Minimum Spanning Trees: It’s the backbone of Kruskal’s Algorithm. Grid Problems: Identifying "islands" or connected regions in a 2D matrix. #DataStructures #Algorithms #LeetCode #Java #GraphTheory #CodingLife #SoftwareEngineering

🧠 Day 212 — Maximum Distance Between Valid Pairs 📏⚡ Today solved a solid two-pointer optimization problem on sorted arrays. 📌 Problem Goal Given two non-increasing arrays: ✔️ Find indices (i, j) such that ✔️ i ≤ j and nums1[i] ≤ nums2[j] ✔️ Maximize the distance (j - i) 🔹 Core Idea Use two pointers to efficiently explore valid pairs: ✔️ Start both pointers at the beginning ✔️ Expand j to find valid matches ✔️ Move i only when condition breaks 🔹 Key Observation ✔️ Arrays are sorted in non-increasing order → huge advantage ✔️ If nums1[i] > nums2[j], move i forward ✔️ Otherwise, update answer and try expanding j 🧠 Key Learning ✔️ Two-pointer technique works best on sorted data ✔️ Avoid brute force → think in terms of pointer movement ✔️ Maintain valid window while maximizing distance 💡 Big Realization Whenever you see: 👉 “Maximize/minimize distance” 👉 “Sorted arrays” Think: ➡️ Can I solve this using two pointers instead of nested loops? 🚀 Momentum Status: Strong grip on array + pointer patterns. On to Day 213. #DSA #TwoPointers #Arrays #Optimization #LeetCode #Java #CodingJourney #ConsistencyWins

**Day 115 of #365DaysOfLeetCode Challenge** Today’s problem: **Diagonal Traverse (LeetCode 498)** A smart **matrix traversal** problem where the goal is to print all elements in zigzag diagonal order. Example: ```text id="k44nq2" 1 2 3 4 5 6 7 8 9 ``` Output: `[1,2,4,7,5,3,6,8,9]` **Core Idea:** Each diagonal is identified by: `row + col` * If `(row + col)` is even → move **up-right** * If `(row + col)` is odd → move **down-left** This removes the need for an extra direction variable. 📌 **Approach:** 1️⃣ Start at `(0,0)` 2️⃣ Add current element to result 3️⃣ Check parity of `(row + col)` 4️⃣ Move diagonally 5️⃣ If boundary reached, adjust row/col accordingly Repeat until all cells are visited. ⚡ **Time Complexity:** O(m × n) ⚡ **Space Complexity:** O(1) extra (excluding output) **What I learned today:** Sometimes parity (`row + col`) can simplify movement logic beautifully. Instead of tracking direction separately: 👉 Even diagonal = upward 👉 Odd diagonal = downward 💭 **Key Takeaway:** Great solutions often replace state variables with mathematical patterns. #LeetCode #DSA #Matrix #Arrays #Traversal #Java #CodingChallenge #ProblemSolving #TechJourney #Consistency

Day 24 of my #30DayCodeChallenge: The Art of In-Place Transformation! The Problem: Rotate Image (90 Degrees Clockwise) How do you rotate an n × n matrix without using extra space? The challenge isn't just the rotation- it's doing it in-place, maintaining O(1) extra space complexity. The Logic: Instead of trying to move every element to its final destination in one leap, this problem is best solved by breaking it down into two simple geometric transformations: 1. The Transpose: First, I flipped the matrix over its main diagonal. This turns all rows into columns (and vice versa). Mathematically, we swap matrix [i][j] with matrix [j][i]. 2. The Reflection: Once transposed, the image "sideways." To fix the orientation for a clockwise rotation, I ersed each row. This horizontal flip move columns into their correct 90-dearee positions. One step closer to mastery. Onward to Day 25! #Java #Algorithms #DataStructures #Matrix #ProblemSolving #150DaysOfCode #SoftwareEngineering #LeetCode

🚀 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 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 80/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Convert Sorted Array to Binary Search Tree A classic divide-and-conquer problem that builds intuition for balanced trees. Problem idea: Convert a sorted array into a height-balanced BST. Key idea: Recursion + choosing the middle element as root. Why? • The array is already sorted • Picking the middle ensures balance • Left half forms left subtree, right half forms right subtree How it works: • Find the middle index of the array • Create a node with that value • Recursively build left subtree using left half • Recursively build right subtree using right half Time Complexity: O(n) Space Complexity: O(log n) (recursion stack) Big takeaway: Whenever you need a balanced BST from sorted data, think divide & conquer with mid as root. 🔥 This pattern is widely used in tree construction problems. Day 80 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #BinarySearchTree #DivideAndConquer #Recursion #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

Day 94: Slanted Ciphertext & Loop Optimization 📟 Problem 2075: Decode the Slanted Ciphertext Today’s solve was a fun callback to the "ZigZag Conversion" problem I've tackled before. The challenge: read a string that was written diagonally across a matrix and then flattened into a single row. The Strategy: • Diagonal Traversal: The key is calculating the step size. In a slanted cipher, the next character in a diagonal is exactly columns + 1 indices away. • Refining the Loop: My first approach worked well, but I realized I could shave off execution time by adding an early exit. • The "Efficiency" Jump: By adding a simple check, if(j % column == column-1) break;—I stopped the inner loop from looking for diagonal neighbors that would logically fall outside the matrix boundaries. The Result: This small logic tweak dropped my runtime from 28ms down to 18ms, jumping from beating 56% to 97.63% of users. It’s a great reminder that even on "easier" problems, there’s always room to optimize. Seeing that performance graph move to the far left is the best kind of motivation. 🚀 #LeetCode #Java #StringManipulation #Algorithm #Optimization #DailyCode

#70DayStreak 🚀 27/04/26 — Optimized Sliding Window | Longest Substring Without Repeating Characters (LeetCode 3) Today I revisited a classic problem — Longest Substring Without Repeating Characters — and implemented a more optimized Sliding Window using HashMap. Previously, I used a HashSet approach where the window shrinks step-by-step. This time, I upgraded it with a "jumping window" technique, allowing direct pointer movement. 🔑 Key Optimization Insight Instead of removing characters one by one: • Store last seen index of each character • When duplicate appears → jump left pointer instantly • Avoid unnecessary iterations 👉 This reduces redundant work and improves efficiency significantly. ⚙️ Algorithm Highlights • Left pointer jumps using stored indices • Right pointer scans once • Continuous max window calculation 📊 Complexity • Time: O(n) • Space: O(min(m, n)) 📈 Performance • Runtime: 5ms (Beats 87.15%) • Memory: 45.67 MB (Beats 69.72%) 🔥 Consistency Metrics • 84 Active Days • 70-Day Streak 💡 Key Learning Switching from HashSet → HashMap transforms the approach from iterative shrinking to direct optimization. This is a small shift in thinking, but a big upgrade in performance. 📌 Even after 100+ problems, refinement and optimization still matter. #DSA #Java #LeetCode #SlidingWindow #HashMap #Algorithms #CodingJourney #ProblemSolving #Optimization #100DaysOfCode