Search Blogs

Showing results for "Math"

Found 8 results

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

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

🔗 Problem LinkLeetCode 389 – Find the Difference 👉 https://leetcode.com/problems/find-the-difference/IntroductionThis is a very clever problem.At first glance, you might think:Use a HashMapCount frequenciesCompare both stringsBut there’s a much smarter and cleaner way to solve it using character arithmetic (ASCII values).This problem teaches an important lesson:Sometimes math can replace extra space.Let’s break it down.📌 Problem UnderstandingYou are given two strings:stString t is created by:Shuffling string sAdding one extra character at a random positionYour task:Return the extra character added to t.Example 1Input: s = "abcd" t = "abcde"Output: "e"Example 2Input: s = "" t = "y"Output: "y"🧠 First Intuition (Brute Force Thinking)When solving this for the first time, a common approach would be:Count frequency of characters in sCount frequency of characters in tCompare bothThe one with extra count is the answerThat works in O(n) time and O(26) space.But we can do better.🚀 Smarter Approach – ASCII Sum Trick💡 Key InsightCharacters are stored as integer ASCII values.If:We add all ASCII values of characters in tSubtract all ASCII values of characters in sWhat remains?👉 The ASCII value of the extra character.Because:All matching characters cancel out.Only the added character remains.💻 Your Codeclass Solution { public char findTheDifference(String s, String t) { int tot = 0; for(int i = 0; i < t.length(); i++){ tot += (int)t.charAt(i); } for(int i = 0; i < s.length(); i++){ tot -= (int)s.charAt(i); } return (char)tot; }}🔍 Step-by-Step Explanation1️⃣ Initialize Totalint tot = 0;This will store the running ASCII difference.2️⃣ Add All Characters of ttot += (int)t.charAt(i);We add ASCII values of every character in t.3️⃣ Subtract All Characters of stot -= (int)s.charAt(i);We subtract ASCII values of every character in s.4️⃣ Return Remaining Characterreturn (char)tot;After subtraction, only the extra character’s ASCII value remains.We convert it back to char.🎯 Why This WorksLet’s take example:s = "abcd"t = "abcde"ASCII Sum:t = a + b + c + d + es = a + b + c + dSubtract:(t sum) - (s sum) = eEverything cancels except the extra letter.Simple and powerful.⏱ Complexity AnalysisTime Complexity: O(n)One loop over tOne loop over sSpace Complexity: O(1)No extra data structure used.🔥 Even Smarter Approach – XOR TrickAnother elegant method is using XOR:Why XOR Works?Properties:a ^ a = 0a ^ 0 = aXOR is commutativeIf we XOR all characters in both strings:Matching characters cancel out.Only the extra character remains.XOR Versionclass Solution { public char findTheDifference(String s, String t) { char result = 0; for(char c : s.toCharArray()){ result ^= c; } for(char c : t.toCharArray()){ result ^= c; } return result; }}This is considered the most elegant solution.🏁 Final ThoughtsThis problem teaches:Thinking beyond brute forceUsing mathematical propertiesUnderstanding ASCII representationUsing XOR smartlySometimes the best solution is not about data structures — it’s about recognizing hidden math patterns.

StringMath TrickASCIIBit ManipulationLeetCodeEasy

LeetCode 258 — Add Digits | Brute Force to O(1) Digital Root Trick Explained in Java

