Search Blogs

Showing results for "Two Pointer"

Found 30 results

LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

IntroductionLeetCode 1855 – Maximum Distance Between a Pair of Values is a classic problem that beautifully demonstrates the power of the Two Pointer technique on sorted (non-increasing) arrays.At first glance, it may feel like a brute-force problem—but using the right observation, it can be solved efficiently in O(n) time.In this article, we will cover:Problem intuitionWhy brute force failsOptimized two-pointer approach (your solution)Alternative approachesTime complexity analysis🔗 Problem LinkLeetCode: Maximum Distance Between a Pair of ValuesProblem StatementYou are given two non-increasing arrays:nums1nums2A pair (i, j) is valid if:i <= jnums1[i] <= nums2[j]👉 Distance = j - iReturn the maximum distance among all valid pairs.ExamplesExample 1Input:nums1 = [55,30,5,4,2]nums2 = [100,20,10,10,5]Output:2Key InsightThe most important observation:Both arrays are NON-INCREASING👉 This allows us to use two pointers efficiently instead of brute force.❌ Naive Approach (Brute Force)IdeaTry all (i, j) pairsCheck conditionsTrack maximumComplexityTime: O(n × m) ❌👉 This will cause TLE for large inputs (up to 10⁵)✅ Optimized Approach: Two PointersIntuitionUse two pointers:i → nums1j → nums2We try to:Expand j as far as possibleMove i only when necessaryKey LogicIf nums1[i] <= nums2[j] → valid → increase jElse → move i forwardJava Codeclass Solution { public int maxDistance(int[] nums1, int[] nums2) { int i = 0; // pointer for nums1 int j = 0; // pointer for nums2 int max = Integer.MIN_VALUE; // Traverse both arrays while (i < nums1.length && j < nums2.length) { // Valid pair condition if (nums1[i] <= nums2[j] && i <= j) { // Update maximum distance max = Math.max(max, j - i); // Try to expand distance by moving j j++; } else if (nums1[i] >= nums2[j]) { // nums1[i] is too large → move i forward i++; } else { // Just move j forward j++; } } // If no valid pair found, return 0 return max == Integer.MIN_VALUE ? 0 : max; }}Step-by-Step Dry RunInput:nums1 = [55,30,5,4,2]nums2 = [100,20,10,10,5]Execution:(0,0) → valid → distance = 0Move j → (0,1) → invalid → move iContinue...Final best pair:(i = 2, j = 4) → distance = 2Why This WorksArrays are sorted (non-increasing)Moving j increases distanceMoving i helps find valid pairs👉 No need to re-check previous elementsComplexity AnalysisTime ComplexityO(n + m)Each pointer moves at most once through the array.Space ComplexityO(1) (no extra space used)Alternative Approach: Binary SearchIdeaFor each i in nums1:Use binary search in nums2Find farthest j such that:nums2[j] >= nums1[i]ComplexityO(n log m)Code (Binary Search Approach)class Solution { public int maxDistance(int[] nums1, int[] nums2) { int max = 0; for (int i = 0; i < nums1.length; i++) { int left = i, right = nums2.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums2[mid] >= nums1[i]) { max = Math.max(max, mid - i); left = mid + 1; } else { right = mid - 1; } } } return max; }}Two Pointer vs Binary SearchApproachTimeSpaceTwo PointerO(n + m) ✅O(1)Binary SearchO(n log m)O(1)👉 Two pointer is optimal hereKey TakeawaysUse two pointers when arrays are sortedAlways look for monotonic propertiesAvoid brute force when constraints are largeGreedy pointer movement can optimize drasticallyCommon Interview PatternsThis problem is related to:Two pointer problemsSliding windowBinary search on arraysGreedy expansionConclusionThe Maximum Distance Between a Pair of Values problem is a great example of how recognizing array properties can drastically simplify the solution.By using the two-pointer technique, we reduce complexity from O(n²) to O(n)—a massive improvement.Frequently Asked Questions (FAQs)1. Why do we use two pointers?Because arrays are sorted, allowing linear traversal.2. Why not brute force?It is too slow for large inputs (10⁵).3. What is the best approach?👉 Two-pointer approach

MediumLeetCodeJavaArrayBinary SearchTwo Pointer

LeetCode 844: Backspace String Compare — Java Solution With All Approaches Explained

IntroductionLeetCode 844 Backspace String Compare is a fantastic problem that shows up frequently in coding interviews. It combines string manipulation, stack simulation, and even has a follow-up that challenges you to solve it in O(1) space — which is what separates a good candidate from a great one.Here is the Link of Question -: LeetCode 844In this article we cover a plain English explanation, real life analogy, 3 Java approaches including the O(1) space two pointer solution, dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You are given two strings s and t. Both contain lowercase letters and # characters. Think of # as the backspace key on your keyboard — it deletes the character just before it. If there is nothing to delete, it does nothing.Process both strings through these backspace operations and check if the resulting strings are equal. Return true if equal, false otherwise.Quick Example:s = "ab#c" → # deletes b → becomes "ac"t = "ad#c" → # deletes d → becomes "ac"Both equal "ac" → return true ✅Real Life Analogy — The Keyboard TypoYou are typing a message. You type "ab", realize you made a typo, hit backspace, and type "c". Your friend types "ad", hits backspace, and types "c". Even though you both typed differently, the final message on screen is the same — "ac".That is exactly what this problem is about. Two people typing differently but ending up with the same result.Approach 1: StringBuilder as Stack (Optimal & Clean) ✅The IdeaThis is your own solution and the best O(n) approach. Process each string independently using a StringBuilder as a stack:Letter → append to StringBuilder (push)# → delete last character if StringBuilder is not empty (pop)Then simply compare the two resulting StringBuilders.public boolean backspaceCompare(String s, String t) { return process(s).equals(process(t));}private String process(String str) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } } else { sb.append(c); } } return sb.toString();}Notice how extracting a process() helper method makes the code cleaner and avoids repeating the same loop twice — a great habit to show in interviews!Dry Run — s = "ab##", t = "c#d#"Processing s = "ab##":a → append → "a"b → append → "ab"# → delete last → "a"# → delete last → ""Processing t = "c#d#":c → append → "c"# → delete last → ""d → append → "d"# → delete last → ""Both result in "" → return true ✅Time Complexity: O(n + m) — where n and m are lengths of s and t Space Complexity: O(n + m) — two StringBuilders storing processed stringsApproach 2: Stack Based Solution (Interview Classic)The IdeaSame logic as above but using explicit Stack<Character> objects. Great for explaining your thought process clearly in an interview even though StringBuilder is cleaner.public boolean backspaceCompare(String s, String t) { return processStack(s).equals(processStack(t));}private String processStack(String str) { Stack<Character> st = new Stack<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (!st.empty()) { st.pop(); } } else { st.push(c); } } StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString();}Dry Run — s = "a#c", t = "b"Processing s = "a#c":a → push → stack: [a]# → pop → stack: []c → push → stack: [c]Result: "c"Processing t = "b":b → push → stack: [b]Result: "b""c" does not equal "b" → return false ✅Time Complexity: O(n + m) Space Complexity: O(n + m)Approach 3: Two Pointer — O(1) Space (Follow-Up Solution) 🔥This is the follow-up the problem asks about — can you solve it in O(n) time and O(1) space? This means no extra StringBuilder or Stack allowed.The IdeaInstead of building processed strings, traverse both strings from right to left simultaneously. Keep a count of pending backspaces. Skip characters that would be deleted and compare characters that survive.Why right to left? Because # affects characters to its left, so processing from the end lets us know upfront how many characters to skip.public boolean backspaceCompare(String s, String t) { int i = s.length() - 1; int j = t.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { // Find next valid character in s while (i >= 0) { if (s.charAt(i) == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } } // Find next valid character in t while (j >= 0) { if (t.charAt(j) == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } // Compare the valid characters if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) { return false; } } else if (i >= 0 || j >= 0) { return false; // one string still has chars, other doesn't } i--; j--; } return true;}Dry Run — s = "ab#c", t = "ad#c"Starting from the right end of both strings:Round 1:s[3] = 'c' → valid, no skips → stopt[3] = 'c' → valid, no skips → stopCompare 'c' == 'c' ✅ → move both pointers leftRound 2:s[2] = '#' → skipS = 1, move lefts[1] = 'b' → skipS > 0, skipS = 0, move lefts[0] = 'a' → valid, stopt[2] = '#' → skipT = 1, move leftt[1] = 'd' → skipT > 0, skipT = 0, move leftt[0] = 'a' → valid, stopCompare 'a' == 'a' ✅ → move both pointers leftBoth pointers exhausted → return true ✅Time Complexity: O(n + m) — each character visited at most once Space Complexity: O(1) — only pointer and counter variables, no extra storage!Approach ComparisonThe StringBuilder approach is the easiest to write and explain. The Stack approach is slightly more verbose but shows clear intent. The Two Pointer approach is the hardest to code but the most impressive — it solves the follow-up and uses zero extra space.In an interview, start with the StringBuilder solution, explain it clearly, then mention the Two Pointer approach as the O(1) space optimization if asked.How This Fits the Stack Simulation PatternYou have now seen this same pattern across four problems:3174 Clear Digits — digit deletes closest left non-digit 2390 Removing Stars — star deletes closest left non-star 1047 Remove Adjacent Duplicates — character cancels matching top of stack 844 Backspace String Compare — # deletes closest left character, then compare two stringsAll four use the same StringBuilder-as-stack core. The only differences are the trigger character and what you do with the result. This is the power of pattern recognition in DSA.Common Mistakes to AvoidNot handling backspace on empty string When # appears but the StringBuilder is already empty, do nothing. Always guard with sb.length() > 0 before calling deleteCharAt. The problem explicitly states backspace on empty text keeps it empty.Using Stack and forgetting to handle # when stack is empty In the Stack approach, only pop if the stack is not empty. Pushing # onto the stack when it is empty is a common bug that gives wrong answers.In Two Pointer, comparing before both pointers find valid characters Make sure both inner while loops fully complete before comparing. Comparing too early is the most common mistake in the O(1) space solution.FAQs — People Also AskQ1. What is the best approach for LeetCode 844 in Java? For most interviews, the StringBuilder approach is the best — clean, readable, and O(n) time. If the interviewer asks for O(1) space, switch to the Two Pointer approach traversing from right to left.Q2. How does the O(1) space solution work for LeetCode 844? It uses two pointers starting from the end of both strings, keeping a skip counter to track pending backspaces. Characters that would be deleted are skipped, and only surviving characters are compared.Q3. What is the time complexity of LeetCode 844? All three approaches run in O(n + m) time where n and m are the lengths of the two strings. The Two Pointer approach achieves this with O(1) space instead of O(n + m).Q4. Why traverse from right to left in the Two Pointer approach? Because # affects characters to its left. Scanning from the right lets you know upfront how many characters to skip before you reach them, avoiding the need to store anything.Q5. Is LeetCode 844 asked in Google interviews? Yes, it is commonly used as a warmup or screening problem. The follow-up O(1) space solution is what makes it interesting for senior-level interviews.Similar LeetCode Problems to Practice Next1047. Remove All Adjacent Duplicates In String — Easy — same stack pattern2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace1209. Remove All Adjacent Duplicates in String II — Medium — k adjacent duplicates678. Valid Parenthesis String — Medium — stack with wildcardsConclusionLeetCode 844 Backspace String Compare is a well-rounded problem that tests string manipulation, stack simulation, and space optimization all in one. The StringBuilder solution is your go-to for interviews. But always be ready to explain the Two Pointer O(1) space follow-up — that is what shows real depth of understanding.Check out these problems alongside 1047, 2390, and 3174 and you will have the entire stack simulation pattern locked down for any coding interview.

StringStackTwo PointerString Builder

LeetCode 121 — Best Time to Buy and Sell Stock I | Two Pointer / Sliding Window Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/Understanding the ProblemYou are given an array prices where prices[i] is the stock price on day i. You can buy on one day and sell on a later day. You want to maximize your profit.Goal: Return the maximum profit possible. If no profit can be made, return 0.Key Rules:You must buy before you sell — no going back in time.You can only make one transaction (one buy, one sell).If prices only go down, profit is impossible — return 0.Constraints:1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁴Understanding the Problem With a Real-World AnalogyImagine you're watching a stock ticker for a week. You want to pick the single best day to buy and a later day to sell. You can't predict the future — you just have historical prices. The question is: looking back at all the prices, what was the best single buy-sell pair you could have chosen?Key Observation (Before Writing a Single Line of Code)The profit on any given pair of days is:profit = prices[sell_day] - prices[buy_day]To maximize profit, for every potential sell day, we want the lowest possible buy price seen so far to the left of it. This is the core insight that drives the efficient solution.If at any point the current price is lower than our tracked minimum, there is no point keeping the old minimum — the new one is strictly better for any future sell day.Intuition — The Two Pointer ApproachWe use two pointers i (buy pointer) and j (sell pointer), both starting at the beginning with i = 0 and j = 1.At every step we ask: is prices[j] greater than prices[i]?If yes → this is a profitable pair. Compute the profit and update the maximum if it's better.If no → prices[j] is cheaper than prices[i]. There's no reason to keep i where it is — any future sell day would be better served by buying at j instead. So we move i to j.Either way, j always moves forward by 1 until it reaches the end of the array.Why Moving i to j is CorrectThis is the most important conceptual point. When prices[j] < prices[i], you might wonder — why not just skip j and move on? Why move i?Because for any future day k > j, the profit buying at j is:prices[k] - prices[j]And the profit buying at i is:prices[k] - prices[i]Since prices[j] < prices[i], buying at j will always give a higher or equal profit for the same sell day k. So we update i = j — there is no scenario where keeping the old i is better.Dry Run — Example 1 (Step by Step)Input: prices = [7, 1, 5, 3, 6, 4]We start with i = 0, j = 1, maxP = 0.Step 1: i = 0, j = 1 → prices[i] = 7, prices[j] = 17 > 1 → prices[j] is cheaper. Move i to j. i = 1, j moves to 2. maxP = 0.Step 2: i = 1, j = 2 → prices[i] = 1, prices[j] = 51 < 5 → Profitable! profit = 5 - 1 = 4. 4 > 0 → update maxP = 4. j moves to 3.Step 3: i = 1, j = 3 → prices[i] = 1, prices[j] = 31 < 3 → Profitable! profit = 3 - 1 = 2. 2 < 4 → maxP stays 4. j moves to 4.Step 4: i = 1, j = 4 → prices[i] = 1, prices[j] = 61 < 6 → Profitable! profit = 6 - 1 = 5. 5 > 4 → update maxP = 5. j moves to 5.Step 5: i = 1, j = 5 → prices[i] = 1, prices[j] = 41 < 4 → Profitable! profit = 4 - 1 = 3. 3 < 5 → maxP stays 5. j moves to 6. j = 6 = prices.length → loop ends.Output: maxP = 5 ✅ (Buy at day 2 price=1, sell at day 5 price=6)Dry Run — Example 2 (Step by Step)Input: prices = [7, 6, 4, 3, 1]We start with i = 0, j = 1, maxP = 0.Step 1: i = 0, j = 1 → prices[i] = 7, prices[j] = 67 > 6 → Move i to j. i = 1, j moves to 2. maxP = 0.Step 2: i = 1, j = 2 → prices[i] = 6, prices[j] = 46 > 4 → Move i to j. i = 2, j moves to 3. maxP = 0.Step 3: i = 2, j = 3 → prices[i] = 4, prices[j] = 34 > 3 → Move i to j. i = 3, j moves to 4. maxP = 0.Step 4: i = 3, j = 4 → prices[i] = 3, prices[j] = 13 > 1 → Move i to j. i = 4, j moves to 5. j = 5 = prices.length → loop ends.Output: maxP = 0 ✅ (Prices only went down, no profitable transaction exists)The Code — Implementationclass Solution {public int maxProfit(int[] prices) {int i = 0; // Buy pointer — points to the current minimum price dayint j = 1; // Sell pointer — scans forward through the arrayint maxP = 0; // Tracks the maximum profit seen so far// j scans from day 1 to the end of the arraywhile (i < j && j < prices.length) {if (prices[i] > prices[j]) {// prices[j] is cheaper than current buy price// Move buy pointer to j — buying here is strictly better// for any future sell dayi = j;} else {// prices[j] > prices[i] — this is a profitable pair// Calculate profit and update maxP if it's the best so farint profit = prices[j] - prices[i];if (profit > maxP) {maxP = profit;}}// Always move the sell pointer forwardj++;}// If no profitable transaction was found, maxP remains 0return maxP;}}Code Walkthrough — Step by StepInitialization: i = 0 acts as our buy day pointer (always pointing to the lowest price seen so far). j = 1 is our sell day pointer scanning forward. maxP = 0 is our answer — defaulting to 0 handles the case where no profit is possible.The loop condition: i < j ensures we never sell before buying. j < prices.length ensures we don't go out of bounds.When prices[i] > prices[j]: The current sell day price is cheaper than our buy day. We update i = j, because buying at j dominates buying at i for all future sell days.When prices[j] >= prices[i]: We have a potential profit. We compute it and update maxP if it beats the current best.j always increments: Regardless of which branch we take, j++ moves the sell pointer forward every iteration — this is what drives the loop to completion.Common Mistakes to AvoidNot returning 0 for no-profit cases: If prices are strictly decreasing, maxP never gets updated and stays 0. The initialization maxP = 0 handles this correctly — never initialize it to a negative number.Using a nested loop (brute force): A common first instinct is two nested loops checking every pair. That is O(N²) and will TLE on large inputs. The two pointer approach solves it in O(N).Thinking you need to sort: Sorting destroys the order of days, which is fundamental to the problem. Never sort the prices array here.Moving i forward by 1 instead of to j: When prices[j] < prices[i], some people write i++ instead of i = j. This is wrong — you might miss the new minimum entirely and waste iterations.Complexity AnalysisTime Complexity: O(N) The j pointer traverses the array exactly once from index 1 to the end. The i pointer only moves forward and never exceeds j. So the entire algorithm is a single linear pass — O(N).Space Complexity: O(1) No extra arrays, maps, or stacks are used. Only three integer variables — i, j, and maxP.Alternative Way to Think About It (Min Tracking)Some people write this problem using a minPrice variable instead of two pointers. Both approaches are equivalent — the two pointer framing is slightly more intuitive visually, but here is the min-tracking version for reference:int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int price : prices) {if (price < minPrice) {minPrice = price;} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;}}return maxProfit;The logic is the same — always track the cheapest buy day seen so far, and for each day compute what profit would look like if you sold today.Similar Problems (Build on This Foundation)LeetCode 122 — Best Time to Buy and Sell Stock II (multiple transactions allowed) [ Blog is also avaliable on this - Read Now ]LeetCode 123 — Best Time to Buy and Sell Stock III (at most 2 transactions) [ Blog is also avaliable on this - Read Now ]LeetCode 188 — Best Time to Buy and Sell Stock IV (at most k transactions)LeetCode 309 — Best Time to Buy and Sell Stock with CooldownLeetCode 714 — Best Time to Buy and Sell Stock with Transaction FeeLeetCode 121 is the foundation. Master this one deeply before moving to the others — they all build on the same core idea.Key Takeaways✅ For every potential sell day, the best buy day is always the minimum price seen to its left — this drives the whole approach.✅ When the sell pointer finds a cheaper price than the buy pointer, always move the buy pointer there — it strictly dominates the old buy day for all future sells.✅ Initialize maxP = 0 so that no-profit scenarios (prices only going down) are handled automatically.✅ The two pointer approach solves this in a single linear pass — O(N) time and O(1) space.✅ j always increments every iteration — i only moves when a cheaper price is found.Happy Coding! If this clicked for you, the entire Stock series on LeetCode will feel much more approachable.

LeetCodeTwo PointersEasyJavaDSA

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

🔗 Problem LinkLeetCode 917 – Reverse Only Letters 👉 https://leetcode.com/problems/reverse-only-letters/IntroductionThis is a very clean two-pointer problem.The challenge is not just reversing a string — it’s reversing only the letters while keeping all non-letter characters in their original positions.This problem strengthens:Two pointer techniqueCharacter validation logicIn-place string manipulationLet’s break it down.📌 Problem UnderstandingYou are given a string s.Rules:All non-English letters must remain at the same index.Only English letters (uppercase or lowercase) should be reversed.Return the modified string.Example 1Input: "ab-cd"Output: "dc-ba"Only letters are reversed. Hyphen stays at same position.Example 2Input: "a-bC-dEf-ghIj"Output: "j-Ih-gfE-dCba"Example 3Input: "Test1ng-Leet=code-Q!"Output: "Qedo1ct-eeLg=ntse-T!"Notice:Numbers, -, =, ! stay fixed.Only letters move.🧠 IntuitionThe first thought might be:Extract all lettersReverse themPut them backBut that would require extra space.Instead, we can solve this efficiently using Two Pointers.🚀 Two Pointer ApproachWe use:i → starting from leftj → starting from rightSteps:Convert string into char array.Move i forward until it points to a letter.Move j backward until it points to a letter.Swap letters.Continue until i < j.💻 Your Codeclass Solution { public String reverseOnlyLetters(String s) { int i = 0; int j = s.length() - 1; char arr[] = s.toCharArray(); while(i < j){ boolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z'); boolean r = ('A' <= s.charAt(j) && s.charAt(j) <= 'Z') || ('a' <= s.charAt(j) && s.charAt(j) <= 'z'); if(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; }else if(l){ j--; }else if(r){ i++; }else{ i++; j--; } } return new String(arr); }}🔍 Step-by-Step Explanation1️⃣ Convert to Character Arraychar arr[] = s.toCharArray();Strings are immutable in Java. So we convert to char array to modify it.2️⃣ Initialize Two Pointersint i = 0;int j = s.length() - 1;We start from both ends.3️⃣ Check If Characters Are Lettersboolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z');You manually check ASCII ranges for uppercase and lowercase letters.Same logic for r.4️⃣ Swap When Both Are Lettersif(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--;}Only swap letters.5️⃣ Move Pointers When One Is Not LetterIf left is letter but right is not → move jIf right is letter but left is not → move iIf both are not letters → move bothThis ensures:Non-letter characters remain in their positions.🎯 Why This WorksWe never move non-letter characters.We only swap valid letters.Since we use two pointers:Time complexity stays linear.No extra array needed for letters.⏱ Complexity AnalysisTime Complexity: O(n)Each character is visited at most once.Space Complexity: O(n)Because we convert string to char array.(If considering output string creation, still O(n))🔥 Cleaner OptimizationInstead of manually checking ASCII ranges, Java provides:Character.isLetter(c)Cleaner version:class Solution { public String reverseOnlyLetters(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!Character.isLetter(arr[i])){ i++; }else if(!Character.isLetter(arr[j])){ j--; }else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); }}Much cleaner and readable.🏁 Final ThoughtsThis problem teaches:Two pointer patternIn-place string reversalCharacter validation logicClean pointer movement strategyIt’s a simple but powerful pattern that appears often in interviews.If you master this, you can easily solve:Reverse Vowels of a StringValid PalindromeReverse String IIPalindrome with One Removal

Two PointersString ManipulationLeetCodeEasy

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

🔗 Problem LinkLeetCode 345 – Reverse Vowels of a String 👉 https://leetcode.com/problems/reverse-vowels-of-a-string/IntroductionThis problem is very similar to Reverse Only Letters, but with a small twist:Instead of reversing all letters, we only reverse the vowels.At first, we might think of extracting vowels, reversing them, and putting them back. That works — but it is not the most optimal approach.In this article, we’ll:Understand the brute-force style approach (your solution)Analyze its time complexityOptimize it using the Two Pointer patternCompare both approaches📌 Problem UnderstandingYou are given a string s.You must:Reverse only the vowelsKeep all other characters in the same positionVowels include:a, e, i, o, uA, E, I, O, UExample 1Input: "IceCreAm"Output: "AceCreIm"Vowels: ['I','e','e','A'] Reversed: ['A','e','e','I']Example 2Input: "leetcode"Output: "leotcede"🧠 Your First Approach – Extract, Reverse, ReplaceYour idea:Extract all vowels into a string.Store their indices.Reverse the vowel string.Replace vowels at stored indices.Let’s look at your code.💻 Your Code (Extract & Replace Method)class Solution { public String reverseVowels(String s) { String vow = ""; List<Integer> lis = new ArrayList<>(); HashMap<Integer,Character> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ if(((s.charAt(i) == 'a') || (s.charAt(i) == 'e') || (s.charAt(i) == 'i') || (s.charAt(i) == 'o') || (s.charAt(i) == 'u') || (s.charAt(i) == 'A') || (s.charAt(i) == 'E') || (s.charAt(i) == 'I') || (s.charAt(i) == 'O') || (s.charAt(i) == 'U')) ){ vow += s.charAt(i); lis.add(i); } } String so = ""; for(int i = vow.length()-1; i >= 0; i--){ so += vow.charAt(i); } for(int i =0; i< lis.size();i++){ mp.put(lis.get(i), so.charAt(i)); } String ans = ""; for(int i =0 ; i< s.length();i++){ if(mp.containsKey(i)){ ans += mp.get(i); }else{ ans += s.charAt(i); } } return ans; }}🔍 How This WorksStep 1 – Extract VowelsStore:Vowel characters in vowTheir indices in lisStep 2 – Reverse the Vowel StringCreate new reversed string so.Step 3 – Map Indices to Reversed VowelsUse a HashMap to store:index → reversed vowelStep 4 – Build Final StringTraverse original string:If index in map → use reversed vowelElse → use original character⚠️ Problem with This ApproachAlthough correct, it has inefficiencies:String concatenation (+=) → O(n²) in worst caseExtra space used:Vowel stringList of indicesHashMapFinal answer stringTime Complexity: O(n²) (due to string concatenation) Space Complexity: O(n)We can do better.🚀 Optimized Approach – Two Pointers (Best Solution)Instead of extracting vowels separately, we can:Convert string into char arrayUse two pointersSwap vowels directlyThis avoids extra structures.💻 Optimized Two Pointer Solutionclass Solution { public String reverseVowels(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!isVowel(arr[i])){ i++; } else if(!isVowel(arr[j])){ j--; } else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); } private boolean isVowel(char c){ return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'|| c=='A'||c=='E'||c=='I'||c=='O'||c=='U'; }}🎯 Why This WorksWe:Move left pointer until vowel foundMove right pointer until vowel foundSwapContinueNo extra storage needed.⏱ Complexity ComparisonYour ApproachTime: O(n²) (string concatenation)Space: O(n)Two Pointer ApproachTime: O(n)Space: O(n) (char array)Much cleaner and faster.🔥 Key LearningThis problem reinforces:Two pointer patternIn-place modificationAvoiding unnecessary extra spaceRecognizing optimization opportunitiesWhenever you see:"Reverse something but keep other elements fixed"Think:👉 Two Pointers🏁 Final ThoughtsYour approach shows strong logical thinking:Extract → Reverse → ReplaceThat’s a valid way to solve it.But the optimized two-pointer approach is more interview-friendly.If you master this pattern, you can easily solve:Reverse Only LettersReverse StringValid PalindromeRemove Duplicates from Sorted Array

Two PointersString ManipulationHashMapLeetCodeEasy

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

🚀 Try the ProblemPractice here:https://leetcode.com/problems/remove-nth-node-from-end-of-list/🤔 Let’s Think Differently…Imagine this list:1 → 2 → 3 → 4 → 5You are asked:👉 Remove the 2nd node from the endSo counting from end:5 (1st), 4 (2nd) ❌ remove thisFinal list:1 → 2 → 3 → 5🧠 Problem in Simple WordsYou are given:Head of a linked listA number n👉 Remove the nth node from the end👉 Return the updated list📦 Constraints1 <= number of nodes <= 300 <= Node.val <= 1001 <= n <= size of list🧩 First Thought (Counting Method)💡 IdeaCount total nodesFind position from start:position = total - nTraverse again and remove that node✅ Code (Counting Approach)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return head; // Step 1: Count nodes int co = 0; ListNode tempHead = head; while(tempHead != null){ co++; tempHead = tempHead.next; } // Step 2: If removing head if(co == n) return head.next; // Step 3: Find node before target int k = co - n; int con = 1; ListNode temp = head; while(con < k){ temp = temp.next; con++; } // Step 4: Remove node temp.next = temp.next.next; return head; }}⏱️ ComplexityTime ComplexityO(n) + O(n) = O(n)(two traversals)Space ComplexityO(1)⚠️ Limitation of This Approach👉 It requires two passesBut the problem asks:Can you solve it in one pass?🚀 Optimal Approach: Two Pointer Technique (One Pass)Now comes the interesting part 🔥🧠 Core IdeaWe use two pointers:fast pointerslow pointer🎯 Trick👉 Move fast pointer n steps aheadThen move both pointers together until:fast reaches endAt that moment:👉 slow will be at the node before the one to remove📌 Why This WorksBecause the gap between fast and slow is always n nodesSo when fast reaches end:👉 slow is exactly where we need it🔥 Step-by-Step VisualizationList:1 → 2 → 3 → 4 → 5n = 2Step 1: Move fast 2 stepsfast → 3slow → 1Step 2: Move both togetherfast → 4, slow → 2fast → 5, slow → 3fast → null, slow → 4👉 Now slow is at node before target🧼 Clean and Safe Approach (Using Dummy Node)Using dummy node avoids edge cases like removing head.💻 Code (Optimal One Pass Solution)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // Dummy node to handle edge cases ListNode dummy = new ListNode(0, head); ListNode fast = dummy; ListNode slow = dummy; // Move fast pointer n steps ahead for(int i = 0; i < n; i++){ fast = fast.next; } // Move both pointers while(fast.next != null){ fast = fast.next; slow = slow.next; } // Remove nth node slow.next = slow.next.next; return dummy.next; }}⏱️ ComplexityTime ComplexityO(n)(single pass)Space ComplexityO(1)⚖️ Comparing ApproachesApproachPassesTimeSpaceDifficultyCounting2O(n)O(1)EasyTwo Pointer1O(n)O(1)Optimal❌ Common MistakesForgetting to handle removing head nodeNot using dummy nodeOff-by-one errors in pointer movementMoving fast incorrectly🔥 Interview InsightThis problem is a classic example of:Fast & Slow Pointer TechniqueUsed in many problems like:Cycle DetectionMiddle of Linked ListPalindrome Linked List🧠 Final ThoughtAt first, counting feels natural…But once you learn this trick:"Create a gap and move together"👉 You unlock a powerful pattern.🚀 ConclusionThe Remove Nth Node From End problem is not just about deletion…It teaches:Efficient traversalPointer coordinationOne-pass optimization👉 Tip: Whenever you see “from end”, think:"Can I use two pointers with a gap?"That’s your shortcut to solving these problems like a pro 🚀

Linked ListTwo PointersFast & Slow PointerOne Pass AlgorithmLeetCodeMedium

LeetCode 122 — Best Time to Buy and Sell Stock II | Every Approach Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/Understanding the ProblemYou are given an array prices where prices[i] is the stock price on day i. Unlike the classic version, here you can make as many transactions as you want — but you can only hold one share at a time. You may buy and sell on the same day.Goal: Return the maximum total profit achievable.Key Rules:You can buy and sell multiple times.You cannot hold more than one share at a time — you must sell before buying again.If no profit is possible, return 0.Constraints:1 ≤ prices.length ≤ 3 × 10⁴0 ≤ prices[i] ≤ 10⁴How This Differs From LeetCode 121 #In LeetCode 121, you were limited to exactly one buy-sell transaction. Here, the restriction is lifted — you can participate in as many transactions as you want. This fundamentally changes the strategy. Instead of hunting for the single best pair, you want to capture every profitable price movement in the array.The Core InsightLook at the price chart mentally. Every time the price goes up from one day to the next, that's money on the table. The question is — how do you collect all of it?The answer is surprisingly simple: add every single upward price difference to your profit. If prices go up three days in a row from 1 → 3 → 5 → 8, you collect (3-1) + (5-3) + (8-5) = 7, which is exactly the same as buying at 1 and selling at 8. You never miss a gain.This is the foundation of all approaches below.Approach 1 — Simple Greedy (Collect Every Upward Move)Intuition: Every time prices[i] > prices[i-1], add the difference to profit. You are essentially buying at every valley and selling at every peak, collecting each individual daily gain without explicitly tracking buy/sell days.Why it works: The total gain from buying at day 0 and selling at day N is mathematically equal to the sum of all positive daily differences in between. You never lose anything by collecting gains day by day.Example: prices = [1, 2, 3, 4, 5] Daily gains: (2-1) + (3-2) + (4-3) + (5-4) = 1+1+1+1 = 4 Same as buying at 1 and selling at 5 directly.class Solution {public int maxProfit(int[] prices) {int maxProfit = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}return maxProfit;}}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — no extra space used.This is the cleanest and most recommended solution for this problem.Approach 2 — Peak Valley ApproachIntuition: Instead of collecting every daily gain, explicitly find every valley (local minimum) to buy at and every peak (local maximum) to sell at. You buy when price stops falling and sell when price stops rising.How it works: Scan through the array. When you find a valley (prices[i] ≤ prices[i+1]), that is your buy point. Then keep going until you find a peak (prices[i] ≥ prices[i+1]) — that is your sell point. Add the peak minus valley to profit. Repeat.Example: prices = [7, 1, 5, 3, 6, 4]Valley at index 1 (price = 1), Peak at index 2 (price = 5) → profit += 4 Valley at index 3 (price = 3), Peak at index 4 (price = 6) → profit += 3 Total = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int maxProfit = 0;int valley, peak;while (i < prices.length - 1) {while (i < prices.length - 1 && prices[i] >= prices[i + 1]) {i++;}valley = prices[i];while (i < prices.length - 1 && prices[i] <= prices[i + 1]) {i++;}peak = prices[i];maxProfit += peak - valley;}return maxProfit;}}Time Complexity: O(N) — each element is visited at most twice. Space Complexity: O(1) — no extra space used.This approach is more explicit and easier to visualize on a graph, though the code is slightly more involved than Approach 1.Approach 3 — Two PointerIntuition: Use two pointers i (buy day) and j (sell day). Move j forward one step at a time. Whenever prices[j] > prices[i], you have a profitable window — add the profit and immediately move i to j (simulate selling and rebuying at the same price on the same day). Whenever prices[j] < prices[i], just move i to j since a cheaper buy day has been found.Why moving i to j after every profitable sale works: Selling at j and immediately rebuying at j costs nothing (profit of 0 for that rebuy). But it positions i at the latest price so you can catch the next upward movement. This correctly simulates collecting every upward segment.Example: prices = [7, 1, 5, 3, 6, 4]i=0, j=1 → 7 > 1, move i to 1. j=2. i=1, j=2 → 1 < 5, profit += 4, move i to 2. j=3. i=2, j=3 → 5 > 3, move i to 3. j=4. i=3, j=4 → 3 < 6, profit += 3, move i to 4. j=5. i=4, j=5 → 6 > 4, move i to 5. j=6. Loop ends. Total profit = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int j = 1;int maxProfit = 0;while (i < j && j < prices.length) {if (prices[i] > prices[j]) {i = j;} else {maxProfit += prices[j] - prices[i];i = j;}j++;}return maxProfit;}}Time Complexity: O(N) — j traverses the array exactly once. Space Complexity: O(1) — only three integer variables.This approach is functionally identical to Approach 1 — both collect every upward daily movement. The two pointer framing makes the buy/sell simulation more explicit.Approach 4 — Dynamic ProgrammingIntuition: At any point in time, you are in one of two states — either you hold a stock or you do not hold a stock. Define two DP values updated each day:hold = maximum profit if you are currently holding a stock at the end of this day.cash = maximum profit if you are not holding any stock at the end of this day.Transitions:To hold on day i: either you already held yesterday, or you buy today. hold = max(hold, cash - prices[i])To have cash on day i: either you already had cash yesterday, or you sell today. cash = max(cash, hold + prices[i])Initialization:hold = -prices[0] (you bought on day 0)cash = 0 (you did nothing on day 0)class Solution {public int maxProfit(int[] prices) {int hold = -prices[0];int cash = 0;for (int i = 1; i < prices.length; i++) {hold = Math.max(hold, cash - prices[i]);cash = Math.max(cash, hold + prices[i]);}return cash;}}Time Complexity: O(N) — single pass. Space Complexity: O(1) — only two variables maintained at each step.This approach is the most powerful because it extends naturally to harder variants of this problem — like LeetCode 309 (with cooldown) and LeetCode 714 (with transaction fee) — where greedy no longer works and you need explicit state tracking.Dry Run — All Approaches on Example 1Input: prices = [7, 1, 5, 3, 6, 4], Expected Output: 7Approach 1 (Simple Greedy): Day 1→2: 1 - 7 = -6, skip. Day 2→3: 5 - 1 = 4, add. profit = 4. Day 3→4: 3 - 5 = -2, skip. Day 4→5: 6 - 3 = 3, add. profit = 7. Day 5→6: 4 - 6 = -2, skip. Result = 7 ✅Approach 4 (DP): Start: hold = -7, cash = 0. Day 1 (price=1): hold = max(-7, 0-1) = -1. cash = max(0, -1+1) = 0. Day 2 (price=5): hold = max(-1, 0-5) = -1. cash = max(0, -1+5) = 4. Day 3 (price=3): hold = max(-1, 4-3) = 1. cash = max(4, 1+3) = 4. Day 4 (price=6): hold = max(1, 4-6) = 1. cash = max(4, 1+6) = 7. Day 5 (price=4): hold = max(1, 7-4) = 3. cash = max(7, 3+4) = 7. Result = 7 ✅Comparison of All ApproachesApproach 1 — Simple Greedy Code simplicity: Simplest possible. Best for interviews — clean and readable. Does not extend to constrained variants.Approach 2 — Peak Valley Code simplicity: Moderate. Best for visual/conceptual understanding. Slightly verbose but maps directly to a chart.Approach 3 — Two Pointer Code simplicity: Simple. Explicit simulation of buy/sell actions. Functionally identical to Approach 1.Approach 4 — Dynamic Programming Code simplicity: Moderate. Most powerful — extends to cooldown, fee, and k-transaction variants. Worth mastering for the full stock problem series.Common Mistakes to AvoidThinking you need to find exact buy/sell days: The problem only asks for maximum profit — you do not need to output which days you traded. This frees you to use the simple greedy sum approach.Trying to find the global minimum and maximum: Unlike LeetCode 121, the single best buy-sell pair is not always optimal here. You need to capture multiple smaller movements, not one big one.Holding more than one share: You cannot buy twice in a row without selling in between. In Approach 3, moving i = j after every transaction ensures you always sell before the next buy.Not handling a flat or decreasing array: If prices never go up, all approaches correctly return 0 — the greedy sum adds nothing, peak-valley finds no valid pairs, and DP's cash stays at 0.Complexity SummaryAll four approaches run in O(N) time and O(1) space. The difference between them is conceptual clarity and extensibility, not raw performance.The Full Stock Problem Series on LeetCodeThis problem is part of a six-problem series. Understanding them in order builds intuition progressively:LeetCode 121 — One transaction only. Two pointer / min tracking greedy. [ Blog is also avaliable on this - Read Now]LeetCode 123 — At most 2 transactions. DP with explicit state for two transactions. [ Blog is also avaliable on this - Read Now]LeetCode 188 — At most k transactions. Generalized DP.LeetCode 309 — Unlimited transactions with cooldown after selling. DP with three states.LeetCode 714 — Unlimited transactions with a fee per transaction. DP with adjusted transitions.Each problem adds one constraint on top of the previous. If you understand the DP state machine from Approach 4 deeply, every problem in this series becomes a small modification of the same framework.Key Takeaways✅ When transactions are unlimited, collect every upward daily price movement — that is the global optimum.✅ The sum of all positive daily differences equals the sum of all peak-valley differences. Both are provably optimal.✅ The two pointer approach explicitly simulates buy and sell events — moving i = j after a sale means selling and immediately rebuying at the same price to stay positioned for the next gain.✅ The DP approach with hold and cash states is the most versatile — it is the foundation for every harder variant in the stock series.✅ Always initialize maxProfit = 0 so that the no-profit case (prices only falling) is handled correctly without extra conditions.Happy Coding! Once you have this problem locked down, the rest of the stock series will feel like natural extensions rather than new problems entirely. 🚀

LeetCodeGreedyTwo PointersDynamic ProgrammingMediumJavaArrays

LeetCode 143 Reorder List - Java Solution Explained

IntroductionLeetCode 143 Reorder List is one of those problems that looks simple when you read it but immediately makes you wonder — where do I even start? There is no single trick that solves it. Instead it combines three separate linked list techniques into one clean solution. Mastering this problem means you have genuinely understood linked lists at an intermediate level.You can find the problem here — LeetCode 143 Reorder List.This article walks through everything — what the problem wants, the intuition behind each step, all three techniques used, a detailed dry run, complexity analysis, and common mistakes beginners make.What Is the Problem Really Asking?You have a linked list: L0 → L1 → L2 → ... → LnYou need to reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...In plain English — take one node from the front, then one from the back, then one from the front, then one from the back, and keep alternating until all nodes are used.Example:Input: 1 → 2 → 3 → 4 → 5Output: 1 → 5 → 2 → 4 → 3Node 1 from front, Node 5 from back, Node 2 from front, Node 4 from back, Node 3 stays in middle.Real Life Analogy — Dealing Cards From Both EndsImagine you have a deck of cards laid out in a line face up: 1, 2, 3, 4, 5. Now you deal them by alternately picking from the left end and the right end of the line:Pick 1 from left → placePick 5 from right → place after 1Pick 2 from left → place after 5Pick 4 from right → place after 2Pick 3 (only one left) → place after 4Result: 1, 5, 2, 4, 3That is exactly what the problem wants. The challenge is doing this efficiently on a singly linked list where you cannot just index from the back.Why This Problem Is Hard for BeginnersIn an array you can just use two pointers — one at the start and one at the end — and swap/interleave easily. But a singly linked list only goes forward. You cannot go backwards. You cannot easily access the last element.This is why the problem requires a three-step approach that cleverly works around the limitations of a singly linked list.The Three Step ApproachEvery experienced developer solves this problem in exactly three steps:Step 1 — Find the middle of the linked list using the Fast & Slow Pointer techniqueStep 2 — Reverse the second half of the linked listStep 3 — Merge the two halves by alternating nodes from eachLet us understand each step deeply before looking at code.Step 1: Finding the Middle — Fast & Slow PointerThe Fast & Slow Pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds through the list:slow moves one step at a timefast moves two steps at a timeWhen fast reaches the end, slow is exactly at the middle. This works because fast covers twice the distance of slow in the same number of steps.ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next;}// slow is now at the middleFor 1 → 2 → 3 → 4 → 5:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: slow=3, fast=5 (fast.next is null, stop)Middle is node 3For 1 → 2 → 3 → 4:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: fast.next.next is null, stopslow=2, middle is node 2After finding the middle, we cut the list in two by setting slow.next = null. This disconnects the first half from the second half.Step 2: Reversing the Second HalfOnce we have the second half starting from slow.next, we reverse it. After reversal, what was the last node becomes the first — giving us easy access to the back elements of the original list.public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; // save next curr.next = prev; // reverse the link prev = curr; // move prev forward curr = next; // move curr forward } return prev; // prev is the new head}For second half 3 → 4 → 5 (from the first example):Reverse → 5 → 4 → 3Now we have:First half: 1 → 2 → 3 (but 3 is the end since we cut at slow)Wait — actually after cutting at slow=3: first half is 1 → 2 → 3, second half reversed is 5 → 4Let us be precise. For 1 → 2 → 3 → 4 → 5, slow stops at 3. slow.next = null cuts to give:First half: 1 → 2 → 3 → nullSecond half before reverse: 4 → 5Second half after reverse: 5 → 4Step 3: Merging Two HalvesNow we have two lists and we merge them by alternately taking one node from each:Take from first half, take from second half, take from first half, take from second half...ListNode orig = head; // pointer for first halfListNode newhead = second; // pointer for reversed second halfwhile (newhead != null) { ListNode temp1 = orig.next; // save next of first half ListNode temp2 = newhead.next; // save next of second half orig.next = newhead; // first → second newhead.next = temp1; // second → next of first orig = temp1; // advance first half pointer newhead = temp2; // advance second half pointer}Why do we loop on newhead != null and not orig != null? Because the second half is always equal to or shorter than the first half (we cut at middle). Once the second half is exhausted, the remaining first half nodes are already in the correct position.Complete Solutionclass Solution { public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } public void reorderList(ListNode head) { // Step 1: Find middle using fast & slow pointer ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } // Step 2: Reverse second half ListNode newhead = reverse(slow.next); slow.next = null; // cut the list into two halves // Step 3: Merge two halves alternately ListNode orig = head; while (newhead != null) { ListNode temp1 = orig.next; ListNode temp2 = newhead.next; orig.next = newhead; newhead.next = temp1; orig = temp1; newhead = temp2; } }}Complete Dry Run — head = [1, 2, 3, 4, 5]Step 1: Find MiddleList: 1 → 2 → 3 → 4 → 5Initial: slow=1, fast=1Iteration 1: slow=2, fast=3Iteration 2: fast.next=4, fast.next.next=5 → slow=3, fast=5fast.next is null → stopslow is at node 3Step 2: Cut and ReverseCut: slow.next = nullFirst half: 1 → 2 → 3 → nullSecond half: 4 → 5Reverse second half 4 → 5:prev=null, curr=4 → next=5, 4.next=null, prev=4, curr=5prev=4, curr=5 → next=null, 5.next=4, prev=5, curr=nullReturn prev=5Reversed second half: 5 → 4 → nullStep 3: Mergeorig=1, newhead=5Iteration 1:temp1 = orig.next = 2temp2 = newhead.next = 4orig.next = newhead → 1.next = 5newhead.next = temp1 → 5.next = 2orig = temp1 = 2newhead = temp2 = 4List so far: 1 → 5 → 2 → 3Iteration 2:temp1 = orig.next = 3temp2 = newhead.next = nullorig.next = newhead → 2.next = 4newhead.next = temp1 → 4.next = 3orig = temp1 = 3newhead = temp2 = nullList so far: 1 → 5 → 2 → 4 → 3newhead is null → loop endsFinal result: 1 → 5 → 2 → 4 → 3 ✅Dry Run — head = [1, 2, 3, 4]Step 1: Find MiddleInitial: slow=1, fast=1Iteration 1: slow=2, fast=3fast.next=4, fast.next.next=null → stopslow is at node 2Step 2: Cut and ReverseFirst half: 1 → 2 → nullSecond half: 3 → 4Reversed: 4 → 3 → nullStep 3: Mergeorig=1, newhead=4Iteration 1:temp1=2, temp2=31.next=4, 4.next=2orig=2, newhead=3List: 1 → 4 → 2 → 3Iteration 2:temp1=null (2.next was originally 3 but we cut at slow=2, so 2.next = null... wait)Actually after cutting at slow=2, first half is 1 → 2 → null, so orig when it becomes 2, orig.next = null.temp1 = orig.next = nulltemp2 = newhead.next = null2.next = 3, 3.next = nullorig = null, newhead = nullnewhead is null → stopFinal result: 1 → 4 → 2 → 3 ✅Why slow.next = null Must Come After Saving newheadThis is a subtle but critical ordering detail in the code. Look at this sequence:ListNode newhead = reverse(slow.next); // save reversed second half FIRSTslow.next = null; // THEN cut the listIf you cut first (slow.next = null) and then try to reverse, you lose the reference to the second half entirely because slow.next is already null. Always save the second half reference before cutting.Time and Space ComplexityTime Complexity: O(n) — each of the three steps (find middle, reverse, merge) makes a single pass through the list. Total is 3 passes = O(3n) = O(n).Space Complexity: O(1) — everything is done by rearranging pointers in place. No extra arrays, no recursion stack, no additional data structures. Just a handful of pointer variables.This is the optimal solution — linear time and constant space.Alternative Approach — Using ArrayList (Simpler but O(n) Space)If you find the three-step approach hard to implement under interview pressure, here is a simpler approach using extra space:public void reorderList(ListNode head) { // store all nodes in ArrayList for random access List<ListNode> nodes = new ArrayList<>(); ListNode curr = head; while (curr != null) { nodes.add(curr); curr = curr.next; } int left = 0; int right = nodes.size() - 1; while (left < right) { nodes.get(left).next = nodes.get(right); left++; if (left == right) break; // odd number of nodes nodes.get(right).next = nodes.get(left); right--; } nodes.get(left).next = null; // terminate the list}This is much easier to understand and code. Store all nodes in an ArrayList, use two pointers from both ends, and wire up the next pointers.Time Complexity: O(n) Space Complexity: O(n) — ArrayList stores all nodesThis is acceptable in most interviews. Mention the O(1) space approach as the optimal solution if asked.Common Mistakes to AvoidNot cutting the list before merging If you do not set slow.next = null after finding the middle, the first half still points into the second half. During merging, this creates cycles and infinite loops. Always cut before merging.Wrong loop condition for finding the middle The condition fast.next != null && fast.next.next != null ensures fast does not go out of bounds when jumping two steps. Using just fast != null && fast.next != null moves slow one step too far for even-length lists.Looping on orig instead of newhead The merge loop should run while newhead != null, not while orig != null. The second half is always shorter or equal to the first half. Once the second half is done, the remaining first half is already correctly placed.Forgetting to save both temp pointers before rewiring In the merge step, you must save both orig.next and newhead.next before changing any pointers. Changing orig.next first and then trying to access orig.next to save it gives you the wrong node.How This Problem Combines Multiple PatternsThis problem is special because it does not rely on a single technique. It is a combination of three fundamental linked list operations:Fast & Slow Pointer — you saw this concept in problems like finding the middle of a list and detecting cycles (LeetCode 141, 142).Reverse a Linked List — the most fundamental linked list operation, appears in LeetCode 206 and as a subtask in dozens of problems.Merge Two Lists — similar to merging two sorted lists (LeetCode 21) but here order is not sorted, it is alternating.Solving this problem proves you are comfortable with all three patterns individually and can combine them when needed.FAQs — People Also AskQ1. What is the most efficient approach for LeetCode 143 Reorder List? The three-step approach — find middle with fast/slow pointer, reverse second half, merge alternately — runs in O(n) time and O(1) space. It is the optimal solution. The ArrayList approach is O(n) time and O(n) space but simpler to code.Q2. Why use fast and slow pointer to find the middle? Because a singly linked list has no way to access elements by index. You cannot just do list[length/2]. The fast and slow pointer technique finds the middle in a single pass without knowing the length beforehand.Q3. Why reverse the second half instead of the first half? The problem wants front-to-back alternation. If you reverse the second half, its first node is the original last node — exactly what you need to interleave with the front of the first half. Reversing the first half would give the wrong order.Q4. What is the time complexity of LeetCode 143? O(n) time for three linear passes (find middle, reverse, merge). O(1) space since all operations are in-place pointer manipulations with no extra data structures.Q5. Is LeetCode 143 asked in coding interviews? Yes, frequently at companies like Amazon, Google, Facebook, and Microsoft. It is considered a benchmark problem for linked list mastery because it requires combining three separate techniques cleanly under pressure.Similar LeetCode Problems to Practice Next206. Reverse Linked List — Easy — foundation for step 2 of this problem876. Middle of the Linked List — Easy — fast & slow pointer isolated21. Merge Two Sorted Lists — Easy — merging technique foundation234. Palindrome Linked List — Easy — also uses find middle + reverse second half148. Sort List — Medium — merge sort on linked list, uses same split techniqueConclusionLeetCode 143 Reorder List is one of the best Medium linked list problems because it forces you to think in multiple steps and combine techniques rather than apply a single pattern. The fast/slow pointer finds the middle efficiently without knowing the length. Reversing the second half turns the "cannot go backwards" limitation of singly linked lists into a non-issue. And the alternating merge weaves everything together cleanly.Work through the dry runs carefully — especially the pointer saving step in the merge. Once you see why each step is necessary and how they connect, this problem will always feel approachable no matter when it shows up in an interview.

LeetCodeJavaLinked ListTwo PointerFast Slow PointerMedium

Intersection of Two Linked Lists – The Smart Trick Most People Miss (LeetCode 160)

🚀 Try the ProblemPractice here:https://leetcode.com/problems/intersection-of-two-linked-lists/🤔 Let’s Start With a ThoughtImagine two roads:Road A: 4 → 1 → 8 → 4 → 5 Road B: 5 → 6 → 1 → 8 → 4 → 5At some point… both roads merge into one.👉 That merging point is the intersection node🧠 Problem in Simple WordsYou are given:Head of List AHead of List B👉 Find the node where both linked lists intersect👉 If no intersection exists → return null⚠️ Important Clarification👉 Intersection means:Same memory node (same reference)NOT:Same value ❌📌 Example InsightList A: 1 → 9 → 1 → 2 → 4 List B: 3 → 2 → 4Even though both lists have 2 and 4:👉 They intersect ONLY if they point to the same node in memory📦 Constraints1 <= m, n <= 3 * 10^41 <= Node.val <= 10^5No cycles in the list🔍 First Thought (Brute Force)IdeaFor every node in List A:👉 Traverse entire List B and check if nodes matchComplexityTime: O(m * n) ❌Space: O(1)Too slow.🧩 Better Approach: Length Difference MethodIdeaFind length of both listsMove the longer list ahead by the differenceNow traverse both togetherWhy This Works👉 After skipping extra nodes, both pointers are equally far from intersectionComplexityTime: O(m + n)Space: O(1)🚀 Optimal Approach: Two Pointer Switching TrickNow comes the most beautiful trick 🔥🧠 Core IdeaWe use two pointers:pointerA → starts from headApointerB → starts from headB🎯 The Magic Trick👉 When a pointer reaches end → switch it to the other list🔄 VisualizationLet’s say:Length A = mLength B = nPointer paths:pointerA travels: A → BpointerB travels: B → ASo both travel:m + n distance💡 Why They Meet👉 If intersection exists → they meet at intersection👉 If not → both reach null at same time🔥 Step-by-Step ExampleA: 4 → 1 → 8 → 4 → 5 B: 5 → 6 → 1 → 8 → 4 → 5Iteration:A pointer: 4 → 1 → 8 → 4 → 5 → null → 5 → 6 → 1 → 8 B pointer: 5 → 6 → 1 → 8 → 4 → 5 → null → 4 → 1 → 8👉 They meet at 8💻 Clean Java Code (Optimal Solution)public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode tempa = headA; ListNode tempb = headB; // Traverse until both pointers meet while(tempa != tempb){ // Move pointer A if(tempa != null) tempa = tempa.next; else tempa = headB; // Move pointer B if(tempb != null) tempb = tempb.next; else tempb = headA; } // Either intersection node OR null return tempa; }}⏱️ ComplexityTime ComplexityO(m + n)Space ComplexityO(1)⚖️ Approach ComparisonApproachTimeSpaceNotesBrute ForceO(m*n)O(1)Too slowLength DifferenceO(m+n)O(1)GoodTwo Pointer SwitchO(m+n)O(1)Best & elegant❌ Common MistakesComparing values instead of nodes ❌Forgetting to switch listsNot handling null correctlyAssuming intersection always exists🔥 Interview InsightThis is one of the most clever pointer problems.It teaches:👉 How to equalize paths without extra memory👉 How pointer switching solves alignment problems🧠 Final ThoughtAt first, this trick feels like magic…But actually it’s just:Equalizing path lengths🚀 ConclusionThe Intersection of Two Linked Lists problem is a perfect example of:Smart thinking > brute forceClean logic > complex code👉 Tip: Whenever two lists need alignment, think:"Can I make both pointers travel equal distance?"That’s where the magic begins ✨

Linked ListTwo PointersIntersectionPointer SwitchingDSALeetCodeEasy

LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach

🔗 Try This Problemhttps://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/🎥 Video ExplanationProblem ExplanationYou are given the head of a singly linked list. The task is to remove the middle node and return the updated list.The middle node is defined using 0-based indexing:Middle Index = ⌊n / 2⌋Where n is the total number of nodes.ExampleInput: [1, 3, 4, 7, 1, 2, 6]Index: 0 1 2 3 4 5 6n = 7Middle index = 3Node to remove = 7Output: [1, 3, 4, 1, 2, 6]Approach 1: Brute Force (Two Traversals)IdeaTraverse the list to count total nodesCompute middle indexTraverse again to delete that nodeComplexityTime Complexity: O(n)Space Complexity: O(1)LimitationThis approach requires two passes, which is not optimal when a single traversal solution exists.Approach 2: Fast and Slow Pointer (Optimal)IntuitionUse two pointers:Slow pointer moves one step at a timeFast pointer moves two steps at a timeWhen the fast pointer reaches the end of the list:Slow pointer will be at the middle nodeImportant DetailTo remove the middle node, access to the previous node is required.Therefore, maintain an additional pointer:prev → tracks node before slowAlgorithm StepsInitialize:slow = headfast = headprev = nullTraverse:Move fast by 2 stepsMove slow by 1 stepUpdate prev = slow (before moving slow)When loop ends:slow points to middle nodeprev points to node before middleDelete node:prev.next = slow.nextDetailed Dry RunInput1 → 3 → 4 → 7 → 1 → 2 → 6Initial Stateslow = 1fast = 1prev = nullIteration 1fast → 4slow → 3prev → 1Iteration 2fast → 1slow → 4prev → 3Iteration 3fast → nullslow → 7prev → 4After Loopslow = 7 (middle node)prev = 4Deletionprev.next = slow.nextResult:1 → 3 → 4 → 1 → 2 → 6Optimized Code (Java)class Solution {public ListNode deleteMiddle(ListNode head) {// Edge case: single nodeif(head == null) return head;if(head.next == null) return null;ListNode slow = head;ListNode fast = head;ListNode prev = null;// Traverse using fast and slow pointerwhile(fast != null && fast.next != null){fast = fast.next.next;prev = slow;slow = slow.next;}// Remove middle nodeprev.next = slow.next;return head;}}Complexity AnalysisTime Complexity: O(n)Space Complexity: O(1)Only one traversal of the linked listNo extra data structures usedEdge CasesSingle NodeInput: [1]Output: []Two NodesInput: [2, 1]Output: [2]Even Length ListInput: [1, 2, 3, 4]n = 4Middle index = 2Node removed = 3Key TakeawaysFast and slow pointer reduces two-pass solution to one-passTracking the previous node is necessary for deletionWorks efficiently for large linked listsA fundamental pattern used in multiple linked list problemsConclusionThe fast and slow pointer technique provides an elegant and efficient way to identify and remove the middle node in a linked list. By leveraging different traversal speeds, the problem can be solved in a single pass with constant space, making it optimal for both interviews and practical implementations.

LeetCodeMediumLinked ListFast and Slow Pointer

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

Contains Duplicate

LeetCode Problem 217Link of the Problem to try -: LinkGiven an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.Example 1:Input: nums = [1,2,3,1]Output: trueExplanation:The element 1 occurs at the indices 0 and 3.Example 2:Input: nums = [1,2,3,4]Output: falseExplanation:All elements are distinct.Example 3:Input: nums = [1,1,1,3,3,4,3,2,4,2]Output: trueConstraints:1 <= nums.length <= 105-109 <= nums[i] <= 109Solution:1. The HashMap ApproachUsing a HashMap is a highly effective way to track occurrences. Although we are only checking for the existence of a value, the HashMap logic allows us to store the element as a "Key" and its frequency as a "Value."Logic:Iterate through the nums array.Before inserting an element, check if the HashMap already contains that key.If it exists, you've found your duplicate—return true.Otherwise, put the value into the map and continue.Code:public boolean containsDuplicate(int[] nums) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {// Check if the current number is already a key in our mapif (map.containsKey(nums[i])) {return true;}// Map the number to its count (1)map.put(nums[i], 1);}return false;}2. The HashSet Approach (Optimized for Storage)While similar to the HashMap, the HashSet is often more appropriate for this specific problem because we only care if a number exists, not how many times it appears or what its index is.Logic:We initialize an empty HashSet.As we loop through the array, we check ms.contains(nums[i]).If the set already has the number, it's a duplicate.This approach is preferred over HashMap for this problem because it uses less memory and has cleaner syntax.Code:public boolean containsDuplicate(int[] nums) {HashSet<Integer> ms = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (ms.contains(nums[i])) {return true;}ms.add(nums[i]);}return false;}3. The Sorting & Two-Pointer ApproachIf you want to avoid using extra memory (like a Set or Map), you can use the Two-Pointer method combined with Sorting.Logic:First, we sort the array. This ensures that any duplicate values are placed next to each other.We use two pointers: j (the previous element) and i (the current element).By moving these pointers across the array, we compare the values. If nums[i] == nums[j], a duplicate exists.Code:public boolean containsDuplicate(int[] nums) {// Step 1: Sort the arrayArrays.sort(nums);// Step 2: Use two pointers to compare adjacent elementsint j = 0;for (int i = 1; i < nums.length; i++) {if (nums[i] == nums[j]) {return true; // Duplicate found}j++; // Move the previous pointer forward}return false;}Performance SummaryApproachTime ComplexitySpace ComplexityRecommendationHashSetO(n)O(n)Best Overall – Fastest performance.HashMapO(n)O(n)Good, but HashSet is cleaner for this use case.Two PointerO(n \log n)O(1)Best for Memory – Use if space is limited.Final ThoughtsChoosing the right approach depends on whether you want to prioritize speed (HashSet) or memory efficiency (Two-Pointer). For most coding interviews, the HashSet solution is the "Gold Standard" due to its linear time complexity.

LeetCodeEasyHashMap

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 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/odd-even-linked-list/Problem Description (In Very Simple Words)You are given the head of a linked list.Your task is:👉 Rearrange the list such that:All nodes at odd positions come firstFollowed by all nodes at even positionsImportant Clarification❗ This problem is about positions (indices), NOT values.1st node → Odd2nd node → Even3rd node → Odd4th node → EvenExample WalkthroughExample 1Input:[1,2,3,4,5]Positions:1(odd), 2(even), 3(odd), 4(even), 5(odd)Output:[1,3,5,2,4]Example 2Input:[2,1,3,5,6,4,7]Output:[2,3,6,7,1,5,4]Constraints0 <= number of nodes <= 10^4-10^6 <= Node.val <= 10^6Core Idea of the ProblemWe need to:Separate nodes into two groups:Odd index nodesEven index nodesMaintain their original orderFinally:👉 Attach even list after odd listThinking About Different ApproachesWhen solving this problem, multiple approaches may come to mind:Approach 1: Create New ListsIdeaTraverse the listCreate new nodes for odd and even positionsBuild two separate listsMerge themProblem with This Approach❌ Uses extra space❌ Not optimal (violates O(1) space requirement)❌ Code becomes messy and harder to maintainYour approach is logically correct, but:👉 It is not optimal and can be simplified a lot.Approach 2: Brute Force Using Array/ListIdeaStore nodes in an arrayRearrange based on indicesRebuild linked listComplexityTime: O(n)Space: O(n) ❌ (Not allowed)Approach 3: Optimal In-Place Approach (Best Solution)This is the cleanest and most important approach.Optimal Approach: Two Pointer Technique (In-Place)IdeaInstead of creating new nodes:👉 We rearrange the existing nodesWe maintain:odd → points to odd nodeseven → points to even nodesevenHead → stores start of even listVisualizationInput:1 → 2 → 3 → 4 → 5We separate into:Odd: 1 → 3 → 5Even: 2 → 4Final:1 → 3 → 5 → 2 → 4Step-by-Step LogicStep 1: Initialize pointersodd = headeven = head.nextevenHead = head.nextStep 2: Traverse the listWhile:even != null && even.next != nullUpdate:odd.next = odd.next.nexteven.next = even.next.nextMove pointers forward:odd = odd.nexteven = even.nextStep 3: Mergeodd.next = evenHeadClean Java Implementation (Optimal)class Solution { public ListNode oddEvenList(ListNode head) { // Edge case if(head == null || head.next == null) return head; // Initialize pointers ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; // Rearranging nodes while(even != null && even.next != null){ odd.next = odd.next.next; // Link next odd even.next = even.next.next; // Link next even odd = odd.next; even = even.next; } // Attach even list after odd list odd.next = evenHead; return head; }}Dry Run (Important)Input:1 → 2 → 3 → 4 → 5Steps:Iteration 1:odd → 1, even → 2Link:1 → 32 → 4Iteration 2:odd → 3, even → 4Link:3 → 54 → nullFinal connection:5 → 2Result:1 → 3 → 5 → 2 → 4Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why This Approach is BestFeatureResultExtra Space❌ NoneClean Code✅ YesEfficient✅ O(n)Interview Friendly✅ HighlyCommon Mistakes❌ Confusing values with positions❌ Creating new nodes unnecessarily❌ Forgetting to connect even list at the end❌ Breaking the list accidentallyKey LearningThis problem teaches:In-place linked list manipulationPointer handlingList partitioningFinal ThoughtsThe Odd Even Linked List problem is a classic example of how powerful pointer manipulation can be.Even though creating new nodes might seem easier at first, the in-place approach is:👉 Faster👉 Cleaner👉 Interview optimized👉 Tip: Whenever you are asked to rearrange a linked list, always think:"Can I solve this by just changing pointers instead of creating new nodes?"That’s the key to mastering linked list problems 🚀

Linked ListPointer ManipulationIn-Place AlgorithmTwo PointersLeetCode Medium

Maximum Twin Sum of a Linked List (LeetCode 2130) — Intuition, Dry Run & Optimal Approach

🔗 Try This ProblemPractice here:https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/📌 Problem OverviewYou are given a linked list of even length.Each node has a twin node defined as:Node at index i → Twin is at index (n - 1 - i)👉 Example (n = 4):Index 0 ↔ Index 3Index 1 ↔ Index 2The twin sum is:node[i] + node[n - 1 - i]🎯 Goal:Return the maximum twin sum among all such pairs.🧠 Understanding the ProblemLet’s take a simple example:Input: [4, 2, 2, 3]Pairs:4 + 3 = 72 + 2 = 4👉 So the answer is:7💡 Intuition — How to Think About This ProblemAt first glance, it feels like we need to access:First nodeLast nodeSecond nodeSecond last node👉 This naturally suggests:Two-directional accessBut linked lists don’t allow backward traversal🤔 Possible Thinking Patterns🔹 Idea 1: Use Extra SpaceStore values in an arrayUse two pointers from both ends✔ Works❌ But uses extra space O(n)🔹 Idea 2: Work Directly on Linked List (Better)We need a way to:Reach the middleAccess second half in reverse order👉 That leads to a powerful idea:“What if we reverse the second half of the list?”Now we can compare:First half (forward)Second half (also forward after reversal)🎥 Visual Intuition (Your Explanation Video)👉 In this section, focus only on:ConceptVisualizationThought process❌ Avoid code here✔ Build understanding⚙️ Optimized Approach (Step-by-Step)Step 1: Find MiddleUse two pointers:slow → moves 1 stepfast → moves 2 steps👉 When fast reaches end → slow is at middleStep 2: Reverse Second HalfStart from:slow.nextReverse the listStep 3: Compare Twin PairsNow:One pointer → start of listOne pointer → start of reversed halfCalculate:sum = left.val + right.valTrack maximum🧪 Dry RunExample:Input: [5, 4, 2, 1]Step 1: Find MiddleSlow → 4Fast → EndStep 2: Reverse Second HalfSecond half: 2 → 1Reversed: 1 → 2Step 3: Compare5 + 1 = 64 + 2 = 6✅ Maximum = 6💻 Optimized Code (Java)class Solution {public ListNode reverse(ListNode head){ListNode curr = head;ListNode prev = null;while(curr != null){ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}public int pairSum(ListNode head) {ListNode slow = head;ListNode fast = head;// Find middlewhile(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;}// Reverse second halfListNode secondHalf = reverse(slow.next);// Compare pairsListNode firstHalf = head;int max = Integer.MIN_VALUE;while(secondHalf != null){int sum = firstHalf.val + secondHalf.val;max = Math.max(max, sum);firstHalf = firstHalf.next;secondHalf = secondHalf.next;}return max;}}⏱️ Complexity AnalysisTypeValueTime ComplexityO(n)Space ComplexityO(1)🧩 Key TakeawaysLinked list problems often require restructuring instead of extra spaceReversing half is a powerful trickFast & slow pointer is essential for mid-finding🏁 Final ThoughtsThis problem is a perfect example of:Combining multiple conceptsOptimizing spaceThinking beyond direct access👉 Once you understand this pattern, many linked list problems become easier.

LeetcodeMediumLinkedListFast and Slow Pointer

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

IntroductionFinding substrings with unique characters is a common problem in string manipulation and interview questions.GFG’s Longest Substring with K Unique Characters problem challenges you to find the length of the longest substring containing exactly K distinct characters.The focus is not just on brute-force solutions, but on using sliding window with a HashMap to efficiently track character frequencies and window boundaries.If you’d like to try solving the problem first, you can attempt it here: Try the problem on GeeksforGeeks: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A string s of lowercase lettersAn integer kYour task: Return the length of the longest substring containing exactly k distinct characters.Examples:Input: s = "aabacbebebe", k = 3Output: 7Explanation: "cbebebe" is the longest substring with 3 distinct characters.Input: s = "aaaa", k = 2Output: -1Explanation: No substring contains exactly 2 distinct characters.Input: s = "aabaaab", k = 2Output: 7Explanation: "aabaaab" has exactly 2 unique characters.A naive approach would try all possible substrings, count unique characters, and track the max length.Time Complexity: O(n²)Inefficient for large stringsKey Idea: Sliding Window + HashMapInstead of recomputing the unique characters for every substring:Use a HashMap to store character frequencies in the current windowUse two pointers (i and j) to maintain the windowExpand the window by moving j and add characters to the mapShrink the window from the left when the number of unique characters exceeds kUpdate the max length whenever the window has exactly k unique charactersThis ensures each character is processed only once, giving a linear solution.Approach (Step-by-Step)Initialize a HashMap mp to store character countsUse two pointers i (window start) and j (window end)Iterate over the string with jAdd s[j] to the map and update its countCheck the map size:If size < k → move j forwardIf size == k → update max length, move j forwardIf size > k → shrink window from i until map size <= kAfter iterating, return max (or -1 if no valid substring exists)Optimization:Using a HashMap avoids recalculating the number of unique characters for every substringSliding window ensures O(n) complexityImplementation (Java)class Solution {public int longestKSubstr(String s, int k) {HashMap<Character,Integer> mp = new HashMap<>();int i = 0, j = 0;int max = -1;while (j < s.length()) {// Add current character to mapmp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);if (mp.size() < k) {j++;}else if (mp.size() == k) {// Update max length when exactly k unique charactersmax = Math.max(max, j - i + 1);j++;}else {// Shrink window until map size <= kwhile (mp.size() > k) {mp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);if (mp.get(s.charAt(i)) == 0) {mp.remove(s.charAt(i));}i++;}max = Math.max(max, j - i + 1);j++;}}return max;}}Dry Run ExampleInput:s = "aabacbebebe", k = 3Execution:Window [0-4] = "aaba" → unique = 2 → continueWindow [1-6] = "abacb" → unique = 3 → max = 5Window [4-10] = "cbebebe" → unique = 3 → max = 7Output:7Complexity AnalysisTime Complexity: O(n) → Each character enters and leaves the window onceSpace Complexity: O(k) → HashMap stores at most k unique charactersEdge Cases Consideredk greater than number of unique characters → return -1Entire string has exactly k unique charactersString with repeated characters onlyMinimum string length (1)Sliding Window Pattern ImportanceThis problem reinforces a common sliding window + hashmap pattern used in:Longest substring problems with constraintsCounting substrings with exactly K conditionsOptimizing brute-force approaches to linear solutionsConclusionBy combining sliding window with HashMap frequency tracking, we reduce an O(n²) problem to O(n).Once you master this approach, many string and substring problems with constraints on unique characters become much easier to solve efficiently.

SlidingWindowHashMapStringsGFG

LeetCode 234: Palindrome Linked List (Java) | Intuition, Dry Run & O(1) Space Solution

🧩 Problem OverviewGiven the head of a singly linked list, determine whether it is a palindrome.A palindrome means the sequence reads the same forward and backward.Example:Input: [1,2,2,1] → Output: trueInput: [1,2] → Output: false🎯 Why This Problem MattersThis problem tests:Linked list traversalTwo-pointer technique (slow & fast)In-place reversalIt’s a must-know pattern for interviews.🧠 IntuitionA simple approach is to copy elements into an array and check for palindrome.But that uses extra space O(n).Optimal Idea:We can solve this in O(1) space by:Finding the middle of the linked listReversing the second halfComparing both halves🎥 Dry Run (Step-by-Step Explanation)👉 Watch the complete dry run and pointer movement below:This video explains how slow and fast pointers work and how the comparison is performed.⚙️ ApproachStep 1: Handle Edge CasesIf list has one node → return trueStep 2: Find MiddleUse slow and fast pointersFast moves 2 steps, slow moves 1Step 3: Reverse Second HalfReverse the list starting from the middleStep 4: Compare Both HalvesCompare values from:start of liststart of reversed half💻 Java Solutionclass Solution {public ListNode reverse(ListNode head) {ListNode curr = head;ListNode prev = null;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}public boolean isPalindrome(ListNode head) {if (head == null) return false;if (head.next == null) return true;ListNode slow = head;ListNode fast = head;// Find middlewhile (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// Reverse second halfListNode secondHalf = reverse(slow);// Compare both halvesListNode firstHalf = head;while (secondHalf != null) {if (secondHalf.val != firstHalf.val) {return false;}secondHalf = secondHalf.next;firstHalf = firstHalf.next;}return true;}}🔍 Dry Run (Quick Summary)Example:1 → 2 → 2 → 1Middle foundSecond half reversedCompare values one by oneResult → Palindrome ✅⏱️ Time and Space ComplexityTime Complexity: O(n)Space Complexity: O(1)⚠️ Edge CasesSingle nodeTwo nodesOdd length listEven length list💡 Key TakeawaysFast & slow pointer technique is essentialReversing linked list is a reusable patternHelps optimize space complexity🚀 Final ThoughtsThis is a classic interview problem combining multiple linked list techniques.Make sure you understand:Pointer movementReversal logicComparison step👉 For full clarity, don’t skip the video explanation above.

LinkedListFast and Slow PointerPalindromeEasy

Fruit Into Baskets – Sliding Window with Two Types

IntroductionLeetCode 904: Fruit Into Baskets is a classic sliding window problem that tests your ability to track a limited number of distinct elements in a subarray.The problem can be rephrased as:Find the longest subarray containing at most 2 distinct types of elements.This is a great example of using HashMap + sliding window to efficiently track counts of elements while expanding and shrinking the window.If you’d like to try solving the problem first, you can attempt it here:Try the problem on LeetCode:https://leetcode.com/problems/fruit-into-baskets/Problem UnderstandingYou are given:An array fruits where fruits[i] represents the type of fruit from tree iTwo baskets, each can hold only one type of fruitRules:Start at any tree and move only to the rightPick exactly one fruit from each tree while movingStop when a tree’s fruit cannot fit in your basketsGoal: Return the maximum number of fruits you can pick.Examples:Input: fruits = [1,2,1]Output: 3Explanation: Pick all fruits [1,2,1].Input: fruits = [0,1,2,2]Output: 3Explanation: Best subarray [1,2,2].Input: fruits = [1,2,3,2,2]Output: 4Explanation: Best subarray [2,3,2,2].A naive approach would check all subarrays, count distinct fruits, and pick the max →Time Complexity: O(n²) → too slow for fruits.length up to 10⁵Key Idea: Sliding Window with At Most Two TypesInstead of brute-force:Track the number of each fruit type in the current window using a HashMapUse two pointers i and j for the windowExpand j by adding fruits[j] to the mapIf the number of distinct types mp.size() exceeds 2:Shrink the window from the left (i) until mp.size() <= 2The window length j - i + 1 gives the max fruits collected so farIntuition:Only two baskets → window can contain at most 2 distinct fruitsThe sliding window efficiently finds the longest subarray with ≤ 2 distinct elementsApproach (Step-by-Step)Initialize i = 0, j = 0 for window pointersInitialize HashMap mp to store fruit countsInitialize co = 0 → maximum fruits collectedIterate j over fruits:Add fruits[j] to the mapCheck mp.size():If ≤ 2 → update co = max(co, j - i + 1)If > 2 → shrink window from i until mp.size() <= 2Continue expanding the windowReturn co as the maximum fruits collectedOptimization:HashMap keeps track of counts → no need to scan subarray repeatedlySliding window ensures linear traversalImplementation (Java)class Solution {public int totalFruit(int[] nums) {HashMap<Integer,Integer> mp = new HashMap<>();int i = 0, j = 0; // window pointersint co = 0; // max fruits collectedwhile (j < nums.length) {// Add current fruit to mapmp.put(nums[j], mp.getOrDefault(nums[j], 0) + 1);if (mp.size() <= 2) {co = Math.max(co, j - i + 1); // valid windowj++;} else {// Shrink window until at most 2 types of fruitswhile (mp.size() > 2) {mp.put(nums[i], mp.get(nums[i]) - 1);if (mp.get(nums[i]) == 0) {mp.remove(nums[i]);}i++;}co = Math.max(co, j - i + 1);j++;}}return co;}}Dry Run ExampleInput:fruits = [1,2,3,2,2]Execution:Window [i, j]Fruit counts mpDistinct TypesValid?Max co[0,0] → [1]{1:1}1Yes1[0,1] → [1,2]{1:1,2:1}2Yes2[0,2] → [1,2,3]{1:1,2:1,3:1}3No → shrink2[1,2] → [2,3]{2:1,3:1}2Yes2[1,3] → [2,3,2]{2:2,3:1}2Yes3[1,4] → [2,3,2,2]{2:3,3:1}2Yes4Output:4Complexity AnalysisTime Complexity: O(n) → Each element is added and removed at most onceSpace Complexity: O(1) → HashMap stores at most 2 types of fruitsEdge Cases ConsideredArray with ≤ 2 types → entire array can be pickedArray with all same type → window length = array lengthZeros or non-continuous fruit types → handled by sliding windowLarge arrays up to 10⁵ elements → O(n) solution works efficientlySliding Window Pattern ImportanceThis problem demonstrates the sliding window + frequency map pattern:Track limited number of distinct elementsExpand/shrink window dynamicallyEfficiently compute max subarray length with constraintsIt’s directly related to problems like:Max consecutive ones with flipsLongest substring with k distinct charactersFruit collection / subarray problems with type limitsConclusionBy tracking fruit counts with a HashMap in a sliding window, we efficiently find the maximum fruits collectible in O(n) time.Mastering this pattern allows solving many array and string problems with constraints on distinct elements in a linear and elegant way.

SlidingWindowHashMapLeetCodeMedium

LeetCode 1614: Maximum Nesting Depth of Parentheses — Java Solution Explained

IntroductionLeetCode 1614 Maximum Nesting Depth of Parentheses is a natural follow-up to LeetCode 20 Valid Parentheses. While LeetCode 20 asks "are the brackets valid?", this problem asks "how deeply are they nested?" It is a clean, focused problem that teaches you how to think about bracket depth — a concept that appears in compilers, parsers, JSON validators, and XML processors in real world software.Here is the Link of Question -: LeetCode 1614In this article we cover plain English explanation, real life analogy, two Java approaches with dry runs, complexity analysis, and all the important details you need for interviews.What Is the Problem Really Asking?You are given a valid parentheses string. You need to find the maximum number of nested (not just sequential) open parentheses at any point in the string.The key distinction here is nested vs sequential:"()()()" → depth is 1, brackets are sequential not nested"((()))" → depth is 3, brackets are fully nested inside each other"()(())" → depth is 2, the second pair is nested one level deepReal Life Analogy — Folders Inside FoldersThink of your computer's file system. You have a folder, inside that a subfolder, inside that another subfolder. The depth is how many folders deep you are at the deepest point."(1+(2*3)+((8)/4))+1" is like:Outer folder ( → depth 1Inner folder ( inside it → depth 2Innermost folder (( → depth 3The answer is how deep the deepest file is buried. You do not care about other folders — just the maximum depth reached at any single moment.Approach 1: Stack Based Solution (Classic)The IdeaUse a stack exactly like LeetCode 20. Every time you push an opening bracket, increment a counter. Every time you pop a closing bracket, record the max before decrementing. The stack size at any moment represents current depth.public int maxDepth(String s) { Stack<Character> st = new Stack<>(); int current = 0; int max = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { st.push(c); current++; max = Math.max(max, current); // record depth when going deeper } else if (c == ')') { if (!st.empty() && st.peek() == '(') { max = Math.max(max, current); current--; st.pop(); } } } return max;}Dry Run — s = "()(())((()()))"( → push, current = 1, max = 1) → pop, current = 0( → push, current = 1, max = 1( → push, current = 2, max = 2) → pop, current = 1) → pop, current = 0( → push, current = 1, max = 2( → push, current = 2, max = 2( → push, current = 3, max = 3 ✅) → pop, current = 2( → push, current = 3, max = 3) → pop, current = 2) → pop, current = 1) → pop, current = 0✅ Output: 3Time Complexity: O(n) — single pass Space Complexity: O(n) — stack holds up to n/2 opening bracketsApproach 2: Counter Only — No Stack (Optimal) ✅The IdeaThis is the smartest approach and the real insight of this problem. You do not actually need a stack at all! Think about it — the depth at any moment is simply how many unmatched opening brackets we have seen so far. That is just a counter!( → increment counter, update max) → decrement counterEverything else → ignorepublic int maxDepth(String s) { int current = 0; int max = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { current++; max = Math.max(max, current); } else if (s.charAt(i) == ')') { current--; } } return max;}This is beautifully simple. No stack, no extra memory, just two integer variables.Dry Run — s = "(1+(2*3)+((8)/4))+1"Only tracking ( and ), ignoring digits and operators:( → current = 1, max = 1( → current = 2, max = 2) → current = 1( → current = 2, max = 2( → current = 3, max = 3 ✅) → current = 2) → current = 1) → current = 0✅ Output: 3Time Complexity: O(n) — single pass Space Complexity: O(1) — only two integer variables, no extra storage!Why Update Max on ( Not on )?This is the most important implementation detail. You update max when you open a bracket, not when you close it. Why?Because when you encounter (, your depth just increased to a new level — that is when you might have hit a new maximum. When you encounter ), you are going back up — depth is decreasing, so it can never be a new maximum.Always capture the peak on the way down into nesting, not on the way back out.Stack vs Counter — Which to Use?The counter approach is strictly better here — same time complexity but O(1) space instead of O(n). In an interview, start by mentioning the stack approach to show you recognize the stack pattern, then immediately offer the counter optimization to show deeper understanding.This mirrors the same progression as LeetCode 844 Backspace String Compare — where the O(1) two pointer follow-up impressed interviewers more than the standard stack solution.How This Fits the Stack Pattern SeriesLooking at the full series you have been solving:20 Valid Parentheses — are brackets correctly matched? 1614 Maximum Nesting Depth — how deeply are they nested?These two problems are complementary. One validates structure, the other measures depth. Together they cover the two most fundamental questions you can ask about a bracket string. Real world parsers need to answer both — "is this valid?" and "how complex is the nesting?"Common Mistakes to AvoidUpdating max after decrementing on ) If you write current-- before Math.max, you will always be one level too low and miss the true maximum. Always capture max before or at the moment of increment, never after decrement.Counting all characters not just brackets Digits, operators like +, -, *, / must be completely ignored. Only ( and ) affect depth.Using a Stack when a counter suffices Since the problem guarantees a valid parentheses string, you never need to validate matching — just track depth. A Stack adds unnecessary complexity and memory overhead here.FAQs — People Also AskQ1. What is nesting depth in LeetCode 1614? Nesting depth is the maximum number of open parentheses that are simultaneously unclosed at any point in the string. For example "((()))" has depth 3 because at the innermost point, three ( are open at the same time.Q2. What is the best approach for LeetCode 1614 in Java? The counter approach is optimal — O(n) time and O(1) space. Increment a counter on (, update max, decrement on ). No stack needed since the string is guaranteed to be a valid parentheses string.Q3. What is the time complexity of LeetCode 1614? Both approaches are O(n) time. The Stack approach uses O(n) space while the counter approach uses O(1) space, making the counter approach strictly better.Q4. What is the difference between LeetCode 20 and LeetCode 1614? LeetCode 20 validates whether a bracket string is correctly formed. LeetCode 1614 assumes the string is already valid and asks how deeply the brackets are nested. LeetCode 20 needs a stack for matching; LeetCode 1614 only needs a counter.Q5. Is LeetCode 1614 asked in coding interviews? It appears occasionally as a warmup or follow-up after LeetCode 20. The more important skill it tests is recognizing when a stack can be replaced by a simpler counter — that kind of space optimization thinking is valued in interviews.Similar LeetCode Problems to Practice Next20. Valid Parentheses — Easy — validate bracket structure1021. Remove Outermost Parentheses — Easy — depth-based filtering1249. Minimum Remove to Make Valid Parentheses — Medium — remove minimum brackets32. Longest Valid Parentheses — Hard — longest valid substring394. Decode String — Medium — nested brackets with encodingConclusionLeetCode 1614 Maximum Nesting Depth of Parentheses teaches a deceptively simple but important lesson — not every bracket problem needs a stack. When the string is guaranteed valid and you only need to measure depth, a counter is all you need.The progression from LeetCode 20 to 1614 perfectly illustrates how understanding the core problem deeply leads to elegant simplifications. Master both, understand why one needs a stack and the other does not, and you will have a strong foundation for every bracket problem in your interview journey.

StringStackLeetCodeEasy

LeetCode 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

IntroductionIn this article, we will solve LeetCode 187: Repeated DNA Sequences using Java. This is a popular string problem that tests your understanding of the sliding window technique and efficient use of hash-based data structures.DNA sequences are composed of four characters:A (Adenine)C (Cytosine)G (Guanine)T (Thymine)The goal is to identify all 10-letter-long substrings that appear more than once in a given DNA string.You can try solving the problem directly on LeetCode here: https://leetcode.com/problems/repeated-dna-sequences/Problem StatementGiven a string s that represents a DNA sequence, return all the 10-letter-long substrings that occur more than once.Example 1Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"Output: ["AAAAACCCCC", "CCCCCAAAAA"]Example 2Input: s = "AAAAAAAAAAAAA"Output: ["AAAAAAAAAA"]Key ObservationsWe only need substrings of fixed length 10.The maximum length of the string can be up to 10^5.A brute-force solution checking all substrings multiple times would be inefficient.This problem can be solved efficiently using a sliding window and hash-based data structures.Approach 1: Sliding Window with HashSet (Given Solution)IdeaUse two pointers (i and j) to maintain a sliding window.Build a substring of size 10 dynamically.Store previously seen substrings in a HashSet.If a substring is already present in the set:Check if it is already in the result list.If not, add it to the result list.Slide the window forward and continue.Java Code (Your Implementation)class Solution { public List<String> findRepeatedDnaSequences(String s) { HashSet<String> ms = new HashSet<>(); List<String> lis = new ArrayList<>(); int i = 0; int j = 0; String tes = ""; while (j < s.length()) { tes += s.charAt(j); if (j - i + 1 < 10) { j++; } else { if (j - i + 1 == 10) { if (ms.contains(tes)) { boolean fl = false; for (String a : lis) { if (a.equals(tes)) { fl = true; } } if (!fl) { lis.add(tes); } } else { ms.add(tes); } tes = tes.substring(1); i++; j++; } } } return lis; }}ExplanationThe variable tes maintains the current substring.ms stores all previously seen substrings of length 10.If a substring already exists in ms, we manually check whether it has already been added to the result list.This avoids duplicate entries in the final output.Time ComplexitySliding through the string: O(n)Checking duplicates in the result list: O(n) in the worst caseOverall worst-case complexity: O(n²)Space ComplexityHashSet storage: O(n)Limitation of Approach 1The manual duplicate check using a loop inside the result list introduces unnecessary overhead. This makes the solution less efficient.We can improve this by using another HashSet to automatically handle duplicates.Approach 2: Optimized Solution Using Two HashSetsIdeaUse one HashSet called seen to track all substrings of length 10.Use another HashSet called repeated to store substrings that appear more than once.Iterate from index 0 to s.length() - 10.Extract substring of length 10.If adding to seen fails, it means it has appeared before.Add it directly to repeated.This removes the need for a nested loop.Optimized Java Codeclass Solution { public List<String> findRepeatedDnaSequences(String s) { Set<String> seen = new HashSet<>(); Set<String> repeated = new HashSet<>(); for (int i = 0; i <= s.length() - 10; i++) { String substring = s.substring(i, i + 10); if (!seen.add(substring)) { repeated.add(substring); } } return new ArrayList<>(repeated); }}Why This Approach is BetterNo manual duplicate checking.Cleaner and more readable code.Uses HashSet properties efficiently.Each substring is processed only once.Time Complexity (Optimized)Single traversal of the string: O(n)Substring extraction of fixed length 10: O(1)Overall time complexity: O(n)Space ComplexityTwo HashSets storing substrings: O(n)ConclusionLeetCode 187 is a classic example of combining the sliding window technique with hash-based data structures.The first approach works but has unnecessary overhead due to manual duplicate checks.The second approach is more optimal, cleaner, and recommended for interviews.Always leverage the properties of HashSet to avoid redundant checks.This problem highlights the importance of choosing the right data structure to optimize performance.

JavaSliding WindowMedium

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/remove-linked-list-elements/Problem Description (In Very Simple Words)You are given:The head of a linked listAn integer value valYour task is:👉 Remove all nodes from the linked list whose value is equal to val.👉 Return the updated head of the linked list.What is a Linked List? (Quick Recap)A linked list is a chain of nodes where each node contains:value + pointer to next nodeExample:1 → 2 → 6 → 3 → 4 → 5 → 6 → nullExample WalkthroughExample 1Input:head = [1,2,6,3,4,5,6]val = 6Output:[1,2,3,4,5]ExplanationWe remove all nodes with value 6.1 → 2 → ❌6 → 3 → 4 → 5 → ❌6Final list:1 → 2 → 3 → 4 → 5Example 2Input:head = []val = 1Output:[]Example 3Input:head = [7,7,7,7]val = 7Output:[]All nodes are removed.Constraints0 <= number of nodes <= 10^41 <= Node.val <= 500 <= val <= 50Understanding the Problem DeeplyThe tricky part is:👉 Nodes can appear anywhere:At the beginningIn the middleAt the endOr all nodes👉 Linked list does NOT allow backward traversalSo we must carefully handle pointers.Thinking About the SolutionWhen solving this problem, multiple approaches may come to mind:Possible ApproachesTraverse the list and remove nodes manually.Handle head separately, then process the rest.Use a dummy node to simplify logic.Use recursion (less preferred for beginners).Approach 1: Without Dummy Node (Manual Handling)IdeaFirst, remove nodes from the start (head) if they match val.Then traverse the list using two pointers:prev → previous nodecurr → current nodeKey ChallengeHandling head separately makes code more complex.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Remove matching nodes from the beginning while(head != null && head.val == val){ head = head.next; } // If list becomes empty if(head == null) return null; ListNode prev = head; ListNode curr = head.next; while(curr != null){ if(curr.val == val){ // Skip the node prev.next = curr.next; } else { // Move prev only when node is not removed prev = curr; } curr = curr.next; } return head; }}Why This WorksWe ensure prev always points to the last valid nodeWhen we find a node to delete:prev.next = curr.nextThis skips the unwanted nodeProblem With This Approach👉 Too many edge cases:Removing head nodesEmpty listAll nodes equalApproach 2: Dummy Node (Best & Clean Approach)IdeaWe create a fake node (dummy) before the head.dummy → head → rest of listThis helps us:👉 Treat head like a normal node👉 Avoid special casesVisualizationOriginal:1 → 2 → 6 → 3After dummy:-1 → 1 → 2 → 6 → 3Java Implementation (Best Approach)class Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Create dummy node ListNode dumm = new ListNode(-1, head); // Step 2: Start from dummy ListNode curr = dumm; while(curr.next != null){ // If next node needs to be removed if(curr.next.val == val){ // Skip that node curr.next = curr.next.next; } else { // Move forward only when no deletion curr = curr.next; } } // Step 3: Return new head return dumm.next; }}Step-by-Step Dry RunInput:1 → 2 → 6 → 3 → 4 → 5 → 6val = 6After dummy:-1 → 1 → 2 → 6 → 3 → 4 → 5 → 6Traversal:curr = -1 → 1 (keep)curr = 1 → 2 (keep)curr = 2 → 6 (remove)curr = 2 → 3 (keep)curr = 3 → 4 (keep)curr = 4 → 5 (keep)curr = 5 → 6 (remove)Final:1 → 2 → 3 → 4 → 5Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why Dummy Node is PreferredWithout DummyWith DummyComplex edge casesClean logicSpecial handling for headNo special handlingError-proneSafe and readableApproach 3: Recursive Solution (Conceptual)IdeaWe process one node at a time and recursively solve for the rest.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) return null; head.next = removeElements(head.next, val); if(head.val == val){ return head.next; } else { return head; } }}Time ComplexityO(n)Space ComplexityO(n)(due to recursion stack)Key TakeawaysLinked list problems are all about pointer manipulationAlways think about edge cases (especially head)Dummy node simplifies almost every linked list problemConclusionThe Remove Linked List Elements problem is perfect for understanding how linked lists work in real scenarios.While the manual approach works, the dummy node technique provides a much cleaner and safer solution.If you master this pattern, you will be able to solve many linked list problems easily in interviews.👉 Tip: Whenever you feel stuck in linked list problems, try adding a dummy node — it often simplifies everything!

Linked ListIterationDummy NodePointer ManipulationLeetCodeEasy

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

IntroductionLeetCode 496 Next Greater Element I is your gateway into one of the most important and frequently tested patterns in coding interviews — the Monotonic Stack. Once you understand this problem deeply, problems like Next Greater Element II, Daily Temperatures, and Largest Rectangle in Histogram all start to make sense.Here is the Link of Question -: LeetCode 496This article covers plain English explanation, real life analogy, brute force and optimal approaches in Java, detailed dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You have two arrays. nums2 is the main array. nums1 is a smaller subset of nums2. For every element in nums1, find its position in nums2 and look to the right — what is the first element that is strictly greater? If none exists, return -1.Example:nums1 = [4,1,2], nums2 = [1,3,4,2]For 4 in nums2: elements to its right are [2], none greater → -1For 1 in nums2: elements to its right are [3,4,2], first greater is 3For 2 in nums2: no elements to its right → -1Output: [-1, 3, -1]Real Life Analogy — The Taller Person in a QueueImagine you are standing in a queue and you want to know — who is the first person taller than you standing somewhere behind you in the line?You look to your right one by one until you find someone taller. That person is your "next greater element." If everyone behind you is shorter, your answer is -1.Now imagine doing this for every person in the queue efficiently — instead of each person looking one by one, you use a smart system that processes everyone in a single pass. That smart system is the Monotonic Stack.Approach 1: Brute Force (Beginner Friendly)The IdeaFor each element in nums1, find its position in nums2, then scan everything to its right to find the first greater element.javapublic int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { int found = -1; boolean seen = false; for (int j = 0; j < nums2.length; j++) { if (seen && nums2[j] > nums1[i]) { found = nums2[j]; break; } if (nums2[j] == nums1[i]) { seen = true; } } ans[i] = found; } return ans;}Simple to understand but inefficient. For each element in nums1 you scan the entire nums2.Time Complexity: O(m × n) — where m = nums1.length, n = nums2.length Space Complexity: O(1) — ignoring output arrayThis works for the given constraints (n ≤ 1000) but will not scale for larger inputs. The follow-up specifically asks for better.Approach 2: Monotonic Stack + HashMap (Optimal Solution) ✅The IdeaThis is your solution and the best one. The key insight is — instead of answering queries for nums1 elements one by one, precompute the next greater element for every element in nums2 and store results in a HashMap. Then answering nums1 queries becomes just a HashMap lookup.To precompute efficiently, we use a Monotonic Stack — a stack that always stays in decreasing order from bottom to top.Why traverse from right to left? Because we are looking for the next greater element to the right. Starting from the right end, by the time we process any element, we have already seen everything to its right.Algorithm:Traverse nums2 from right to leftMaintain a stack of "candidate" next greater elementsFor current element, pop all stack elements that are smaller or equal — they can never be the next greater for anything to the leftIf stack is empty → next greater is -1, else → top of stack is the answerPush current element onto stackStore result in HashMapLook up each nums1 element in the HashMapjavapublic int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> st = new Stack<>(); HashMap<Integer, Integer> mp = new HashMap<>(); // Precompute next greater for every element in nums2 for (int i = nums2.length - 1; i >= 0; i--) { // Pop elements smaller than current — they are useless while (!st.empty() && nums2[i] >= st.peek()) { st.pop(); } // Top of stack is the next greater, or -1 if empty mp.put(nums2[i], st.empty() ? -1 : st.peek()); // Push current element as a candidate for elements to its left st.push(nums2[i]); } // Answer queries for nums1 int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { ans[i] = mp.get(nums1[i]); } return ans;}Why Is the Stack Monotonic?After popping smaller elements, the stack always maintains a decreasing order from bottom to top. This means the top of the stack at any point is always the smallest element seen so far to the right — making it the best candidate for "next greater."This is called a Monotonic Decreasing Stack and it is the heart of this entire pattern.Detailed Dry Run — nums2 = [1,3,4,2]We traverse from right to left:i = 3, nums2[3] = 2Stack is emptyNo elements to popStack empty → mp.put(2, -1)Push 2 → stack: [2]i = 2, nums2[2] = 4Stack top is 2, and 4 >= 2 → pop 2 → stack: []Stack empty → mp.put(4, -1)Push 4 → stack: [4]i = 1, nums2[1] = 3Stack top is 4, and 3 < 4 → stop poppingStack not empty → mp.put(3, 4)Push 3 → stack: [4, 3]i = 0, nums2[0] = 1Stack top is 3, and 1 < 3 → stop poppingStack not empty → mp.put(1, 3)Push 1 → stack: [4, 3, 1]HashMap after processing nums2:1 → 3, 2 → -1, 3 → 4, 4 → -1Now answer nums1 = [4, 1, 2]:nums1[0] = 4 → mp.get(4) = -1nums1[1] = 1 → mp.get(1) = 3nums1[2] = 2 → mp.get(2) = -1✅ Output: [-1, 3, -1]Time Complexity: O(n + m) — n for processing nums2, m for answering nums1 queries Space Complexity: O(n) — HashMap and Stack both store at most n elementsWhy Pop Elements Smaller Than Current?This is the most important thing to understand in this problem. When we are at element x and we see a stack element y where y < x, we pop y. Why?Because x is to the right of everything we will process next (we go right to left), and x is already greater than y. So for any element to the left of x, if they are greater than y, they are definitely also greater than y — meaning y would never be the "next greater" for anything. It becomes useless and gets discarded.This is why the stack stays decreasing — every element we keep is a legitimate candidate for being someone's next greater element.How This Differs From Previous Stack ProblemsYou have been solving stack problems with strings — backspace, stars, adjacent duplicates. This problem introduces the stack for arrays and searching, which is a step up in complexity.The pattern shift is: instead of using the stack to build or reduce a string, we use it to maintain a window of candidates while scanning. This monotonic stack idea is what powers many hard problems like Largest Rectangle in Histogram, Trapping Rain Water, and Daily Temperatures.Common Mistakes to AvoidUsing >= instead of > in the pop condition We pop when nums2[i] >= st.peek(). If you use only >, equal elements stay on the stack and give wrong answers since we need strictly greater.Traversing left to right instead of right to left Going left to right makes it hard to know what is to the right of the current element. Always go right to left for "next greater to the right" problems.Forgetting HashMap lookup handles the nums1 query efficiently Some people recompute inside the nums1 loop. Always precompute in a HashMap — that is the whole point of the optimization.FAQs — People Also AskQ1. What is a Monotonic Stack and why is it used in LeetCode 496? A Monotonic Stack is a stack that maintains its elements in either increasing or decreasing order. In LeetCode 496, a Monotonic Decreasing Stack is used to efficiently find the next greater element for every number in nums2 in a single pass, reducing time complexity from O(n²) to O(n).Q2. What is the time complexity of LeetCode 496 optimal solution? The optimal solution runs in O(n + m) time where n is the length of nums2 and m is the length of nums1. Processing nums2 takes O(n) and answering all nums1 queries via HashMap takes O(m).Q3. Why do we traverse nums2 from right to left? Because we are looking for the next greater element to the right. Starting from the right end means by the time we process any element, we have already seen all elements to its right and stored them in the stack as candidates.Q4. Is LeetCode 496 asked in coding interviews? Yes, it is commonly used as an introduction to the Monotonic Stack pattern at companies like Amazon, Google, and Microsoft. It often appears as a warmup before harder follow-ups like Next Greater Element II (circular array) or Daily Temperatures.Q5. What is the difference between LeetCode 496 and LeetCode 739 Daily Temperatures? Both use the same Monotonic Stack pattern. In 496 you return the actual next greater value. In 739 you return the number of days (index difference) until a warmer temperature. The core stack logic is identical.Similar LeetCode Problems to Practice Next739. Daily Temperatures — Medium — days until warmer temperature, same pattern503. Next Greater Element II — Medium — circular array version901. Online Stock Span — Medium — monotonic stack with span counting84. Largest Rectangle in Histogram — Hard — classic monotonic stack42. Trapping Rain Water — Hard — monotonic stack or two pointerConclusionLeetCode 496 Next Greater Element I is the perfect entry point into the Monotonic Stack pattern. The brute force is easy to understand, but the real learning happens when you see why the stack stays decreasing and how that single insight collapses an O(n²) problem into O(n).Once you truly understand why we pop smaller elements and how the HashMap bridges the gap between precomputation and query answering, the entire family of Next Greater Element problems becomes approachable — including the harder circular and histogram variants.

ArrayStackMonotonic StackHashMapEasyLeetCode

Maximum Average Subarray I — Efficient Solution Using Sliding Window (LeetCode 643)

IntroductionLeetCode Problem 643: Maximum Average Subarray I is a classic problem that tests understanding of arrays and the sliding window technique.The task is simple in description but requires optimization to work efficiently for large inputs.We are given:An integer array numsAn integer kWe must find a contiguous subarray of length k that has the maximum average value, and return that average.If you want to try solving the problem yourself before reading further, you can attempt it here:👉 Try the problem on LeetCode: https://leetcode.com/problems/maximum-average-subarray-i/Problem UnderstandingA brute-force solution would compute the sum for every subarray of length k and track the maximum average. However, recalculating sums repeatedly results in O(n × k) time complexity, which becomes inefficient for large arrays.Instead, we can use the sliding window technique to optimize the process.Key Idea: Sliding WindowInstead of recomputing sums:Compute the sum of the first window of size k.Slide the window forward by:Adding the next elementRemoving the element leaving the windowUpdate the maximum average at each step.This reduces time complexity to O(n).ApproachMaintain two pointers representing the window.Keep adding elements until window size becomes k.Compute average and update maximum.Slide the window by removing the left element.Continue until the end of the array.Implementation (Java)class Solution { public double findMaxAverage(int[] nums, int k) { double ans = Integer.MIN_VALUE; int i = 0; int j = 0; int sum = 0; while (j < nums.length) { sum += nums[j]; if (j - i + 1 < k) { j++; } else { ans = Math.max(ans, (double) sum / k); sum -= nums[i]; i++; j++; } } return ans; }}Dry Run ExampleInput:nums = [1,12,-5,-6,50,3], k = 4Windows examined:[1,12,-5,-6] → avg = 0.5[12,-5,-6,50] → avg = 12.75 (maximum)[-5,-6,50,3] → avg = 10.5Maximum average = 12.75Complexity AnalysisTime Complexity: O(n) Each element enters and leaves the window once.Space Complexity: O(1) No extra space is used apart from variables.Edge Cases ConsideredSingle element array (k = 1)All negative numbersLarge input sizeLarge positive or negative valuesWhy Sliding Window MattersSliding window is a crucial technique used in many interview problems:Subarray sum problemsLongest substring problemsFixed or variable window size optimizationsMastering this pattern greatly improves coding interview performance.ConclusionThis problem demonstrates how recognizing patterns like sliding window can transform a slow brute-force solution into an efficient one.If you are preparing for coding interviews, mastering sliding window problems is essential since they appear frequently.

LeetCodeSliding WindowEasy

Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

🔗 Problem LinkLeetCode 424 – Longest Repeating Character Replacement👉 https://leetcode.com/problems/longest-repeating-character-replacement/IntroductionWhen I first looked at this problem, it didn’t immediately feel like a typical sliding window question. It talks about replacing characters, not finding substrings directly.But the moment you carefully read:"Return the length of the longest substring containing the same letter after at most k replacements."That’s when the pattern becomes clear.This is a variable-size sliding window problem where we try to maintain a valid window under a certain condition.In this blog, I’ll explain:The intuition behind the problemWhy sliding window worksThe key tricky conditionStep-by-step explanation of the codeTime and space complexity📌 Problem UnderstandingWe are allowed to:Pick any character in the stringReplace it with any uppercase letterPerform at most k replacementsWe need to find the maximum length substring that can become all the same character after at most k changes.🧠 Key ObservationIn any window (substring):To make all characters the same, we need to:Keep the most frequent characterReplace all other charactersSo the number of replacements required is:Window Size - Maximum Frequency Character in that WindowIf that value is ≤ k, then the window is valid.This is the most important insight in the entire problem.🚀 Why Sliding Window?We are asked for:Longest substringUnder a constraintWith dynamic window expansionThat is a clear sign of the sliding window pattern.We use:i → left pointerj → right pointerHashMap → to track character frequencies💻 Your Codeclass Solution {public int characterReplacement(String s, int k) {HashMap<Character,Integer> mp = new HashMap<>();int i= 0;int j =0;int co =0;while(j < s.length()){mp.put(s.charAt(j),mp.getOrDefault(s.charAt(j),0)+1);int maxfreq = 0;for(int a : mp.values()){maxfreq = Math.max(maxfreq,a);}while((j - i +1)-maxfreq > k){ // Tricky partmp.put(s.charAt(i),mp.get(s.charAt(i))-1);if(mp.get(s.charAt(i)) == 0){mp.remove(s.charAt(i));}i++;}co = Math.max(co,j-i+1);j++;}return co;}}🔍 Step-by-Step Explanation1️⃣ Expanding the Windowmp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);We add the current character into the frequency map.2️⃣ Finding Maximum Frequencyint maxfreq = 0;for(int a : mp.values()){maxfreq = Math.max(maxfreq,a);}We calculate the highest frequency character inside the window.Why?Because that is the character we will keep.All others will be replaced.3️⃣ The Most Important Condition (Tricky Part)while((j - i +1)-maxfreq > k)Let’s break this:j - i + 1 → Window sizemaxfreq → Count of most frequent characterwindowSize - maxfreq → Replacements neededIf replacements needed > k → window is invalidSo we shrink from left.4️⃣ Shrinking the Windowmp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);if(mp.get(s.charAt(i)) == 0){mp.remove(s.charAt(i));}i++;We remove left character and move i forward.5️⃣ Updating Maximum Lengthco = Math.max(co, j - i + 1);We update our answer whenever the window is valid.🎯 Why This WorksWe always maintain:(window size - most frequent character count) <= kThat guarantees:We can convert the entire window into one repeating character using at most k replacements.⏱ Time and Space ComplexityTime Complexity: O(26 * n) ≈ O(n)For each character, we scan at most 26 letters.Since there are only uppercase letters, this is effectively linear.Space Complexity: O(26)At most 26 uppercase characters stored.🔥 Important Optimization InsightYour solution recalculates maxfreq every time using a loop.A common optimization is:Maintain a global maxfreqUpdate only when expanding windowDo not recalculate during shrinkingThat reduces unnecessary scanning.But your solution is completely correct and efficient.🏁 Final ThoughtsThis problem teaches:Sliding Window with conditionFrequency trackingWindow validation logicThinking in terms of "how many changes needed"The key formula to remember:window size - max frequency <= kIf you truly understand this condition, you unlock many similar problems like:Longest Substring with K ReplacementsMax Consecutive Ones IIIFruit Into Baskets

Sliding WindowLeetCodeTwo PointersHashMapMedium

Count Subarrays of Size K with Average ≥ Threshold — Sliding Window Solution (LeetCode 1343)

IntroductionLeetCode 1343: Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is another excellent problem to practice the sliding window technique.The goal is not just to compute values but to count how many subarrays satisfy a given condition efficiently.You are given:An integer array arrAn integer k representing subarray sizeA threshold valueYou must return the number of subarrays of size k whose average is greater than or equal to the threshold.If you'd like to try solving the problem first, you can attempt it here:👉 Try the problem on LeetCode:https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/Problem UnderstandingA direct approach would calculate the average for every subarray of size k. However, recomputing sums repeatedly leads to unnecessary work.To optimize, we use a sliding window, allowing us to reuse previous computations and move efficiently across the array.Key Idea: Sliding Window OptimizationInstead of calculating sums repeatedly:Maintain the sum of the current window.Slide the window by:Adding the next elementRemoving the element leaving the windowCheck if the average satisfies the threshold.Count valid windows.This ensures each element is processed only once.ApproachMaintain two pointers to represent the window.Add elements until window size reaches k.Check if average meets the threshold.Move the window forward.Count valid subarrays.An important optimization: instead of computing average each time, we can compare the sum with threshold * k. However, your current implementation using division also works correctly.Implementation (Java)class Solution { public int numOfSubarrays(int[] arr, int k, int t) { int curr = 0; int i = 0; int j = 0; int co = 0; while (j < arr.length) { curr += arr[j]; if (j - i + 1 < k) { j++; } else { if (j - i + 1 == k) { if (curr / k >= t) { co++; } curr -= arr[i]; i++; j++; } } } return co; }}Dry Run ExampleInput:arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4Valid subarrays:[2,5,5] → avg = 4[5,5,5] → avg = 5[5,5,8] → avg = 6Total valid subarrays = 3Complexity AnalysisTime Complexity: O(n)Each element enters and leaves the window once.Space Complexity: O(1)Only constant extra variables are used.Edge Cases ConsideredThreshold equals zeroMinimum array lengthLarge array sizesNon-integer averagesAll elements smaller than thresholdSliding Window Pattern ImportanceThis problem reinforces the sliding window pattern, which appears frequently in:Fixed-size window problemsMaximum or minimum subarray problemsCounting valid segmentsString window problemsMastering this pattern helps solve many interview questions efficiently.ConclusionThis problem is a strong example of turning a potentially expensive brute-force approach into an efficient linear solution using sliding window.Once you recognize this pattern, many array and string problems become significantly easier to solve.

LeetCodeSliding WindowMedium

Mastering Binary Search – LeetCode 704 Explained

IntroductionBinary Search is one of the most fundamental and powerful algorithms in computer science. If you're preparing for coding interviews, mastering Binary Search is absolutely essential.In this blog, we’ll break down LeetCode 704 – Binary Search, explain the algorithm in detail, walk through your Java implementation, analyze complexity, and recommend additional problems to strengthen your understanding.You can try this problem -: Problem Link📌 Problem OverviewYou are given:A sorted array of integers nums (ascending order)An integer targetYour task is to return the index of target if it exists in the array. Otherwise, return -1.Example 1Input: nums = [-1,0,3,5,9,12], target = 9Output: 4Example 2Input: nums = [-1,0,3,5,9,12], target = 2Output: -1Constraints1 <= nums.length <= 10⁴All integers are uniqueThe array is sorted in ascending orderRequired Time Complexity: O(log n)🚀 Understanding the Binary Search AlgorithmBinary Search works only on sorted arrays.Instead of checking each element one by one (like Linear Search), Binary Search:Finds the middle element.Compares it with the target.Eliminates half of the search space.Repeats until the element is found or the search space is empty.Why is it Efficient?Every iteration cuts the search space in half.If the array size is n, the number of operations becomes:log₂(n)This makes it extremely efficient compared to linear search (O(n)).🧠 Step-by-Step AlgorithmInitialize two pointers:low = 0high = nums.length - 1While low <= high:Calculate middle index:mid = low + (high - low) / 2If nums[mid] == target, return midIf target > nums[mid], search right half → low = mid + 1Else search left half → high = mid - 1If loop ends, return -1💻 Your Java Code ExplainedHere is your implementation:class Solution {public int search(int[] nums, int target) {int high = nums.length-1;int low = 0;while(low <= high){int mid = low+(high-low)/2;if(target == nums[mid] ){return mid;}else if(target > nums[mid]){low = mid+1;}else{high = mid-1;}}return -1;}}🔍 Code Breakdown1️⃣ Initialize Boundariesint high = nums.length - 1;int low = 0;You define the search space from index 0 to n-1.2️⃣ Loop Conditionwhile(low <= high)The loop continues as long as there is a valid search range.3️⃣ Safe Mid Calculationint mid = low + (high - low) / 2;This is preferred over:(low + high) / 2Why?Because (low + high) may cause integer overflow in large arrays.Your approach prevents that.4️⃣ Comparison Logicif(target == nums[mid])If found → return index.else if(target > nums[mid])low = mid + 1;Search in right half.elsehigh = mid - 1;Search in left half.5️⃣ Not Found Casereturn -1;If the loop finishes without finding the target.⏱ Time and Space ComplexityTime Complexity: O(log n)Each iteration halves the search space.Space Complexity: O(1)No extra space used — purely iterative.🔥 Why This Problem Is ImportantLeetCode 704 is:The foundation of all Binary Search problemsA template questionFrequently asked in interviewsRequired to understand advanced problems like:Search in Rotated Sorted ArrayFind First and Last PositionPeak ElementBinary Search on Answer📚 Recommended Binary Search Practice ProblemsAfter solving this, practice these in order:🟢 Easy35. Search Insert Position69. Sqrt(x)278. First Bad Version🟡 Medium34. Find First and Last Position of Element in Sorted Array33. Search in Rotated Sorted Array74. Search a 2D Matrix875. Koko Eating Bananas (Binary Search on Answer)🔴 Advanced Pattern Practice1011. Capacity To Ship Packages Within D Days410. Split Array Largest SumThese will help you master:Lower bound / upper boundBinary search on monotonic functionsSearching in rotated arraysSearching in 2D matricesBinary search on answer pattern🎯 Final ThoughtsBinary Search is not just a single algorithm — it’s a pattern.If you truly understand:How the search space shrinksWhen to move left vs rightHow to calculate mid safelyLoop conditions (low <= high vs low < high)You can solve 50+ interview problems easily.LeetCode 704 is the perfect starting point.Master this template, and you unlock an entire category of problems.

Binary SearchLeetCodeEasy

LeetCode 1365: How Many Numbers Are Smaller Than the Current Number | Java Solution, Intuition, Dry Run & Complexity Analysis

IntroductionIn this problem, we are given an integer array nums.For every element in the array, we must calculate how many numbers are smaller than the current number.The result should be stored in another array where:Each index contains the count of smaller numbersComparison must be done against every other elementWe cannot count the element itselfThis is a beginner-friendly array problem that teaches comparison logic and nested loop thinking.Problem StatementGiven the array nums, return an array answer such that:answer[i] = count of numbers smaller than nums[i]Question LinkProblem Link -: Leetcode 1365ExampleInputnums = [8,1,2,2,3]Output[4,0,1,1,3]Explanation8 → four smaller numbers → 1,2,2,31 → no smaller number2 → one smaller number → 12 → one smaller number → 13 → three smaller numbers → 1,2,2Understanding the ProblemWe need to check:For every element:How many values in the array are smaller than it?This means:Compare one number with all other numbersCount valid smaller valuesStore count in answer arrayIntuitionThe simplest idea is:Pick one numberCompare it with every elementCount smaller numbersSave resultRepeat for all indicesSince constraints are small:nums.length <= 500Brute force works perfectly.ApproachWe use two loops:Outer loop → selects current numberInner loop → compares with all numbersIf:nums[j] < nums[i]Then increase count.Java Solutionclass Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int i = 0; int j = 1; int ans[] = new int[nums.length]; int cou = 0; while(i < nums.length){ if(i != j && nums[i] > nums[j]){ cou++; } j++; if(j == nums.length){ ans[i] = cou; i++; cou = 0; j = 0; } } return ans; }}Code ExplanationVariablesiCurrent element index.jUsed for comparison.couStores count of smaller numbers.ans[]Final result array.Step-by-Step LogicStep 1Pick current number using:iStep 2Compare with every number using:jStep 3If another value is smaller:nums[i] > nums[j]Increase count.Step 4Store count.Step 5Move to next element.Dry RunInputnums = [8,1,2,2,3]First Element = 8Compare with:NumberSmaller?1Yes2Yes2Yes3YesCount = 4ans[0] = 4Second Element = 1No smaller number.ans[1] = 0Third Element = 2Smaller number:1Count = 1ans[2] = 1Final Answer[4,0,1,1,3]Time ComplexityWe compare every element with every other element.ComplexityO(N²)Because:Outer loop = NInner loop = NTotal:N × NSpace ComplexityWe only store output array.ComplexityO(N)Better Clean Version (Recommended)Your logic works, but interviewers usually prefer readable code.class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int n = nums.length; int[] ans = new int[n]; for(int i = 0; i < n; i++) { int count = 0; for(int j = 0; j < n; j++) { if(i != j && nums[j] < nums[i]) { count++; } } ans[i] = count; } return ans; }}Optimized ApproachSince:0 <= nums[i] <= 100We can use frequency counting.This gives:O(N + K)Where:N = array sizeK = range of valuesCommon Mistakes1. Comparing Same IndexWrong:nums[i] > nums[i]Correct:i != j2. Forgetting Reset CountWrong:count keeps increasingCorrect:count = 0after each iteration.3. Index Out Of BoundsAlways ensure:j < nums.lengthInterview TipsThis problem teaches:Nested loopsArray traversalCounting logicComparison problemsBrute force thinkingInterviewers may ask:Can you optimize it?Answer:Use counting sort or prefix frequency.FAQsIs this problem easy?Yes. It is beginner-friendly.Is brute force accepted?Yes.Constraints are small.Can we optimize?Yes.Using counting frequency array.Is this asked in interviews?Yes.Especially for beginners.Final ThoughtsLeetCode 1365 is a simple array problem that helps build strong fundamentals.You learn:How comparisons workHow nested loops solve counting problemsHow to convert logic into output arrays

LeetCodeEasyTwo PointerArrayJava

LeetCode 123 — Best Time to Buy and Sell Stock III | At Most Two Transactions Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you will learn much more that way.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/What Is the Problem Asking?You have a list of stock prices, one for each day. You are allowed to buy and sell the stock, but with one important restriction — you can make at most two transactions in total. A transaction means one buy followed by one sell.You cannot hold two stocks at the same time, meaning you must sell whatever you are holding before you buy again.Your job is to find the maximum profit you can make by doing at most two transactions. If there is no way to make any profit, return 0.Example to build intuition: prices = [3, 3, 5, 0, 0, 3, 1, 4]If you buy on day 4 (price 0) and sell on day 6 (price 3), profit = 3. Then buy on day 7 (price 1) and sell on day 8 (price 4), profit = 3. Total profit = 6. That is the best you can do.Constraints:1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁵Why Is This Harder Than the Previous Stock Problems?In LeetCode 121, you could only make one transaction — so you just found the best single buy-sell pair.In LeetCode 122, you could make unlimited transactions — so you greedily collected every upward price movement.Here, you are limited to exactly two transactions. Greedy does not work anymore because sometimes skipping a small profit early on allows you to make a much bigger combined profit across two trades. You need a smarter strategy.The Big Idea Behind the SolutionHere is a simple way to think about it.If you are allowed two transactions, you can imagine drawing a dividing line somewhere in the price array. The first transaction happens entirely on the left side of that line. The second transaction happens entirely on the right side.So the problem becomes:For every possible dividing position, find the best profit on the left side and the best profit on the right side.Add them together.The maximum sum across all dividing positions is your answer.The challenge is doing this efficiently without checking every position with a nested loop, which would be O(N²) and too slow.Approach 1 — Left-Right Prefix DPThe idea:Instead of trying every split point from scratch, precompute the answers in advance.Build a leftProfit array where leftProfit[i] stores the best single transaction profit you can make using prices from day 0 to day i.Build a rightProfit array where rightProfit[i] stores the best single transaction profit you can make using prices from day i to the last day.Then for every index i, the answer if you split at i is simply leftProfit[i] + rightProfit[i]. Take the maximum across all indices.How to build leftProfit:Go left to right. Keep track of the minimum price seen so far. At each day i, the best profit you could make ending at or before day i is either the same as the day before, or selling today at today's price minus the minimum price seen so far. Take whichever is larger.How to build rightProfit:Go right to left. Keep track of the maximum price seen so far from the right. At each day i, the best profit you could make starting at or after day i is either the same as the day after, or buying today at today's price and selling at the maximum price seen to the right. Take whichever is larger.Dry Run — prices = [3, 3, 5, 0, 0, 3, 1, 4]Building leftProfit left to right, tracking minimum price seen:Day 0 → min=3, leftProfit[0] = 0 (nothing to compare yet) Day 1 → min=3, best profit = 3-3 = 0, leftProfit[1] = max(0, 0) = 0 Day 2 → min=3, best profit = 5-3 = 2, leftProfit[2] = max(0, 2) = 2 Day 3 → min=0, best profit = 0-0 = 0, leftProfit[3] = max(2, 0) = 2 Day 4 → min=0, best profit = 0-0 = 0, leftProfit[4] = max(2, 0) = 2 Day 5 → min=0, best profit = 3-0 = 3, leftProfit[5] = max(2, 3) = 3 Day 6 → min=0, best profit = 1-0 = 1, leftProfit[6] = max(3, 1) = 3 Day 7 → min=0, best profit = 4-0 = 4, leftProfit[7] = max(3, 4) = 4leftProfit = [0, 0, 2, 2, 2, 3, 3, 4]Building rightProfit right to left, tracking maximum price seen:Day 7 → max=4, rightProfit[7] = 0 (nothing to compare yet) Day 6 → max=4, best profit = 4-1 = 3, rightProfit[6] = max(0, 3) = 3 Day 5 → max=4, best profit = 4-3 = 1, rightProfit[5] = max(3, 1) = 3 Day 4 → max=4, best profit = 4-0 = 4, rightProfit[4] = max(3, 4) = 4 Day 3 → max=4, best profit = 4-0 = 4, rightProfit[3] = max(4, 4) = 4 Day 2 → max=5, best profit = 5-5 = 0, rightProfit[2] = max(4, 0) = 4 Day 1 → max=5, best profit = 5-3 = 2, rightProfit[1] = max(4, 2) = 4 Day 0 → max=5, best profit = 5-3 = 2, rightProfit[0] = max(4, 2) = 4rightProfit = [4, 4, 4, 4, 4, 3, 3, 0]Combining at each index: Index 0 → 0 + 4 = 4 Index 1 → 0 + 4 = 4 Index 2 → 2 + 4 = 6 Index 3 → 2 + 4 = 6 Index 4 → 2 + 4 = 6 Index 5 → 3 + 3 = 6 Index 6 → 3 + 3 = 6 Index 7 → 4 + 0 = 4Maximum = 6 ✅Implementation code:class Solution { public int maxProfit(int[] prices) { int lefProf[] = new int[prices.length]; int rigProf[] = new int[prices.length]; int j = 1; int i = 0; int coL = 1; while (i < j && j < prices.length) { if (prices[i] > prices[j]) { i = j; if (coL - 1 != -1) { lefProf[coL] = lefProf[coL - 1]; } coL++; } else { int max = prices[j] - prices[i]; if (coL - 1 != -1) { lefProf[coL] = Math.max(lefProf[coL - 1], max); coL++; } else { lefProf[coL] = max; coL++; } } j++; } int ii = prices.length - 2; int jj = prices.length - 1; int coR = prices.length - 2; while (ii >= 0) { if (prices[ii] > prices[jj]) { jj = ii; if (coR + 1 < prices.length) { rigProf[coR] = rigProf[coR + 1]; } coR--; } else { int max = prices[jj] - prices[ii]; if (coR + 1 < prices.length) { rigProf[coR] = Math.max(rigProf[coR + 1], max); coR--; } else { rigProf[coR] = max; coR--; } } ii--; } int maxAns = 0; for (int k = 0; k < lefProf.length; k++) { maxAns = Math.max(maxAns, lefProf[k] + rigProf[k]); } return maxAns; }}The approach here is exactly right. You are building the left and right profit arrays using a two pointer scanning technique — the same idea as LeetCode 121 but applied twice, once going forward and once going backward. The manual counters coL and coR make it a bit harder to follow, but the logic underneath is solid.Here is the same approach written in a cleaner way so it is easier to read and debug:class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] leftProfit = new int[n]; int[] rightProfit = new int[n]; int minPrice = prices[0]; for (int i = 1; i < n; i++) { minPrice = Math.min(minPrice, prices[i]); leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice); } int maxPrice = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { maxPrice = Math.max(maxPrice, prices[i]); rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]); } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, leftProfit[i] + rightProfit[i]); } return maxProfit; }}Time Complexity: O(N) — three separate linear passes through the array. Space Complexity: O(N) — two extra arrays of size N.Approach 2 — Four Variable State Machine DPThe idea:Instead of building arrays, what if you could track everything in just four variables and solve it in a single pass?Think about what is happening at any point in time as you go through the prices. You are always in one of these situations:You have bought your first stock and are currently holding it. You have sold your first stock and are sitting on that profit. You have bought your second stock (using the profit from the first sale) and are holding it. You have sold your second stock and collected your total profit.These four situations are your four states. For each one, you always want to know — what is the best possible profit I could have in this state up to today?Here is how each state updates as you look at a new price:buy1 — This represents the best outcome after buying the first stock. Buying costs money, so this is negative. As you see each new price, you ask: is it better to have bought on some earlier day, or to buy today? You keep whichever gives you the least cost, which means the highest value of negative price.sell1 — This represents the best profit after completing the first transaction. As you see each new price, you ask: is it better to have sold on some earlier day, or to sell today using the best buy1 we have? Selling today means adding today's price on top of buy1.buy2 — This represents the best outcome after buying the second stock. The key insight here is that you are not starting from zero — you already have the profit from the first transaction in your pocket. So buying the second stock costs today's price but you subtract it from sell1. As you see each new price, you ask: is it better to have bought the second stock earlier, or to buy today using the profit from sell1?sell2 — This is your final answer. It represents the best total profit after completing both transactions. As you see each new price, you ask: is it better to have completed both transactions earlier, or to sell the second stock today using the best buy2 we have?The beautiful thing is that all four updates happen in order on every single day, in one pass through the array. Each variable feeds into the next — buy1 feeds sell1, sell1 feeds buy2, buy2 feeds sell2.Dry Run — prices = [3, 3, 5, 0, 0, 3, 1, 4]We start with buy1 and buy2 as very negative (not yet bought anything) and sell1 and sell2 as 0 (no profit yet).Day 0, price = 3: buy1 = max(-∞, -3) = -3. Best cost to buy first stock is spending 3. sell1 = max(0, -3+3) = 0. Selling immediately gives no profit. buy2 = max(-∞, 0-3) = -3. Best cost to buy second stock after first sale is 3. sell2 = max(0, -3+3) = 0. No total profit yet.Day 1, price = 3: Nothing changes — same price as day 0.Day 2, price = 5: buy1 = max(-3, -5) = -3. Still best to have bought at price 3. sell1 = max(0, -3+5) = 2. Selling today at 5 after buying at 3 gives profit 2. buy2 = max(-3, 2-5) = -3. Buying second stock today costs too much relative to first profit. sell2 = max(0, -3+5) = 2. Completing both trades gives 2 so far.Day 3, price = 0: buy1 = max(-3, -0) = 0. Buying today at price 0 is the best possible first buy. sell1 = max(2, 0+0) = 2. Selling today at 0 gives nothing — keep the 2 from before. buy2 = max(-3, 2-0) = 2. Using the profit of 2 and buying today at 0 gives buy2 = 2. sell2 = max(2, 2+0) = 2. Selling second stock today at 0 gives nothing extra.Day 4, price = 0: Nothing changes — same price as day 3.Day 5, price = 3: buy1 = max(0, -3) = 0. Still best to have bought at price 0. sell1 = max(2, 0+3) = 3. Selling today at 3 after buying at 0 gives profit 3. buy2 = max(2, 3-3) = 2. Buying second stock today at 3 using sell1=3 gives 0. Keep 2. sell2 = max(2, 2+3) = 5. Selling second stock today at 3 after buy2=2 gives total 5.Day 6, price = 1: buy1 = max(0, -1) = 0. Still best to have bought at 0. sell1 = max(3, 0+1) = 3. Selling today at 1 gives less than 3 — no change. buy2 = max(2, 3-1) = 2. Buying second stock at 1 using sell1=3 gives 2 — same as before. sell2 = max(5, 2+1) = 5. No improvement yet.Day 7, price = 4: buy1 = max(0, -4) = 0. No change. sell1 = max(3, 0+4) = 4. Selling today at 4 after buying at 0 gives profit 4 — new best. buy2 = max(2, 4-4) = 2. No improvement. sell2 = max(5, 2+4) = 6. Selling second stock today at 4 with buy2=2 gives total 6 — new best.Output: 6 ✅class Solution { public int maxProfit(int[] prices) { int buy1 = Integer.MIN_VALUE; int sell1 = 0; int buy2 = Integer.MIN_VALUE; int sell2 = 0; for (int price : prices) { buy1 = Math.max(buy1, -price); sell1 = Math.max(sell1, buy1 + price); buy2 = Math.max(buy2, sell1 - price); sell2 = Math.max(sell2, buy2 + price); } return sell2; }}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — only four integer variables, no extra arrays.Approach 3 — Generalizing to At Most K TransactionsOnce you understand Approach 2, there is a natural question — what if instead of two transactions, you were allowed K transactions? That is exactly LeetCode 188.Instead of four hardcoded variables, you use two arrays of size K. buy[j] tracks the best outcome after the j-th buy and sell[j] tracks the best outcome after the j-th sell. The logic is identical to Approach 2, just in a loop.For this problem set K = 2 and it gives the same answer:class Solution { public int maxProfit(int[] prices) { int k = 2; int[] buy = new int[k]; int[] sell = new int[k]; Arrays.fill(buy, Integer.MIN_VALUE); for (int price : prices) { for (int j = 0; j < k; j++) { buy[j] = Math.max(buy[j], (j == 0 ? 0 : sell[j - 1]) - price); sell[j] = Math.max(sell[j], buy[j] + price); } } return sell[k - 1]; }}Time Complexity: O(N × K) — for K=2 this is effectively O(N). Space Complexity: O(K) — two small arrays of size K.If you understand this, LeetCode 188 becomes a five minute problem.Comparing All Three ApproachesApproach 1 — Left-Right Prefix DP (Your Approach)You build two arrays — one scanning left to right, one scanning right to left — and combine them. This is the most visual and intuitive approach. It is easy to explain because you are essentially solving LeetCode 121 twice from opposite ends and adding the results. The downside is it uses O(N) extra space for the two arrays.Approach 2 — Four Variable State MachineYou solve the entire problem in a single pass using just four variables. No arrays, no extra memory. This is the most efficient and elegant solution. Once you understand what each variable represents, the code almost writes itself. This is what most interviewers are hoping to see.Approach 3 — General K-Transaction DPThis is Approach 2 extended to handle any number of transactions using arrays instead of hardcoded variables. Solving LeetCode 123 with this approach means you have already solved LeetCode 188 as a bonus.Mistakes That Catch Most PeopleTrying to use the greedy approach from LeetCode 122: Adding every upward price movement does not work when you are limited to two transactions. You need to pick the two best non-overlapping windows, not collect everything.Buying twice without selling in between: The state machine prevents this naturally — buy2 depends on sell1, so you can never enter the second buy before completing the first sell.Initializing buy variables to 0: Both buy1 and buy2 must start at Integer.MIN_VALUE. Setting them to 0 implies you bought a stock for free, which is wrong and will give inflated profits.Returning the wrong variable: Always return sell2, not buy2 or sell1. sell2 is the only variable that represents a completed two-transaction profit.Where This Fits in the Stock SeriesLeetCode 121 — One transaction only. Find the single best buy-sell pair. [ Blog is also avaliable on this - Read Now ]LeetCode 122 — Unlimited transactions. Collect every upward price movement greedily. [ Blog is also avaliable on this - Read Now ]LeetCode 188 — At most K transactions. Direct extension of Approach 3 above.LeetCode 309 — Unlimited transactions but with a cooldown day after every sale.LeetCode 714 — Unlimited transactions but with a fee charged on every transaction.Each problem adds one new constraint on top of the previous one. If you understand LeetCode 123 deeply — especially Approach 2 — every other problem in this series becomes a small modification of the same framework.Key Takeaways✅ When you are limited to two transactions, greedy fails. You need to find two non-overlapping windows that together give maximum profit.✅ The left-right prefix DP approach is the most intuitive — precompute the best single transaction from both ends, then combine at every split point.✅ The four variable state machine solves it in one pass with O(1) space. Each variable tracks the best outcome for one state — buy1 feeds sell1, sell1 feeds buy2, buy2 feeds sell2.✅ Always initialize buy variables to Integer.MIN_VALUE to represent "not yet bought anything."✅ Understanding Approach 3 here means LeetCode 188 is already solved — just change the hardcoded 2 to K.Happy Coding! This problem is the turning point in the stock series where DP becomes unavoidable — once you crack it, the rest of the series feels manageable. 🚀

