Search Blogs

Showing results for "Intersection"

Found 5 results

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

Intersection of Two Arrays

LeetCode Problem 349Link of the Problem to try -: LinkGiven two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order. Example 1:Input: nums1 = [1,2,2,1], nums2 = [2,2]Output: [2]Example 2:Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output: [9,4]Explanation: [4,9] is also accepted. Constraints:1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000Solution: Using HashMap and HashSet for IntersectionCore Objective: The primary goal of this problem is to identify common elements between two arrays and return them as a unique set. To achieve this efficiently, we utilize a combination of a HashMap for quick lookup and a HashSet to handle uniqueness in the result.Logic & Implementation:Populate Lookup Table: We begin by iterating through the first array (nums1) and storing its elements in a HashMap. This allows us to verify the existence of any number in $O(1)$ average time.Identify Intersection: Next, we iterate through the second array (nums2). For each element, we check if it exists within our HashMap.Handle Uniqueness: If a match is found, we add the element to a HashSet. This is a crucial step because the problem requires the output to contain unique elements, even if a common number appears multiple times in the input arrays.Final Conversion: Since the required return type is an array, we determine the size of our HashSet to initialize the result array. Using a for-each loop, we transfer the values from the Set into the array and return it as the final answer.Code Implementation:public int[] intersection(int[] nums1, int[] nums2) { // HashMap to store elements from the first array for lookup HashMap<Integer, Integer> mp = new HashMap<>(); // HashSet to store unique common elements HashSet<Integer> ms = new HashSet<>(); // Populate the map with elements from nums1 for (int i = 0; i < nums1.length; i++) { if (mp.containsKey(nums1[i])) { continue; } mp.put(nums1[i], i); } // Check for common elements in nums2 for (int i = 0; i < nums2.length; i++) { if (mp.containsKey(nums2[i])) { ms.add(nums2[i]); // HashSet ensures duplicates are not added } } // Convert the HashSet to the final integer array int[] ans = new int[ms.size()]; int co = 0; for (int i : ms) { ans[co] = i; co++; } return ans;}

LeetCodeArrayEasyHashMap

Intersection of Two Arrays II

LeetCode Problem 350Link of the Problem to try -: LinkGiven two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order. Example 1:Input: nums1 = [1,2,2,1], nums2 = [2,2]Output: [2,2]Example 2:Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output: [4,9]Explanation: [9,4] is also accepted. Constraints:1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000Solution:In this question we can build a frequency HashMap of each element and then add into the array as per it's frequency is that is a very important thing in this question to do.For creating frequency we will use getOrDefault() method in HashMap that is very useful for creating frequency as this method returns the value of that key if that key is not exist then whatever value we give that value is considered as default value for us.So, back to question here we simply create a map creating frequency of each element and if the element came again we simply increase the frequency of it then we create a ArrayList because we don't know about the size of array here so we use ArrayList after this we will iterate again on the second array and try to find that element in the map also we check it's frequency should be more than 0 and we add in the List also we decreasing the frequency of the element in the loop.At last we simply take all the elements of ArrayList and put into a array of size of that ArrayList because our questions want's ans in array that's why we have to do this step otherwise our ans is in the ArrayList and this is how we find duplicates of the number of times that element appears in both array.Code: public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { // If you are not interested in writing getOrDefault then you can write via if statement as well // int cou =1; // if(mp.containsKey(nums1[i])){ // // int nu = mp.get(nums1[i]); // mp.put(nums1[i],mp.get(nums1[i])+1); // continue; // } // mp.put(nums1[i],cou); // Another way mp.put(nums1[i], mp.getOrDefault(nums1[i], 0) + 1); } List<Integer> lis = new ArrayList<>(); for (int i = 0; i < nums2.length; i++) { if (mp.containsKey(nums2[i]) && mp.get(nums2[i]) > 0) { lis.add(nums2[i]); } mp.put(nums2[i], mp.getOrDefault(nums2[i], 0) - 1); } int[] ans = new int[lis.size()]; for (int i = 0; i < ans.length; i++) { ans[i] = lis.get(i); } return ans; }

LeetcodeEasyHashMapHashSet

LeetCode 402: Remove K Digits — Java Solution Explained

IntroductionLeetCode 402 Remove K Digits is one of those problems where the brute force solution feels obvious but completely falls apart at scale — and the optimal solution requires a genuinely clever insight that, once you see it, feels like magic.This problem sits at the intersection of two powerful techniques — Greedy thinking and Monotonic Stack. If you have already solved Next Greater Element and Asteroid Collision, you have all the building blocks you need. This is where those patterns level up.You can find the problem here — LeetCode 402 Remove K Digits.What Is the Problem Really Asking?You are given a number as a string and an integer k. Remove exactly k digits from the number such that the resulting number is as small as possible. Return it as a string without leading zeros.Example:num = "1432219", k = 3We want to remove 3 digits to make the number as small as possibleRemove 4, 3, 2 → remaining is "1219"Output: "1219"Simple goal — smallest possible number after exactly k removals.Real Life Analogy — Choosing the Best Price TagImagine you are reading a price tag digit by digit from left to right. Every time you see a digit that is bigger than the next one coming, you have a chance to remove it and make the price smaller. You have a limited number of removals — use them wisely on the biggest offenders from the left side, because leftmost digits have the most impact on the overall value.Removing a 9 from the front of a number shrinks it far more than removing a 9 from the end. This left-to-right priority with greedy removal is the entire insight of this problem.The Core Greedy InsightHere is the key question — which digit should we remove first to make the number as small as possible?Think about it this way. In the number "1432219", which digit is hurting us the most? It is 4 — because it is large and sits early in the number. After removing 4 we get "132219". Now 3 is the biggest early offender. And so on.More precisely — whenever you see a digit that is greater than the digit immediately after it, removing it makes the number smaller. This is because a larger digit sitting before a smaller digit inflates the overall value.This is the Greedy rule: scan left to right, and whenever the current digit on the stack is greater than the incoming digit, remove it (if we still have removals left).A Monotonic Increasing Stack enforces exactly this — it keeps digits in non-decreasing order, automatically kicking out any digit that is larger than what comes next.The Solution — Monotonic Stackpublic String removeKdigits(String num, int k) { Stack<Character> st = new Stack<>(); // build monotonic increasing stack for (int i = 0; i < num.length(); i++) { // while stack top is greater than current digit and we still have removals while (!st.empty() && k != 0 && st.peek() > num.charAt(i)) { st.pop(); // remove the larger digit — greedy choice k--; } st.push(num.charAt(i)); } // if k removals still remaining, remove from the end (largest digits are at top) while (k != 0) { st.pop(); k--; } // build result string from stack StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } sb.reverse(); // stack gives reverse order // remove leading zeros while (sb.length() > 0 && sb.charAt(0) == '0') { sb.deleteCharAt(0); } // if nothing left, return "0" return sb.length() == 0 ? "0" : sb.toString();}Step-by-Step Dry Run — num = "1432219", k = 3Processing 1: Stack empty → push. Stack: [1]Processing 4: Stack top 1 < 4 → no pop. Push 4. Stack: [1, 4]Processing 3: Stack top 4 > 3 and k=3 → pop 4, k=2. Stack: [1] Stack top 1 < 3 → stop. Push 3. Stack: [1, 3]Processing 2: Stack top 3 > 2 and k=2 → pop 3, k=1. Stack: [1] Stack top 1 < 2 → stop. Push 2. Stack: [1, 2]Processing 2: Stack top 2 == 2 → not greater, stop. Push 2. Stack: [1, 2, 2]Processing 1: Stack top 2 > 1 and k=1 → pop 2, k=0. Stack: [1, 2] k=0, stop. Push 1. Stack: [1, 2, 1]Processing 9: k=0, no more removals. Push 9. Stack: [1, 2, 1, 9]k is now 0, skip the cleanup loop.Build result: pop all → "9121" → reverse → "1219" No leading zeros. Return "1219" ✅Step-by-Step Dry Run — num = "10200", k = 1Processing 1: stack empty → push. Stack: [1]Processing 0: Stack top 1 > 0 and k=1 → pop 1, k=0. Stack: [] Push 0. Stack: [0]Processing 2: k=0, no removals. Push. Stack: [0, 2]Processing 0: k=0. Push. Stack: [0, 2, 0]Processing 0: k=0. Push. Stack: [0, 2, 0, 0]k=0, skip cleanup.Build result: "0020" → reverse → "0200" Remove leading zero → "200" Return "200" ✅Step-by-Step Dry Run — num = "10", k = 2Processing 1: push. Stack: [1]Processing 0: Stack top 1 > 0 and k=2 → pop 1, k=1. Stack: [] Push 0. Stack: [0]k=1 remaining → cleanup loop → pop 0, k=0. Stack: []Build result: empty string. Remove leading zeros: nothing to remove. Length is 0 → return "0" ✅The Three Tricky Cases You Must HandleCase 1 — k is not fully used after the loop This happens with a non-decreasing number like "12345" with k=2. No element ever gets popped during the loop because no digit is greater than the next one. The stack ends up as [1,2,3,4,5] with k still = 2. The solution is to pop from the top of the stack — which holds the largest digits — until k hits 0.Case 2 — Leading zeros After removing digits, the remaining number might start with zeros. "10200" becomes "0200" after removing 1. We strip leading zeros with a while loop. But we must be careful not to strip the only zero — that is why we check length > 0 before each removal.Case 3 — Empty result If all digits are removed (like "10" with k=2), the StringBuilder ends up empty. We return "0" because an empty number is represented as zero.Why Remaining k Gets Removed From the EndAfter the main loop, if k is still greater than 0, why do we remove from the top of the stack (which corresponds to the end of the number)?Because the stack at this point holds a non-decreasing sequence. In a non-decreasing sequence, the largest values are at the end. Removing from the end removes the largest remaining digits — which is exactly the greedy choice to minimize the number.For example in "12345" with k=2: the stack is [1,2,3,4,5]. Pop top twice → remove 5 and 4 → [1,2,3] → result is "123". Correct!Time and Space ComplexityTime Complexity: O(n) — each digit is pushed onto the stack exactly once and popped at most once. Even with the while loop inside the for loop, total push and pop operations across the entire run never exceed 2n. The leading zero removal is also O(n) in the worst case. Overall stays linear.Space Complexity: O(n) — the stack holds at most n digits in the worst case when no removals happen during the main loop.Common Mistakes to AvoidNot handling remaining k after the loop This is the most common mistake. If the number is already non-decreasing, the loop never pops anything. Forgetting the cleanup loop gives the wrong answer for inputs like "12345" with k=2.Not removing leading zeros After removals, the result might start with zeros. "0200" should be returned as "200". Skipping this step gives wrong output.Returning empty string instead of "0" When all digits are removed, return "0" not "". An empty string is not a valid number representation.Using >= instead of > in the pop condition If you pop on equal digits too, you remove more than necessary and might get wrong results. Only pop when strictly greater — equal digits in sequence are fine to keep.How This Connects to the Monotonic Stack SeriesLooking at the stack problems you have been solving:496 Next Greater Element — monotonic decreasing stack, find first bigger to the right 735 Asteroid Collision — stack simulation, chain reactions 402 Remove K Digits — monotonic increasing stack, greedy removal for minimum numberThe direction of the monotonic stack flips based on what you are optimizing. For "next greater" you keep a decreasing stack. For "smallest number" you keep an increasing stack. Recognizing which direction to go is the skill that connects all these problems.FAQs — People Also AskQ1. Why does a Monotonic Stack give the smallest number in LeetCode 402? A monotonic increasing stack ensures that at every point, the digits we have kept so far are in the smallest possible order. Whenever a smaller digit arrives and the stack top is larger, removing that larger digit can only make the number smaller — this greedy choice is always optimal.Q2. What happens if k is not fully used after the main loop in LeetCode 402? The number is already in non-decreasing order so no removals happened during the loop. The remaining removals should be made from the end of the number (top of stack) since those are the largest values in a non-decreasing sequence.Q3. How are leading zeros handled in LeetCode 402? After building the result string, strip any leading zeros with a while loop. If stripping leaves an empty string, return "0" because the empty case represents zero.Q4. What is the time complexity of LeetCode 402? O(n) time because each digit is pushed and popped at most once across the entire algorithm. Space complexity is O(n) for the stack.Q5. Is LeetCode 402 asked in coding interviews? Yes, it is frequently asked at companies like Google, Amazon, and Microsoft. It tests greedy thinking combined with monotonic stack — two patterns that interviewers love because they require genuine insight rather than memorization.Similar LeetCode Problems to Practice Next496. Next Greater Element I — Easy — monotonic decreasing stack739. Daily Temperatures — Medium — next greater with distances316. Remove Duplicate Letters — Medium — similar greedy stack with constraints1081. Smallest Subsequence of Distinct Characters — Medium — same approach as 31684. Largest Rectangle in Histogram — Hard — advanced monotonic stackConclusionLeetCode 402 Remove K Digits is a beautiful problem that rewards clear thinking. The greedy insight — always remove a digit when a smaller digit comes after it — naturally leads to the monotonic stack solution. The three edge cases (remaining k, leading zeros, empty result) are what separate a buggy solution from a clean, accepted one.Work through all three dry runs carefully. Once you see how the stack stays increasing and how each pop directly corresponds to a greedy removal decision, this pattern will click permanently and carry you through harder stack problems ahead.

LeetCodeJavaStackMonotonic StackGreedyStringMedium

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