Search results for "Math Trick" | Kodesword

LeetCode 36: Valid Sudoku Explained – Java Solutions, Intuition & Formula Dry Run

IntroductionSudoku is a universally beloved puzzle, but validating a Sudoku boardalgorithmically is a classic technical interview question. In this post, we aregoing to dive deep into LeetCode 36: Valid Sudoku.We won't just look at the code; we will explore the intuition behind the problemso you don't have to memorize anything. We’ll cover an ingenious in-placevalidation approach, break down the complex math formula used to check3 \times 3 sub-boxes, and look at an alternative optimal solution usingHashSets.Let's dive in!Understanding the ProblemThe problem asks us to determine if a partially filled 9 \times 9 Sudoku boardis valid. To be valid, the filled cells must follow three straightforward rules:1. Each row must contain the digits 1-9 without repetition.2. Each column must contain the digits 1-9 without repetition.3. Each of the nine 3 \times 3 sub-boxes must contain the digits 1-9 withoutrepetition.Important Note: A valid board doesn't mean the board is fully solvable! We onlycare about checking the numbers that are currently on the board.Intuition: How to Think About the ProblemBefore writing code, how do we, as humans, check if a Sudoku board is valid? Ifyou place a 5 in a cell, you quickly scan horizontally (its row), vertically(its column), and within its small 3 \times 3 square. If you see another 5, theboard is invalid.To translate this to code, we have two choices:1. The Simulation Approach: Go cell by cell. Pick up the number, hide it, andcheck its row, column, and 3 \times 3 box to see if that number existsanywhere else. (This is the approach we will look at first).2. The Memory Approach: Go cell by cell, but keep a "notebook" (like a HashTable) of everything we have seen so far. If we see a number we've alreadywritten down for a specific row, column, or box, it's invalid.Approach 1: The In-Place Validation (Space-Optimized)Here is a brilliant solution that validates the board without using any extradata structures.The Logic: Iterate through every cell on the board. When we find a number, wetemporarily replace it with a . (empty space). Then, we iterate 9 times to checkits entire row, column, and sub-box. If the number is found, we return false.Otherwise, we put the number back and move to the next cell.The Java Codeclass Solution {public boolean isvalid(char[][] board, int i, int j, char k) {for(int m = 0; m < 9; m++) {// Check rowif(board[i][m] == k) return false;// Check columnif(board[m][j] == k) return false;// Check 3x3 sub-boxif(board[3 * (i / 3) + m / 3][3 * (j / 3) + m % 3] == k) return false;}return true;}public boolean isValidSudoku(char[][] board) {for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(board[i][j] != '.') {char temp = board[i][j];board[i][j] = '.'; // Temporarily remove the numberif(!isvalid(board, i, j, temp)) {return false;}board[i][j] = temp; // Put the number back}}}return true;}}The Math Breakdown: Demystifying the 3 \times 3 Grid FormulaThe hardest part of this code to understand is this exact line: board[3*(i/3) +m/3][3*(j/3) + m%3]How does a single loop variable m (from 0 to 8) traverse a 3 \times 3 grid?Let’s do a dry run.Step 1: Finding the Starting Point of the BoxThe grid is 9 \times 9, broken into nine 3 \times 3 boxes. If we are at a randomcell, say row i = 4, col j = 5, which box are we in? Because integer division inJava drops the decimal:i / 3 = 4 / 3 = 1j / 3 = 5 / 3 = 1Now multiply by 3 to get the actual starting coordinates (top-left corner) ofthat specific sub-box:3 * 1 = 3 (Row offset)3 * 1 = 3 (Col offset) So, the 3 \times 3 box starts at row 3, col 3.Step 2: Traversing the Box (Dry Run)Now, as m goes from 0 to 8, we use m / 3 for rows and m % 3 for columns:m = 0: row offset 0/3 = 0, col offset 0%3 = 0 \rightarrow Checks (3+0, 3+0) = (3, 3)m = 1: row offset 1/3 = 0, col offset 1%3 = 1 \rightarrow Checks (3+0, 3+1) = (3, 4)m = 2: row offset 2/3 = 0, col offset 2%3 = 2 \rightarrow Checks (3+0, 3+2) = (3, 5)m = 3: row offset 3/3 = 1, col offset 3%3 = 0 \rightarrow Checks (3+1, 3+0) = (4, 3)m = 4: row offset 4/3 = 1, col offset 4%3 = 1 \rightarrow Checks (3+1, 3+1) = (4, 4)...and so on up to m = 8.This brilliant math formula maps a 1D loop (0 to 8) directly onto a 2D3 \times 3 grid perfectly! No nested loops needed inside the isvalid function.Approach 2: The HashSet Solution (Single Pass)While the first approach is highly space-efficient, it does a bit of redundantchecking. An alternative approach that interviewers love is using a HashSet.Instead of checking rows and columns every time we see a number, we generate aunique "string signature" for every number and attempt to add it to a HashSet.If we see a 5 at row 0 and col 1, we create three strings:1. "5 in row 0"2. "5 in col 1"3. "5 in block 0-0"The HashSet.add() method returns false if the item already exists in the set. Ifit returns false, we instantly know the board is invalid!HashSet Java Code:class Solution {public boolean isValidSudoku(char[][] board) {HashSet<String> seen = new HashSet<>();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char number = board[i][j];if (number != '.') {// HashSet.add() returns false if the element already existsif (!seen.add(number + " in row " + i) ||!seen.add(number + " in col " + j) ||!seen.add(number + " in block " + i/3 + "-" + j/3)) {return false;}}}}return true;}}Notice how we use i/3 + "-" + j/3 to identify the blocks. Top-left is block 0-0,bottom-right is block 2-2.Time and Space Complexity BreakdownInterviewers will always ask for your complexity analysis. Because a Sudokuboard is strictly fixed at 9 \times 9, the strict Big-O is actually constant.However, let's look at it conceptually as if the board were N \times N.Approach 1: In-Place Validation (Your Solution)Time Complexity: O(1) (Strictly speaking). We traverse 81 cells, and foreach cell, we do at most 9 iterations. 81 \times 9 = 729 operations. Since729 is a constant, it's O(1). (If the board was N \times N, time complexitywould be O(N^3) because for N^2 cells, we iterate N times).Space Complexity: O(1). We only use primitive variables (i, j, k, m, temp).No extra memory is allocated.Approach 2: HashSet ApproachTime Complexity: O(1). We traverse the 81 cells exactly once. Generatingstrings and adding to a HashSet takes O(1) time. (If the board wasN \times N, time complexity would be O(N^2)).Space Complexity: O(1). The HashSet will store a maximum of81 \times 3 = 243 strings. Since this upper limit is fixed, space isconstant.ConclusionThe Valid Sudoku problem is a fantastic exercise in matrix traversal andcoordinate math.When solving this in an interview:1. Use the first approach if you want to impress the interviewer with O(1)space complexity and your deep understanding of math formulas (the /3 and %3trick).2. Use the second approach (HashSet) if you want to show off your knowledge ofdata structures and write highly readable, clean, and clever code.I hope this breakdown gives you the intuition needed so you never have tomemorize the code for LeetCode 36!Happy Coding! Keep Learning🤟

LeetCodeJavaMatrixHash TableRecursionBacktrackingMedium

Fast and Slow Pointer Technique in Linked List: Cycle Detection, Proof, and Complete Explanation

🚀 Before We StartTry these problems (optional but helpful):https://leetcode.com/problems/linked-list-cycle/https://leetcode.com/problems/linked-list-cycle-ii/🤔 Let’s Talk Honestly…When you first learn this technique, you’re told:👉 “Slow moves 1 step, fast moves 2 steps”👉 “If they meet → cycle exists”But your brain asks:❓ Why 2 steps?❓ Why do they meet at all?❓ Why does resetting pointer find cycle start?❓ Is this magic or logic?👉 Let’s answer each doubt one by one.🧩 Doubt 1: Why do we even use two pointers?❓ Question:Why not just use one pointer?✅ Answer:With one pointer:You can only move forwardYou cannot detect loops efficiently👉 Two pointers create a relative motionThat relative motion is the key.🧩 Doubt 2: Why fast = 2 steps and slow = 1 step?❓ Question:Why exactly 2 and 1?✅ Answer:We need:Fast speed > Slow speedSo that:👉 Fast catches up to slow🧠 Think like this:If both move same speed:Slow → 1 stepFast → 1 step👉 They will NEVER meet ❌If:Slow → 1 stepFast → 2 steps👉 Fast gains 1 node every step🔥 Key Insight:Relative speed = fast - slow = 1👉 This means fast is closing the gap by 1 node every step🧩 Doubt 3: Why do they ALWAYS meet in a cycle?❓ Question:Okay, fast is faster… but why guaranteed meeting?🧠 Imagine a Circular TrackInside a cycle, the list behaves like:Circle of length = λNow:Slow moves 1 stepFast moves 2 steps🔄 Gap BehaviorEach step:Gap = Gap - 1Because fast is catching up.Eventually:Gap = 0👉 They meet 🎯💡 Simple AnalogyTwo runners on a circular track:One is fasterOne is slower👉 Faster runner will lap and meet slower runner🧩 Doubt 4: What if there is NO cycle?❓ Question:Why does this fail without cycle?✅ Answer:If no cycle:List ends → fast reaches null👉 No loop → no meeting🧩 Doubt 5: Where do they meet?❓ Question:Do they meet at cycle start?❌ Answer:No, not necessarily.They meet somewhere inside the cycle🧩 Doubt 6: Then how do we find the cycle start?Now comes the most important part.🎯 SetupLet’s define:a = distance from head to cycle startb = distance from cycle start to meeting pointc = remaining cycleCycle length:λ = b + c🧠 What happens when they meet?Slow distance:a + bFast distance:2(a + b)Using relation:2(a + b) = a + b + kλSolve:a + b = kλ=> a = kλ - b=> a = (k-1)λ + (λ - b)💥 Final Meaninga = distance from meeting point to cycle start🔥 BIG CONCLUSION👉 Distance from head → cycle start👉 = Distance from meeting point → cycle start🧩 Doubt 7: Why resetting pointer works?❓ Question:Why move one pointer to head?✅ Answer:Because:One pointer is a away from startOther is also a away (via cycle)👉 Move both 1 step:They meet at:Cycle Start 🎯🔄 VisualizationHead → → → Cycle Start → → Meeting Point → → back to StartBoth pointers:One from headOne from meeting point👉 Same distance → meet at start🧩 Doubt 8: Can we use fast = 3 steps?❓ Question:Will this work?✅ Answer:Yes, BUT:Math becomes complexHarder to reasonNo extra benefit👉 So we use simplest:2 : 1 ratio🧠 Final Mental ModelThink in 3 steps:1. Different SpeedsFast moves faster → gap reduces2. Circular StructureCycle → positions repeat3. Guaranteed MeetingFinite positions + relative motion → collision🧩 TEMPLATE 1: Detect CycleListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ return true; }}return false;🧩 TEMPLATE 2: Find Cycle StartListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ slow = head; while(slow != fast){ slow = slow.next; fast = fast.next; } return slow; }}return null;🧩 TEMPLATE 3: Find Middle of Linked List❓ ProblemFind the middle node of a linked list.🧠 IntuitionFast moves twice as fast:When fast reaches end → slow reaches half👉 Slow = middle💻 CodeListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next;}return slow;⚠️ Even Length Case1 → 2 → 3 → 4 → 5 → 6👉 Returns 4 (second middle)❓ How to Get First Middle?while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next;}return slow;🧩 Where Else This Technique Is Used?Detect cycleFind cycle startFind middle nodeCheck palindrome (linked list)Split list (merge sort)Intersection problems⚙️ Time & Space ComplexityTime: O(n)Space: O(1)❌ Common MistakesForgetting fast.next != nullThinking meeting point = cycle start ❌Not resetting pointer properly🧠 Final Mental ModelThink in 3 steps:1. Speed DifferenceFast moves faster → gap reduces2. Circular NatureCycle → repeated positions3. Guaranteed MeetingFinite nodes + relative motion → collision🔥 One Line to RememberFast catches slow because it reduces the gap inside a loop.🚀 ConclusionNow you understand:✅ Why fast moves faster✅ Why they meet✅ Why meeting proves cycle✅ Why reset gives cycle start✅ How to find middle using same logic👉 This is not just a trick…It’s a mathematical guarantee based on motion and cycles.💡 Master this once, and you’ll solve multiple linked list problems easily.

Linked ListFast & Slow PointerTwo Pointer TechniqueFloyd AlgorithmDSA PatternsDeep Intuition

Search Blogs

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

LeetCode 36: Valid Sudoku Explained – Java Solutions, Intuition & Formula Dry Run

Fast and Slow Pointer Technique in Linked List: Cycle Detection, Proof, and Complete Explanation

Ai Assistant Kas