IntroductionSome problems on LeetCode look too simple to teach you anything meaningful. LeetCode 258 — Add Digits is one of those problems that tricks you with its simplicity. The simulation is beginner-friendly and easy to code in five minutes, but hiding right underneath the surface is a beautiful piece of number theory that lets you solve the entire thing in a single arithmetic expression — no loops, no recursion, pure O(1) math.Whether you are just starting your DSA journey or preparing for coding interviews, this problem is worth understanding deeply. Not just for the answer, but for the mathematical intuition that produces it. By the end of this article, you will not just know the formula — you will understand exactly why it works, where it comes from, and how to derive it yourself even if you forget it during an interview.Problem LinkLeetCode 258 — Add Digits https://leetcode.com/problems/add-digits/Problem StatementGiven an integer num, repeatedly add all its digits until the result has only one digit, and return it.The follow-up asks: can you solve this in O(1) time without any loop or recursion?Approach 1 — Simulation (The Intuitive Way)IntuitionThe problem statement itself tells you exactly what to do. Keep summing the digits of the number until you are left with a single digit. You simulate this literally using nested loops.To extract digits from any integer, two operations do all the work:num % 10 isolates the rightmost digit. For 38, that gives 8.num / 10 removes the rightmost digit. For 38, that leaves 3.You accumulate the digits into a sum, replace num with that sum, and repeat the whole process until num drops below 10.Dry Runnum = 38Outer loop iteration 1:38 % 10 = 8 → sum = 8, num = 33 % 10 = 3 → sum = 11, num = 0Inner loop ends. num = 11Outer loop iteration 2:11 % 10 = 1 → sum = 1, num = 11 % 10 = 1 → sum = 2, num = 0Inner loop ends. num = 2num < 10 → outer loop exits → return 2 ✅Codeclass Solution { public int addDigits(int num) { // If already a single digit, return immediately — no work needed if (num < 10) return num; // Keep repeating the digit sum process until num becomes single digit while (num >= 10) { int sum = 0; // Extract each digit from right to left using modulo and division while (num > 0) { int dig = num % 10; // isolate the last digit num = num / 10; // strip the last digit off sum = sum + dig; // accumulate into running sum } // Replace num with the sum of its digits and check again num = sum; } return num; }}ComplexityTime Complexity: O(log n) — Each iteration reduces the number to the sum of its digits, shrinking it dramatically. The number of passes is very small even for large inputs.Space Complexity: O(1) — Only a handful of integer variables. No extra memory allocated.This passes all test cases cleanly. But the follow-up challenges you to eliminate the loop entirely. That is where things get genuinely interesting.Approach 2 — O(1) Digital Root Formula (The Mathematical Way)Starting With ObservationBefore jumping to the formula, let us build the intuition from scratch the way a mathematician would — by looking at small cases and hunting for a pattern.Let us compute the result for every number from 0 to 27 manually:num → result0 → 01 → 12 → 23 → 34 → 45 → 56 → 67 → 78 → 89 → 910 → 1 (1+0)11 → 2 (1+1)12 → 3 (1+2)13 → 4 (1+3)14 → 5 (1+4)15 → 6 (1+5)16 → 7 (1+6)17 → 8 (1+7)18 → 9 (1+8)19 → 1 (1+9=10, then 1+0=1)20 → 2 (2+0)21 → 3 (2+1)22 → 4 (2+2)23 → 5 (2+3)24 → 6 (2+4)25 → 7 (2+5)26 → 8 (2+6)27 → 9 (2+7)The pattern is impossible to miss. After 0, the results cycle through 1, 2, 3, 4, 5, 6, 7, 8, 9 and then repeat, endlessly, with a period of exactly 9.Now the question is — why? Why does the digit sum cycle with period 9? To understand that, we need to talk about what happens to a number modulo 9.The Core Mathematical Property — Why Digits and Modulo 9 Are ConnectedHere is the fundamental theorem that powers this entire solution:Any positive integer is congruent to the sum of its digits modulo 9.In plain English: if you take a number, divide it by 9, and note the remainder — that remainder is the same as the remainder you get when you divide the sum of its digits by 9.Let us prove this properly so it actually makes sense rather than just being a thing you memorize.Take any two-digit number. You can write it as:num = 10a + bWhere a is the tens digit and b is the units digit. For example, 38 = 10(3) + 8.Now notice that 10 = 9 + 1, so:num = (9 + 1)a + b = 9a + a + bWhen you compute num % 9:num % 9 = (9a + a + b) % 9 = (9a % 9) + (a + b) % 9 = 0 + (a + b) % 9 = (a + b) % 9And a + b is exactly the digit sum. So num % 9 = digitSum % 9. They share the same remainder modulo 9.This same logic extends to three-digit numbers. Write num = 100a + 10b + c. Since 100 = 99 + 1 and 10 = 9 + 1:num = (99 + 1)a + (9 + 1)b + c = 99a + 9b + a + b + cWhen you take % 9, the 99a and 9b parts vanish because they are divisible by 9, and you are left with (a + b + c) % 9 — which is again just the digit sum modulo 9.This pattern holds for numbers of any length. Every power of 10 is just 1 more than a multiple of 9 — 10 = 9+1, 100 = 99+1, 1000 = 999+1 — so all the place-value multipliers disappear modulo 9, leaving only the digit sum behind.This is the reason the digit sum process produces the same final result as the original number modulo 9. The digit sum operation preserves the residue modulo 9 at every step.Why the Cycle Has Period 9Now that we know num ≡ digitSum (mod 9), the cycling pattern makes total sense.Every time you apply the digit sum operation, the result changes but the residue modulo 9 stays the same. You keep applying it until you hit a single digit. The single-digit numbers are 0 through 9. Among those, the residue modulo 9 of each single digit is just the digit itself — except 9, whose residue is 0.So the final single digit you land on is determined entirely by what num % 9 is:num % 9 == 0 → result is 9 (for any positive num)num % 9 == 1 → result is 1num % 9 == 2 → result is 2...num % 9 == 8 → result is 8The only exception is num = 0 itself, which is a genuine zero, not a nine.Translating This Into a FormulaIf we tried to write this directly as num % 9, there is one problem: multiples of 9 like 9, 18, 27 give a remainder of 0, but the correct answer for all of them is 9, not 0.We need a formula that maps every positive integer to a value in 1..9 cyclically, rather than 0..8.The standard trick for shifting a zero-indexed cycle to a one-indexed cycle is to subtract 1 before taking the modulo and add 1 after:result = 1 + (num - 1) % 9Let us verify this on a few cases:num = 9: 1 + (9-1) % 9 = 1 + 8 % 9 = 1 + 8 = 9 ✅num = 18: 1 + (18-1) % 9 = 1 + 17 % 9 = 1 + 8 = 9 ✅num = 1: 1 + (1-1) % 9 = 1 + 0 = 1 ✅num = 10: 1 + (10-1) % 9 = 1 + 9 % 9 = 1 + 0 = 1 ✅num = 38: 1 + (38-1) % 9 = 1 + 37 % 9 = 1 + 1 = 2 ✅The only number this formula does not cover is num = 0, which is a special case handled separately since 0 has no digit sum cycle — it simply returns 0.Connecting It Back to the ObservationNow look at the table we built earlier through the lens of this formula. Numbers 1 through 9 map to themselves. Then 10 gives 1 + 0 = 1, same as 1. Numbers 10 through 18 are just 1 through 9 offset by 9. Then 19 wraps back to 1. The cycle length of 9 follows directly from the modulo-9 arithmetic. It is not a coincidence at all — it is the inevitable consequence of how place-value and modular arithmetic interact.Codeclass Solution { public int addDigits(int num) { // Special case: 0 is not part of the 1-9 cycle, it simply returns 0 if (num == 0) return 0; // Digital root formula derived from the congruence property modulo 9. // (num - 1) % 9 maps the range to 0..8 instead of the raw 0..8 cycle // that would make multiples of 9 return 0 incorrectly. // Adding 1 at the end shifts it back to the correct 1..9 range. return 1 + (num - 1) % 9; }}ComplexityTime Complexity: O(1) — A fixed number of arithmetic operations regardless of the size of num.Space Complexity: O(1) — No variables, no data structures, nothing allocated.Approach ComparisonApproachTimeSpaceLoop / RecursionSimulationO(log n)O(1)YesDigital Root FormulaO(1)O(1)NoBoth approaches are entirely correct and both pass all test cases. The simulation is more readable and immediately obvious to anyone reading the code. The digital root formula is what an interviewer is hoping you know when they ask the follow-up — and more importantly, if you understand the modulo-9 proof above, you can derive it on the spot rather than hoping you remembered it.Key TakeawaysThe most important thing this problem teaches you is not the formula itself. It is the habit of asking a deeper question when you see a repeated process: is there a closed-form mathematical pattern hiding inside this repetition?The digit sum operation looks like pure computation at first glance. But underneath it is modular arithmetic, and modular arithmetic has structure that can often be collapsed into a direct formula. That same insight — that repeated digit operations connect to modulo 9 — shows up in divisibility rules you learned in school. A number is divisible by 9 if and only if its digit sum is divisible by 9. A number is divisible by 3 if and only if its digit sum is divisible by 3. Both of those rules are the exact same theorem we used to derive the digital root formula here.Once you internalize this connection between digit sums and modulo 9, you will recognize it surfacing in other problems across number theory, checksum algorithms, and competitive programming. The formula is a one-liner. The understanding behind it is something you carry with you permanently.

