Search Blogs

Showing results for "Median"

Found 3 results

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

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

IntroductionQuick Sort is one of the most powerful and widely used sorting algorithms in computer science. It follows the Divide and Conquer approach and is known for its excellent average-case performance.What makes Quick Sort special is:It sorts in-place (no extra array required)It is faster in practice than many O(n log n) algorithms like Merge SortIt is heavily used in real-world systems and librariesIn this article, we’ll go deep into:Intuition behind Quick SortPartition logic (most important part)Step-by-step dry runJava implementation with commentsTime complexity analysisCommon mistakes and optimizations🔗 Problem LinkGeeksforGeeks: Quick SortProblem StatementGiven an array arr[], sort it in ascending order using Quick Sort.Requirements:Use Divide and ConquerChoose pivot elementPlace pivot in correct positionElements smaller → left sideElements greater → right sideExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [2, 1, 6, 10, 4, 1, 3, 9, 7]Output:[1, 1, 2, 3, 4, 6, 7, 9, 10]Core Idea of Quick SortPick a pivot → Place it correctly → Recursively sort left & right🔥 Key Insight (Partition is Everything)Quick Sort depends entirely on partitioning:👉 After partition:Pivot is at its correct sorted positionLeft side → smaller elementsRight side → larger elementsIntuition (Visual Understanding)Consider:[4, 1, 3, 9, 7]Step 1: Choose PivotLet’s say pivot = 4Step 2: Rearrange Elements[1, 3] 4 [9, 7]Now:Left → smallerRight → largerStep 3: Apply RecursivelyLeft: [1, 3]Right: [9, 7]Final result:[1, 3, 4, 7, 9]Partition Logic (Most Important)Your implementation uses:Pivot = first elementTwo pointers:i → moves forwardj → moves backwardJava Codeclass Solution { public void quickSort(int[] arr, int low, int high) { // Base case: if array has 1 or 0 elements if (low < high) { // Partition array and get pivot index int pivotInd = partition(arr, low, high); // Sort left part quickSort(arr, low, pivotInd - 1); // Sort right part quickSort(arr, pivotInd + 1, high); } } // Function to swap two elements void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private int partition(int[] arr, int low, int high) { int pivot = arr[low]; // choosing first element as pivot int i = low + 1; // start from next element int j = high; // start from end while (i <= j) { // Move i forward until element > pivot while (i <= high && arr[i] <= pivot) { i++; } // Move j backward until element <= pivot while (j >= low && arr[j] > pivot) { j--; } // Swap if pointers haven't crossed if (i < j) { swap(arr, i, j); } } // Place pivot at correct position swap(arr, low, j); return j; // return pivot index }}Step-by-Step Dry RunInput:[4, 1, 3, 9, 7]Execution:Pivot = 4i → moves until element > 4j → moves until element ≤ 4Swaps happen → pivot placed correctlyFinal partition:[1, 3, 4, 9, 7]Complexity AnalysisTime ComplexityCaseComplexityBest CaseO(n log n)Average CaseO(n log n)Worst CaseO(n²)Why Worst Case Happens?When array is:Already sortedReverse sortedPivot always becomes smallest/largest.Space ComplexityO(log n) (recursion stack)❌ Common MistakesWrong partition logicInfinite loops in while conditionsIncorrect pivot placementNot handling duplicates properly⚡ Optimizations1. Random PivotAvoid worst-case:int pivotIndex = low + new Random().nextInt(high - low + 1);swap(arr, low, pivotIndex);2. Median of ThreeChoose better pivot:median(arr[low], arr[mid], arr[high])Quick Sort vs Merge SortFeatureQuick SortMerge Sort link to get moreSpaceO(log n)O(n)SpeedFaster (practical)StableWorst CaseO(n²)O(n log n)Why Quick Sort is PreferredCache-friendlyIn-place sortingFaster in real-world scenariosKey TakeawaysPartition is the heart of Quick SortPivot must be placed correctlyRecursion splits problem efficientlyAvoid worst case using random pivotWhen to Use Quick SortLarge arraysMemory constraints (in-place)Performance-critical applicationsConclusionQuick Sort is one of the most efficient and practical sorting algorithms. Mastering its partition logic is crucial for solving advanced problems and performing well in coding interviews.Understanding how pointers move and how pivot is placed will make this algorithm intuitive and powerful.Frequently Asked Questions (FAQs)1. Is Quick Sort stable?No, it is not stable.2. Why is Quick Sort faster than Merge Sort?Because it avoids extra space and is cache-efficient.3. What is the most important part?👉 Partition logic

MediumJavaSortingQuick SortGeeksofGeeks