LeetCodeDynamic ProgrammingHardJavaDSAPrefix DPArraysStock Series

Sort Colors

LeetCode Problem 75 Link of the Problem to try -: LinkProblem Statement :- Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.Example 1:Input: nums = [2,0,2,1,1,0]Output: [0,0,1,1,2,2]Example 2:Input: nums = [2,0,1]Output: [0,1,2]You must solve this problem without using the library's sort function.My Approach (1)I have solved this question via my approach by counting frequency of each element like 0,1 and 2 as I avoid to use nested loops but i used for loops multiple times but as loops are used in a constant space of time that's why they did not increases the time complexity that's why my solution time complexity is O(n) even though I need to traverse array multiple time.Here is the Approach:int zeroCounter= 0;int oneCounter = 0;int twoCounter=0;int counter =0;for(int i =0; i< nums.length; i++){if(nums[i] == 0){zeroCounter++;}else if(nums[i] == 1){oneCounter++;}else{twoCounter++;}}for(int i=0; i<zeroCounter;i++){nums[i] = 0;counter++;}for(int i=0; i<oneCounter;i++){nums[counter] = 1;counter++;}for(int i=0; i<twoCounter;i++){nums[counter] = 2;counter++;}My Approach (2)This approach uses a algorithm called DNF (Dutch National Flag) Algorithm in this algorithm we have to focus on two elements out of three and make sure those two element are on the correct place as the last one came automatically to the correct position even though my approach(1) is uses loops multiple time but this approach is also take O(n) time complexity but uses loop one time that's why this approach is far cleaner than approach (1).int low =0;int high= nums.length-1;int curr =0;while(curr <= high){if(nums[curr] == 0){int temp = nums[low];nums[low] = nums[curr];nums[curr] = temp;low++;curr++;}else if( nums[curr] == 1){curr++;}else{int temp = nums[curr];nums[curr] = nums[high];nums[high] = temp;high--;}}

LeetCodeMediumTwo PointerDutchman Flag Algorithm

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