Digital RootLeetCode EasyJavaNumber TheoryMath

LeetCode 2033: Minimum Operations to Make a Uni-Value Grid | Java Solution Explained (Median Approach)

IntroductionIn this problem, we are given a 2D grid and an integer x.We can perform one operation where we either:Add x to any grid elementSubtract x from any grid elementOur goal is to make all elements in the grid equal using the minimum number of operations.If making all values equal is not possible, we return -1.This problem may initially look like a matrix manipulation question, but the actual logic is based on:Array transformationMedian propertyGreedy optimization# Problem LinkProblem StatementYou are given:A 2D integer grid of size m × nAn integer xYou can perform operations where you add or subtract x from any cell.A grid becomes uni-value when all elements become equal.Return the minimum number of operations needed.If impossible, return -1.ExampleExample 1Input:grid = [[2,4],[6,8]]x = 2Output:4Explanation:We can make every element equal to 4.2 → 4 (1 operation)6 → 4 (1 operation)8 → 4 (2 operations)Total = 4 operations.Key ObservationBefore solving the problem, we must understand one important rule.If we can add or subtract only x, then:All numbers must belong to the same remainder group when divided by x.Meaning:value % x must be same for every elementWhy?Because if two numbers have different remainders, they can never become equal using only +x or -x operations.IntuitionWe need to convert all numbers into a single target value.But what target value gives minimum operations?The answer is:MedianFor minimizing total absolute distance, median gives the optimal answer.Since every operation changes value by x, we can:Flatten grid into a listSort the listPick median as targetCalculate operations requiredWhy Median Works?Median minimizes:Sum of absolute differencesFor example:Numbers = [1, 2, 3, 10]If target = 2|1-2| + |2-2| + |3-2| + |10-2| = 10If target = 5|1-5| + |2-5| + |3-5| + |10-5| = 14Median gives minimum total distance.Approach 1: Brute ForceWe can try every possible number as target.For each target:Calculate operations requiredStore minimum answerTime ComplexityO(N²)Where N = total grid elementsThis is slow for large constraints.Approach 2: Optimal Median ApproachThis is the best approach.StepsStep 1: Flatten GridConvert 2D grid into 1D array.Step 2: Sort ArraySorting helps us find median.Step 3: Check ValidityAll values must have same remainder when divided by x.value % x must matchOtherwise return -1.Step 4: Pick MedianMedian minimizes operations.Step 5: Count OperationsFor every element:operations += abs(value - median) / xJava Solutionclass Solution {public int minOperations(int[][] grid, int x) {List<Integer> lis = new ArrayList<>();for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {lis.add(grid[i][j]);}}Collections.sort(lis);int mid = lis.size() / 2;int remainder = lis.get(0) % x;for (int value : lis) {if (value % x != remainder) {return -1;}}int ans = 0;for (int value : lis) {int diff = Math.abs(lis.get(mid) - value);ans += diff / x;}return ans;}}Code ExplanationStep 1: Flatten Matrixlis.add(grid[i][j]);We convert grid into list.Step 2: Sort ListCollections.sort(lis);Sorting allows median selection.Step 3: Check Possibilityif(value % x != remainder)If remainders differ, answer becomes impossible.Step 4: Select Medianint mid = lis.size()/2;Median becomes target value.Step 5: Calculate Operationsans += diff/x;Difference divided by x gives operations.Dry RunInput:grid = [[2,4],[6,8]]x = 2Flatten:[2,4,6,8]Sort:[2,4,6,8]Median:6Operations:2 → 6 = 2 operations4 → 6 = 1 operation6 → 6 = 0 operation8 → 6 = 1 operationTotal:4 operationsTime ComplexityFlatten GridO(N)SortingO(N log N)Traverse ArrayO(N)Total ComplexityO(N log N)Where:N = m × nSpace ComplexityWe store all elements in list.O(N)Common Mistakes1. Forgetting Mod CheckMany people directly calculate operations.But without checking:value % xanswer may become invalid.2. Choosing Average Instead of MedianAverage does not minimize absolute distance.Median is required.3. Not Sorting Before Finding MedianMedian requires sorted array.4. Forgetting Division by xOperations are not direct difference.Correct formula:abs(target - value) / xEdge CasesCase 1All values already equal.Answer = 0Case 2Different modulo values.Return -1Case 3Single cell grid.No operation neededFAQsQ1. Why do we use median?Median minimizes total absolute difference.Q2. Why not average?Average minimizes squared distance, not absolute operations.Q3. Why modulo condition is important?Because we can only move by multiples of x.Q4. Can we solve without sorting?Sorting is easiest way to get median.Alternative median-finding algorithms exist but are unnecessary here.Interview InsightInterviewers ask this problem to test:Greedy thinkingMedian propertyMathematical observationArray flatteningOptimization logicConclusionLeetCode 2033 is a great problem that combines math with greedy logic.The most important learning points are:Flatten the gridValidate modulo conditionUse median as targetCalculate operations using difference divided by xThis approach is optimal and easy to implement.Once you understand why median works, this problem becomes very straightforward.

