Divide Two Integers Without Multiplication or Division

**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 78 — Slow & Fast Pointer Pattern (Complete Revision) Today I wrapped up my revision of the Slow & Fast Pointer pattern — one of the most versatile techniques in DSA. This single pattern solves ~60% of linked list problems and extends beautifully to arrays, strings, and even mathematical sequences. 📌 Three Core Applications (100% guaranteed): 1️⃣ Detecting a Cycle slow moves 1 step, fast moves 2 steps. If they meet → cycle exists. If fast reaches null → no cycle. 2️⃣ Finding the Cycle’s Starting Point Detect cycle first (slow == fast). Reset slow to start, keep fast at meeting point. Move both 1 step at a time → they meet at cycle start. 3️⃣ Finding the Middle of a Linked List slow moves 1 step, fast moves 2 steps. When fast reaches end → slow is at middle. 🧠 Beyond Linked Lists: This pattern also solves: LeetCode 202 – Happy Number (mathematical cycle) LeetCode 287 – Find Duplicate Number (array as linked list) LeetCode 141/142 – Linked List Cycle I & II LeetCode 876 – Middle of Linked List 💡 Critical Safety Check: Always ensure fast != null && fast.next != null before moving fast.next.next — avoids null pointer exceptions. No guilt about past breaks. Patterns > problems. One pattern at a time, one day at a time. #DSA #SlowFastPointer #CycleDetection #LinkedList #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

Day 2 of Problem solving: 🚀 Solved 3 DSA Problems Today | Here’s the Simple Logic Behind Them 👇 Today I practiced 3 interesting problems based on BFS, Sliding Window, and Greedy patterns 💡 🔹 1. Valid Path in a Grid (LeetCode 1391) This problem is based on BFS/DFS traversal 🌐 👉 Each grid cell has a street type 👉 We can move only in allowed directions 👉 The next cell must also connect back to the current one So the logic is: • Start from (0,0) 📍 • Explore all valid connected paths • If we reach the last cell, answer is true ✅ ⏱️ Time Complexity: O(m × n) 🔹 2. Longest Repeating Character Replacement This uses the Sliding Window technique 🪟 Main idea 💡 For every window: window size - max frequency <= k This means: • Keep the most frequent character as it is • Replace the remaining characters Logic: • Expand the window ➡️ • If replacements needed are more than k, shrink from left ⬅️ • Track maximum valid length 📏 ⏱️ Time Complexity: O(n) 🔹 3. Codeforces - Line Trip This one is based on a Greedy observation ⛽ Logic: • Find the maximum gap between consecutive gas stations • Last gap needs special care because there is no station at x ⚠️ • So last distance is doubled 🔁 Formula: max(normal gaps, 2 * last gap) That gives the minimum tank capacity needed 🚗 ⏱️ Time Complexity: O(n) ✨ Today’s learning: Recognizing patterns makes DSA much easier 💯 📌 Grid → BFS 📌 String → Sliding Window 📌 Distance → Greedy #DSA #LeetCode #Codeforces #Java #ProblemSolving #Algorithms #CodingJourney 🚀

🚀 Day 75 — Slow & Fast Pointer (Happy Number Detection) Extending the slow‑fast pointer pattern beyond linked lists — today I applied it to a mathematical problem involving cycles. 📌 Problem Solved:  - LeetCode 202 – Happy Number 🧠 Key Learnings: 1️⃣ The Problem in a Nutshell  A number is happy if repeatedly replacing it with the sum of squares of its digits eventually reaches 1. If it enters a cycle that doesn’t include 1, it’s unhappy. 2️⃣ Why Slow‑Fast Pointer Works   - The sequence of numbers (n → sum of squares of digits → ...) will eventually either reach 1 or enter a cycle.   - This is exactly like detecting a cycle in a linked list — except the “next” is defined mathematically.   - Slow moves one step: `slow = sq(slow)`   - Fast moves two steps: `fast = sq(sq(fast))`   - If they meet at a value other than 1 → cycle exists → unhappy number.   - If fast reaches 1 → happy number. 3️⃣ The sq() Helper Computes sum of squares of digits. Clean and reusable. 4️⃣ Edge Cases - n = 1 → returns true immediately (loop condition `fast != 1` fails, returns true).   - Numbers like 2, 3, 4 eventually cycle (4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4). 💡 Takeaway:  The slow‑fast pointer pattern isn’t just for linked lists — it’s a general cycle detection tool that works for any sequence with a deterministic “next” step. Recognizing this abstraction is what makes a great problem solver. No guilt about past breaks — just one problem at a time, one pattern at a time. #DSA #SlowFastPointer #HappyNumber #CycleDetection #LeetCode #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

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