ArraySortingMathMedianMediumMatrixGridLeetCodeJava

LeetCode 3783 Mirror Distance of an Integer | Java Solution Explained

IntroductionSome problems test complex algorithms, while others focus on fundamental concepts done right.LeetCode 3783 – Mirror Distance of an Integer falls into the second category.This problem is simple yet important because it builds understanding of:Digit manipulationReversing numbersMathematical operationsIn this article, we’ll break down the problem in a clean and intuitive way, along with an optimized Java solution.🔗 Problem LinkLeetCode: Mirror Distance of an IntegerProblem StatementYou are given an integer n.The mirror distance is defined as:| n - reverse(n) |Where:reverse(n) = number formed by reversing digits of n|x| = absolute value👉 Return the mirror distance.ExamplesExample 1Input:n = 25Output:27Explanation:reverse(25) = 52|25 - 52| = 27Example 2Input:n = 10Output:9Explanation:reverse(10) = 1|10 - 1| = 9Example 3Input:n = 7Output:0Key InsightThe problem consists of two simple steps:1. Reverse the number2. Take absolute differenceIntuitionLet’s take an example:n = 120Step 1: Reverse digits120 → 021 → 21👉 Leading zeros are ignored automatically.Step 2: Compute difference|120 - 21| = 99ApproachStep-by-StepExtract digits using % 10Build reversed numberUse Math.abs() for final resultJava Codeclass Solution { // Function to reverse a number public int reverse(int k) { int rev = 0; while (k != 0) { int dig = k % 10; // get last digit k = k / 10; // remove last digit rev = rev * 10 + dig; // build reversed number } return rev; } public int mirrorDistance(int n) { // Calculate mirror distance return Math.abs(n - reverse(n)); }}Dry RunInput:n = 25Execution:Reverse → 52Difference → |25 - 52| = 27Complexity AnalysisTime ComplexityReversing number → O(d)(d = number of digits)👉 Overall: O(log n)Space Complexity👉 O(1) (no extra space used)Why This WorksDigit extraction ensures correct reversalLeading zeros automatically removedAbsolute difference ensures positive resultEdge Cases to ConsiderSingle digit → result = 0Numbers ending with zero (e.g., 10 → 1)Large numbers (up to 10⁹)Key TakeawaysSimple math problems can test core logicDigit manipulation is a must-know skillAlways handle leading zeros carefullyUse built-in functions like Math.abs() effectivelyReal-World RelevanceConcepts used here are helpful in:Number transformationsPalindrome problemsReverse integer problemsMathematical algorithmsConclusionThe Mirror Distance of an Integer problem is a great example of combining basic operations to form a meaningful solution.While simple, it reinforces important programming fundamentals that are widely used in more complex problems.Frequently Asked Questions (FAQs)1. What happens to leading zeros in reverse?They are automatically removed when stored as an integer.2. Can this be solved using strings?Yes, but integer-based approach is more efficient.3. What is the best approach?Using arithmetic operations (% and /) is optimal.

EasyArrayReverse NumberLeetCodeJava

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

LeetCode 462: Minimum Moves to Equal Array Elements II | Java Solution Explained (Median Approach)

IntroductionLeetCode 462 is a classic mathematical and greedy problem.We are given an integer array where each operation allows us to:Increment an element by 1Decrement an element by 1Our task is to make all numbers equal while using the minimum number of moves.At first glance, this may look like a simple array problem.But the hidden concept behind this question is:Median propertyGreedy optimizationAbsolute difference minimizationThis problem is extremely popular in coding interviews because it tests logical thinking more than coding complexity.# Problem LinkProblem StatementYou are given an integer array nums.In one move:You can increase an element by 1Or decrease an element by 1You must make all array elements equal.Return the minimum number of operations required.Example 1Input:nums = [1,2,3]Output:2Explanation:[1,2,3]→ [2,2,3]→ [2,2,2]Total operations = 2Example 2Input:nums = [1,10,2,9]Output:16Key ObservationWe need to choose one target value such that all numbers move toward it.Question:Which target gives minimum total moves?Answer:MedianMedian minimizes the sum of absolute differences.Why Median Works?Suppose:nums = [1,2,3,10]If target = 2|1-2| + |2-2| + |3-2| + |10-2|= 1 + 0 + 1 + 8= 10If target = 5|1-5| + |2-5| + |3-5| + |10-5|= 4 + 3 + 2 + 5= 14Median gives minimum moves.Approach 1: Brute ForceIn this approach, we try every possible value as target.For each target:Calculate total operations neededStore minimum answerAlgorithmFind minimum and maximum elementTry every value between themCompute total movesReturn minimumJava Code (Brute Force)class Solution {public int minMoves2(int[] nums) {int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int num : nums) {min = Math.min(min, num);max = Math.max(max, num);}int result = Integer.MAX_VALUE;for (int target = min; target <= max; target++) {int moves = 0;for (int num : nums) {moves += Math.abs(num - target);}result = Math.min(result, moves);}return result;}}Time ComplexityO(N × Range)Very slow for large values.Approach 2: Sorting + Median (Optimal)This is the best and most commonly used approach.IdeaSort arrayPick median elementCalculate total absolute differenceStepsStep 1: Sort ArraySorting helps us easily find median.Step 2: Pick MedianMedian index = n / 2Step 3: Calculate MovesFor every element:moves += abs(median - value)Optimal Java Solutionclass Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int mid = nums.length / 2;int ans = 0;for (int i = 0; i < nums.length; i++) {int diff = Math.abs(nums[mid] - nums[i]);ans += diff;}return ans;}}Code ExplanationStep 1: Sort ArrayArrays.sort(nums);Sorting allows median calculation.Step 2: Get Medianint mid = nums.length / 2;Middle element becomes target.Step 3: Compute DifferenceMath.abs(nums[mid] - nums[i])Find distance from median.Step 4: Add All Movesans += diff;Store total moves.Approach 3: Two Pointer OptimizationAfter sorting, we can use two pointers.Instead of calculating absolute difference manually, we can pair smallest and largest values.IdeaAfter sorting:moves += nums[right] - nums[left]Because both numbers will meet toward median.Java Code (Two Pointer)class Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int left = 0;int right = nums.length - 1;int moves = 0;while (left < right) {moves += nums[right] - nums[left];left++;right--;}return moves;}}Why Two Pointer Works?Because:Median minimizes total distancePairing smallest and largest values gives direct movement cost.Dry RunInput:nums = [1,10,2,9]Sort:[1,2,9,10]Median:9Operations:|1-9| = 8|2-9| = 7|9-9| = 0|10-9| = 1Total:16Time ComplexitySortingO(N log N)TraversingO(N)TotalO(N log N)Space ComplexityO(1)Ignoring sorting stack.Common Mistakes1. Using Average Instead of MedianMany people think average gives minimum.Wrong.Average minimizes squared difference.Median minimizes absolute difference.2. Forgetting SortingMedian requires sorted order.3. Overflow IssueValues can be large.Sometimes use:long ansfor safer calculation.4. Using Wrong Median IndexCorrect:n / 2Edge CasesCase 1Single element array.Answer = 0Case 2All elements already equal.Answer = 0Case 3Negative numbers.Algorithm still works.FAQsQ1. Why median gives minimum moves?Median minimizes total absolute difference.Q2. Can average work?No.Average does not minimize absolute distance.Q3. Is sorting necessary?Yes.Sorting helps us easily find median.Q4. Which approach is best?Sorting + median approach.Interview InsightInterviewers ask this problem to test:Median property understandingGreedy optimizationMathematical thinkingArray manipulationConclusionLeetCode 462 is one of the most important median-based interview questions.The major learning is:Median minimizes total absolute differenceSorting makes finding median easySum of distances gives answerOnce you understand why median works, this question becomes very simple.

MathMedianMediumLeetCodeJavaArrayTwo PointerSorting

LeetCode 2: Add Two Numbers – Step-by-Step Linked List Addition Explained Clearly

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/add-two-numbers/Problem Description (In Simple Words)You are given two linked lists, where:Each node contains a single digit (0–9)The digits are stored in reverse order👉 That means:[2,4,3] represents 342[5,6,4] represents 465Your task is:👉 Add these two numbers👉 Return the result as a linked list (also in reverse order)Important Points to UnderstandEach node contains only one digitNumbers are stored in reverse orderYou must return the answer as a linked listYou must handle carry just like normal additionExample WalkthroughExample 1Input:l1 = [2,4,3]l2 = [5,6,4]Interpretation:342 + 465 = 807Output:[7,0,8]Example 2Input:l1 = [0]l2 = [0]Output:[0]Example 3Input:l1 = [9,9,9,9,9,9,9]l2 = [9,9,9,9]Output:[8,9,9,9,0,0,0,1]Constraints1 <= number of nodes <= 1000 <= Node.val <= 9No leading zeros except the number 0Understanding the Core IdeaThis problem is essentially:👉 Adding two numbers digit by digitBut instead of arrays or integers, the digits are stored in linked lists.How Addition Works (Real-Life Analogy)Let’s add:342 + 465We normally add from right to left:2 + 5 = 74 + 6 = 10 → write 0, carry 13 + 4 + 1 = 8Now notice something important:👉 Linked list is already in reverse order👉 So we can directly process from left to rightThinking About the SolutionBefore coding, let’s think of possible approaches:Possible Ways to SolveConvert linked lists into numbers → add → convert back (Not safe due to overflow)Store digits in arrays and simulate additionTraverse both lists and simulate addition directly (best approach)Optimal Approach: Simulate Addition (Digit by Digit)Key IdeaWe traverse both linked lists and:Add corresponding digitsMaintain a carryCreate a new node for each digit of resultStep-by-Step LogicStep 1: InitializeCreate a dummy node (to simplify result building)Create a pointer curr to build the result listInitialize carry = 0Step 2: Traverse Both ListsContinue while:l1 != null OR l2 != nullAt each step:Start with carry:sum = carryAdd value from l1 (if exists)Add value from l2 (if exists)Step 3: Create New NodeDigit to store:sum % 10New carry:sum / 10Step 4: Move ForwardMove l1 and l2 if they existMove curr forwardStep 5: Handle Remaining CarryIf carry is not zero after loop:👉 Add one more nodeStep 6: Return ResultReturn:dummy.nextCode Implementation (With Explanation)class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // Dummy node to simplify result construction ListNode dumm = new ListNode(-1); ListNode curr = dumm; int sum = 0; int carr = 0; // Traverse both lists while(l1 != null || l2 != null){ // Start with carry sum = carr; // Add l1 value if exists if(l1 != null){ sum += l1.val; l1 = l1.next; } // Add l2 value if exists if(l2 != null){ sum += l2.val; l2 = l2.next; } // Create new node with digit ListNode newNode = new ListNode(sum % 10); // Update carry carr = sum / 10; // Attach node curr.next = newNode; curr = curr.next; } // If carry remains if(carr != 0){ curr.next = new ListNode(carr); } return dumm.next; }}Dry Run (Important for Understanding)Input:l1 = [2,4,3]l2 = [5,6,4]Step-by-step:Step 1:2 + 5 = 7 → node(7), carry = 0Step 2:4 + 6 = 10 → node(0), carry = 1Step 3:3 + 4 + 1 = 8 → node(8), carry = 0Final:7 → 0 → 8Time ComplexityO(max(n, m))Where:n = length of l1m = length of l2Space ComplexityO(max(n, m))For storing the result linked list.Why Dummy Node is ImportantWithout dummy node:You need to handle first node separatelyWith dummy node:Code becomes clean and consistentNo special cases requiredCommon Mistakes to Avoid❌ Forgetting to handle carry❌ Not checking if l1 or l2 is null❌ Missing last carry node❌ Incorrect pointer movementKey TakeawaysThis is a simulation problemLinked list problems become easier with dummy nodesAlways think in terms of real-world analogy (addition)ConclusionThe Add Two Numbers problem is one of the most important linked list problems for interviews.It teaches:Pointer manipulationCarry handlingIterative traversalClean code using dummy nodesOnce you understand this pattern, many other linked list problems become much easier to solve.👉 Tip: Whenever you see problems involving numbers in linked lists, think of digit-by-digit simulation with carry.

Linked ListMathSimulationCarry HandlingDummy NodeLeetCode Medium