🚀 LeetCode — Problem 8 | Day 13 💡 Problem: String to Integer (atoi) --- 🧠 Problem: Convert a string into a 32-bit signed integer (like C/C++ atoi). --- 🧠 Approach: - Skip leading whitespaces - Check sign (+ / -) - Convert digits one by one - Stop at first non-digit character - Handle overflow before it happens --- ⚙️ Core Logic: - Build number step-by-step: result = result * 10 + digit - Before adding digit, check: • If result > Integer.MAX_VALUE / 10 • Or result == MAX/10 and digit > 7 👉 Return: - Integer.MAX_VALUE (overflow) - Integer.MIN_VALUE (underflow) --- ⏱ Time Complexity: O(n) 📦 Space Complexity: O(1) --- ⚠️ Edge Cases: - " 42" → leading spaces - "-42" → negative number - "42abc" → stop at non-digit - "abc" → no digits → return 0 - Large values → handled overflow --- 🔍 Insight: Careful parsing is more important than complex logic --- 🔑 Key Learning: - Step-by-step string parsing - Handling edge cases cleanly - Preventing overflow before it occurs - Real-world input validation logic --- #LeetCode #DSA #Java #CodingJourney

🔥 Day 552 of #750DaysOfCode 🔥 🔐 LeetCode 2075: Decode the Slanted Ciphertext (Medium) Today’s problem looked tricky at first, but once the pattern clicked, it became super elegant 😄 🧠 Problem Understanding We are given an encoded string that was: Filled diagonally (↘) into a matrix Then read row-wise (→) 👉 Our task is to reverse this process and recover the original text. 💡 Key Insight If encoding is: ➡️ Fill diagonally ➡️ Read row-wise Then decoding is: ➡️ Read diagonally from row-wise string ⚙️ Approach ✅ Step 1: Calculate number of columns cols = encodedText.length() / rows; ✅ Step 2: Traverse diagonals starting from each column for (int startCol = 0; startCol < cols; startCol++) { int row = 0, col = startCol; while (row < rows && col < cols) { result.append(encodedText.charAt(row * cols + col)); row++; col++; } } ✅ Step 3: Remove trailing spaces 🚀 Complexity Time: O(n) Space: O(n) 🧠 What I Learned How to reverse matrix-based encoding patterns Converting 2D traversal → 1D index mapping Importance of pattern recognition in problems 📌 Takeaway Not every problem needs heavy logic. Sometimes, it's just about seeing the pattern correctly 👀 #LeetCode #DSA #Java #CodingJourney #ProblemSolving #Algorithms #SoftwareEngineering #100DaysOfCode #750DaysOfCode

Day 1 of problem solving: 🚀 Solved 4 interesting DSA problems today — sharing quick approaches + core logic 👇 1️⃣ Detect Cycles in 2D Grid Used DFS + parent tracking. The key idea is to traverse only same-valued adjacent cells and detect whether we revisit an already visited cell that is not the immediate parent. 🔹 Algorithm: Graph Traversal (DFS) 🔹 Logic: visited[][] + previous cell coordinates 2️⃣ Common Elements in 3 Sorted Arrays Applied the 3-pointer technique. Since all arrays are sorted, we move the pointer pointing to the smallest value until all three values match. 🔹 Algorithm: Two/Three Pointers 🔹 Logic: linear scan in O(n1 + n2 + n3) 3️⃣ Smallest Window Containing 0, 1 and 2 Solved using the Sliding Window approach. Expand the right pointer until the window contains all 3 digits, then shrink from the left to find the minimum valid window. 🔹 Algorithm: Sliding Window 🔹 Logic: frequency count + two pointers 4️⃣ Halloumi Boxes (Codeforces) A beautiful observation-based problem. If k = 1, no movement is possible, so the array must already be sorted. If k > 1, adjacent swaps become possible through reversal, meaning any array can be sorted. 🔹 Algorithm: Greedy / Observation 🔹 Logic: reversal length property 💡 Today’s takeaway: Not every problem needs heavy coding — sometimes the strongest solution comes from the right observation and choosing the correct algorithmic pattern. #DSA #Java #LeetCode #Codeforces #ProblemSolving #Algorithms #DataStructures #CodingInterview #SoftwareEngineer #100DaysOfCode Follow for more problem solving content and stay updated 🚀

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 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