Search Blogs

Showing results for "hashmap"

Found 30 results

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/word-pattern/Problem DescriptionYou are given:A string patternA string sThe string s consists of words separated by spaces.Your task is to determine whether s follows the same pattern defined by the string pattern.To follow the pattern, there must be a bijection between pattern characters and words.Understanding the Meaning of BijectionA bijection means a one-to-one relationship between two sets.For this problem it means:Every character in the pattern maps to exactly one word.Every word maps to exactly one pattern character.Two characters cannot map to the same word.Two words cannot map to the same character.This ensures the mapping is unique in both directions.Example WalkthroughExample 1Inputpattern = "abba"s = "dog cat cat dog"OutputtrueExplanationMapping:a → dogb → catPattern:a b b aWords:dog cat cat dogThe mapping is perfectly consistent.Example 2Inputpattern = "abba"s = "dog cat cat fish"OutputfalseExplanationThe last word "fish" breaks the pattern because "a" was already mapped to "dog".Example 3Inputpattern = "aaaa"s = "dog cat cat dog"OutputfalseExplanationPattern requires:a → same word every timeBut the words differ.Constraints1 <= pattern.length <= 300pattern contains lowercase English letters1 <= s.length <= 3000s contains lowercase letters and spaceswords are separated by a single spaceno leading or trailing spacesCore ObservationBefore applying any algorithm, we should verify one simple condition.If the number of pattern characters does not match the number of words, then the pattern cannot match.Example:pattern = "abba"s = "dog cat dog"Pattern length = 4Words = 3This automatically returns false.Thinking About Possible ApproachesWhile solving this problem, several strategies may come to mind:Use one HashMap to store pattern → word mapping and check duplicates manually.Use two HashMaps to enforce bijection from both directions.Track first occurrence indices of pattern characters and words.Compare mapping patterns using arrays or maps.Let’s explore these approaches one by one.Approach 1: Single HashMap (Your Solution)IdeaWe store mapping:pattern character → wordWhile iterating:If the character already exists in the map→ check if it maps to the same word.If it does not exist→ ensure that no other character already maps to that word.This ensures bijection.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String words[] = s.split(" "); // Length mismatch means impossible mapping if(pattern.length() != words.length) return false; HashMap<Character,String> mp = new HashMap<>(); for(int i = 0; i < words.length; i++){ char ch = pattern.charAt(i); if(mp.containsKey(ch)){ if(!mp.get(ch).equals(words[i])){ return false; } }else{ // Prevent two characters mapping to same word if(mp.containsValue(words[i])){ return false; } } mp.put(ch, words[i]); } return true; }}Time ComplexityO(n²)Because containsValue() can take O(n) time in worst case.Space ComplexityO(n)Approach 2: Two HashMaps (Cleaner Bijection Enforcement)IdeaInstead of checking containsValue, we maintain two maps.pattern → wordword → patternThis ensures bijection naturally.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) return false; HashMap<Character, String> map1 = new HashMap<>(); HashMap<String, Character> map2 = new HashMap<>(); for(int i = 0; i < pattern.length(); i++){ char ch = pattern.charAt(i); String word = words[i]; if(map1.containsKey(ch) && !map1.get(ch).equals(word)) return false; if(map2.containsKey(word) && map2.get(word) != ch) return false; map1.put(ch, word); map2.put(word, ch); } return true; }}Time ComplexityO(n)Because both maps allow constant-time lookups.Space ComplexityO(n)Approach 3: Index Mapping Technique (Elegant Trick)IdeaAnother clever technique is to compare first occurrence indices.Example:pattern = abbawords = dog cat cat dogPattern index sequence:a → 0b → 1b → 1a → 0Words index sequence:dog → 0cat → 1cat → 1dog → 0If the index sequences match, then the pattern holds.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) return false; HashMap<Character,Integer> map1 = new HashMap<>(); HashMap<String,Integer> map2 = new HashMap<>(); for(int i = 0; i < pattern.length(); i++){ char ch = pattern.charAt(i); String word = words[i]; if(!map1.getOrDefault(ch, -1) .equals(map2.getOrDefault(word, -1))){ return false; } map1.put(ch, i); map2.put(word, i); } return true; }}Time ComplexityO(n)Space ComplexityO(n)Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesSingle HashMapO(n²)O(n)Simple but slowerTwo HashMapsO(n)O(n)Cleaner bijection enforcementIndex MappingO(n)O(n)Elegant and interview-friendlyKey Interview InsightProblems like this test your understanding of:Bijection MappingSimilar problems include:Isomorphic StringsWord Pattern IISubstitution Cipher ProblemsUnderstanding how to enforce one-to-one mappings is a powerful technique.ConclusionThe Word Pattern problem is an excellent example of how HashMaps can enforce relationships between two datasets.While a simple HashMap solution works, more optimized methods like two-way mapping or index comparison provide cleaner and more efficient implementations.Mastering these techniques will help you solve many pattern-matching and mapping problems commonly asked in coding interviews.

HashMapString ManipulationBijection MappingTwo HashMapsIndex MappingLeetCode Easy

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

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

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

🔗 Problem LinkLeetCode 1941 – Check if All Characters Have Equal Number of Occurrences 👉 https://leetcode.com/problems/check-if-all-characters-have-equal-number-of-occurrences/IntroductionThis is one of those problems that looks very simple at first glance — and it actually is — but it helps strengthen your understanding of frequency counting using HashMap.The problem asks us to determine whether all characters in a string occur the same number of times.No sliding window. No binary search. Just clean frequency logic.But even simple problems help build strong foundations.📌 Problem UnderstandingA string is considered "good" if:Every character that appears in the stringAppears the same number of timesIf even one character has a different frequency → return false.Example 1Input: s = "abacbc"Output: trueCharacter counts:a → 2b → 2c → 2All equal → ✔ trueExample 2Input: s = "aaabb"Output: falseCharacter counts:a → 3b → 2Not equal → ✘ false🧠 Approach & IntuitionWhen I saw this problem, my thinking was:Count the frequency of every character.Compare all frequencies.If all are equal → return true.The important part is choosing a reference frequency and comparing everything against it.💻 Your Codeclass Solution { public boolean areOccurrencesEqual(String s) { HashMap<Character,Integer> mp = new HashMap<>(); int ref =0; char c = s.charAt(0); for(int i =0 ; i< s.length();i++){ if(c == s.charAt(i)){ ref++; } mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } for(int a:mp.values()){ if(ref != a){ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Initialize HashMapHashMap<Character,Integer> mp = new HashMap<>();This stores frequency of each character.2️⃣ Choose Reference Characterchar c = s.charAt(0);int ref = 0;You use the first character as a reference.Then count how many times it appears while also building the frequency map.3️⃣ Build Frequency Mapmp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);This line increases count for each character.4️⃣ Compare Frequenciesfor(int a : mp.values()){ if(ref != a){ return false; }}If any frequency differs from the reference count → return false.Otherwise → true.⏱ Time and Space ComplexityTime Complexity: O(n)One loop to count frequenciesOne loop over at most 26 charactersSpace Complexity: O(26) ≈ O(1)Only lowercase English letters are allowed.🔥 Small Optimization IdeaYour solution works perfectly.However, we can simplify it slightly:Instead of separately counting the reference frequency, we can:First build the entire frequency map.Take the frequency of the first character from the map.Compare all values with it.Cleaner Versionclass Solution { public boolean areOccurrencesEqual(String s) { HashMap<Character,Integer> mp = new HashMap<>(); for(char ch : s.toCharArray()){ mp.put(ch, mp.getOrDefault(ch, 0) + 1); } int ref = mp.get(s.charAt(0)); for(int freq : mp.values()){ if(freq != ref){ return false; } } return true; }}Same logic — slightly cleaner structure.🎯 Key Learning from This ProblemThis problem reinforces:Frequency counting using HashMapUsing a reference value for comparisonClean loop logicEarly return for optimizationEven though it is an easy problem, it builds the base for harder problems like:Valid AnagramGroup AnagramsFirst Unique CharacterRansom Note🏁 Final ThoughtsProblems like this are not about complexity.They are about:Writing clean logicHandling frequency maps properlyThinking clearly about conditionsMastering easy problems makes medium and hard problems much easier later.

HashMapStringFrequency CountLeetCodeEasy

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 3761 Minimum Absolute Distance Between Mirror Pairs | Java HashMap Solution

IntroductionSome problems look simple at first—but hide a clever trick inside.LeetCode 3761 – Minimum Absolute Distance Between Mirror Pairs is one such problem. It combines:Number manipulation (digit reversal)HashingEfficient searchingIf approached naively, this problem can easily lead to O(n²) time complexity—which is not feasible for large inputs.In this article, we will walk through:Problem intuitionNaive approach (and why it fails)Optimized HashMap solutionStep-by-step explanationClean Java code with comments🔗 Problem LinkLeetCode: Minimum Absolute Distance Between Mirror PairsTo gain a deeper understanding of the problem, it is highly recommended that you review this similar problem Closest Equal Element Queries here is the link of the article. Both cases follow a nearly identical pattern, and studying the initial example will provide valuable context for the current task.Problem StatementYou are given an integer array nums.A mirror pair (i, j) satisfies:0 ≤ i < j < nums.lengthreverse(nums[i]) == nums[j]👉 Your task is to find:The minimum absolute distance between such pairsIf no mirror pair exists, return -1.ExamplesExample 1Input:nums = [12, 21, 45, 33, 54]Output:1Explanation:(0,1) → reverse(12) = 21 → distance = 1(2,4) → reverse(45) = 54 → distance = 2✔ Minimum = 1Example 2Input:nums = [120, 21]Output:1Example 3Input:nums = [21, 120]Output:-1Key InsightThe core idea is:Instead of checking every pair,store reversed values and match on the fly.❌ Naive Approach (Brute Force)IdeaCheck all pairs (i, j)Reverse nums[i]Compare with nums[j]ComplexityTime: O(n²) ❌Space: O(1)ProblemWith n ≤ 100000, this approach will definitely cause TLE.✅ Optimized Approach (HashMap)IntuitionWhile iterating through the array:Reverse the current numberCheck if this number was already seen as a reversed valueIf yes → we found a mirror pairKey TrickInstead of storing original numbers:👉 Store reversed values as keysThis allows instant lookup.Java Code (With Detailed Comments)import java.util.*;class Solution {// Function to reverse digits of a numberpublic int reverse(int m) {int rev = 0;while (m != 0) {int dig = m % 10; // extract last digitm = m / 10; // remove last digitrev = rev * 10 + dig; // build reversed number}return rev;}public int minMirrorPairDistance(int[] nums) {// Map to store reversed values and their indicesHashMap<Integer, Integer> mp = new HashMap<>();int min = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {// Check if current number exists in map// Meaning: some previous number had reverse equal to thisif (mp.containsKey(nums[i])) {// Calculate distanceint prevIndex = mp.get(nums[i]);min = Math.min(min, Math.abs(i - prevIndex));}// Reverse current numberint revVal = reverse(nums[i]);// Store reversed value with indexmp.put(revVal, i);}// If no pair found, return -1return min == Integer.MAX_VALUE ? -1 : min;}}Step-by-Step Dry RunInput:nums = [12, 21, 45, 33, 54]Execution:IndexValueReverseMap CheckAction01221not foundstore (21 → 0)12112founddistance = 124554not foundstore (54 → 2)33333not foundstore (33 → 3)45445founddistance = 2👉 Minimum = 1Complexity AnalysisTime ComplexityReversing number → O(digits) ≈ O(log n)Loop → O(n)👉 Overall: O(n)Space ComplexityHashMap stores at most n elements👉 O(n)Why This Approach WorksAvoids unnecessary pair comparisonsUses hashing for constant-time lookupProcesses array in a single passKey TakeawaysAlways think of hashing when matching conditions existReversing numbers can convert the problem into a lookup problemAvoid brute force when constraints are largeThis is a classic “store & check” patternCommon Interview PatternThis problem is similar to:Two Sum (hashing)Reverse pairsMatching transformationsConclusionThe Minimum Absolute Distance Between Mirror Pairs problem is a great example of how a simple optimization (using a HashMap) can reduce complexity from O(n²) → O(n).Understanding this pattern will help you solve many similar problems involving:TransformationsMatching conditionsEfficient lookupsFrequently Asked Questions (FAQs)1. Why store reversed value instead of original?Because we want to quickly check if a number matches the reverse of a previous number.2. What if multiple same reversed values exist?The map stores the latest index, ensuring minimum distance is considered.3. Can this be solved without HashMap?Yes, but it will result in inefficient O(n²) time.

LeetCodeArrayJavaMediumHashMap

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

🔗 Problem LinkLeetCode 383 – Ransom Note 👉 https://leetcode.com/problems/ransom-note/IntroductionThis is a classic frequency-count problem that tests your understanding of:Character countingHashMap usageGreedy validation logicAt first glance, the problem looks very simple — but it’s a very common interview question because it checks whether you can think in terms of resource usage.Here:magazine → available resourcesransomNote → required resourcesWe must check if the available letters are sufficient to construct the ransom note.📌 Problem UnderstandingYou are given:ransomNotemagazineRules:Each letter in magazine can be used only once.Return true if ransomNote can be formed.Otherwise return false.Example 1Input: ransomNote = "a", magazine = "b"Output: falseExample 2Input: ransomNote = "aa", magazine = "ab"Output: falseExample 3Input: ransomNote = "aa", magazine = "aab"Output: true🧠 IntuitionThe logic is straightforward:Count frequency of each character in magazine.For each character in ransomNote:Check if it exists in the map.Check if its frequency is greater than 0.Reduce frequency after using it.If at any point we cannot use a character → return false.This is a greedy approach.💻 Your Codeclass Solution { public boolean canConstruct(String r, String m) { HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0 ; i < m.length();i++){ mp.put(m.charAt(i),mp.getOrDefault(m.charAt(i),0)+1); } for(int i = 0 ; i <r.length();i++){ if(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0){ mp.put(r.charAt(i),mp.get(r.charAt(i)) -1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Build Frequency Map from MagazineHashMap<Character,Integer> mp = new HashMap<>();for(int i =0 ; i < m.length();i++){ mp.put(m.charAt(i), mp.getOrDefault(m.charAt(i),0) + 1);}We count how many times each character appears in the magazine.2️⃣ Check Each Character in Ransom Notefor(int i = 0 ; i < r.length();i++){For every character in ransomNote:3️⃣ Validate Availabilityif(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0)If:Character exists in mapFrequency is still availableThen reduce its count:mp.put(r.charAt(i), mp.get(r.charAt(i)) - 1);Otherwise:return false;Immediately stop if we cannot construct.🎯 Why This WorksWe treat:magazine as supplyransomNote as demandWe reduce supply every time we use a character.If supply runs out → construction fails.⏱ Complexity AnalysisTime Complexity: O(n + m)One pass to build map from magazineOne pass to check ransomNoteSpace Complexity: O(26) ≈ O(1)Only lowercase English letters.🔥 Even Better Optimization – Using Array Instead of HashMapSince we know:Only lowercase letters are allowedWe can use an integer array of size 26.This is faster and more memory-efficient.Optimized Versionclass Solution { public boolean canConstruct(String r, String m) { int[] freq = new int[26]; for(char c : m.toCharArray()){ freq[c - 'a']++; } for(char c : r.toCharArray()){ if(freq[c - 'a'] == 0){ return false; } freq[c - 'a']--; } return true; }}This avoids HashMap overhead.🏁 Final ThoughtsThis problem reinforces:Frequency counting patternGreedy character usageEarly exit for optimizationUsing arrays instead of HashMap when character set is limitedIt’s a foundational problem that appears often in interviews.If you master this pattern, you can easily solve:Valid AnagramFind the DifferenceCheck if All Characters Have Equal OccurrencesPermutation in String

HashMapStringFrequency CountGreedyLeetCodeEasy

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

LeetCode 3488 — Closest Equal Element Queries: A Complete Walkthrough from Brute Force to Optimal

If you have been grinding LeetCode lately, you have probably run into problems where your first clean-looking solution times out and forces you to rethink from scratch. LeetCode 3488 is exactly that kind of problem. This article walks through the complete thought process — from the naive approach that got me TLE, to the intuition shift, to the final optimized solution in Java.You can find the original problem here: LeetCode 3488 — Closest Equal Element Queries at Problem LinkUnderstanding the ProblemYou are given a circular array nums and an array of queries. For each query queries[i], you must find the minimum distance between the element at index queries[i] and any other index j such that nums[j] == nums[queries[i]]. If no such other index exists, the answer is -1.The critical detail here is the word circular. The array wraps around, which means the distance between two indices i and j in an array of length n is not simply |i - j|. It is:min( |i - j| , n - |i - j| )You can travel either clockwise or counterclockwise, and you take whichever path is shorter.Breaking Down the ExamplesExample 1nums = [1, 3, 1, 4, 1, 3, 2], queries = [0, 3, 5]For query index 0, the value is 1. Other indices holding 1 are 2 and 4. Circular distances are min(2, 5) = 2 and min(4, 3) = 3. The minimum is 2.For query index 3, the value is 4. It appears nowhere else in the array. Answer is -1.For query index 5, the value is 3. The other 3 sits at index 1. Circular distance is min(4, 3) = 3. Answer is 3.Output: [2, -1, 3]Example 2nums = [1, 2, 3, 4], queries = [0, 1, 2, 3]Every element is unique. Every query returns -1.Output: [-1, -1, -1, -1]First Attempt — Brute ForceMy first instinct was straightforward. For each query, scan the entire array, collect every index that matches the queried value, compute the circular distance to each, and return the minimum. Clean logic, easy to reason about, and dead simple to implement.while (i != queries.length) { int max = Integer.MAX_VALUE; for (int j = 0; j < nums.length; j++) { int target = nums[queries[i]]; if (nums[j] == target && j != queries[i]) { // Linear distance between the two indices int right = Math.abs(j - queries[i]); // Distance going the other direction around the ring int left = nums.length - right; // True circular distance is the shorter of the two int dist = Math.min(right, left); max = Math.min(max, dist); } } lis.add(max == Integer.MAX_VALUE ? -1 : max); i++;}This got TLE immediately, and once you look at the constraints it is obvious why. Both nums.length and queries.length can be up to 10^5. For every query you are scanning every element, giving you O(n × q) time — which in the worst case is 10 billion operations. No judge is going to wait for that.Rethinking the Approach — Where Is the Waste?After the TLE, the question I asked myself was: what work is being repeated unnecessarily?The answer was obvious in hindsight. Every time a query asks about a value like 3, the brute force scans the entire array again looking for every index that holds 3. If ten different queries all ask about value 3, you are doing that scan ten times. You are finding the same indices over and over.The fix is to do that work exactly once, before any query is processed. You precompute a map from each value to all the indices where it appears. Then for every query you simply look up the relevant list and work within it.That observation reduces the precomputation to O(n) — one pass through the array. The question then becomes: once you have that sorted list of indices for a given value, how do you find the closest one to your query index efficiently?The Key Insight — You Only Need Two NeighboursHere is the insight that makes this problem elegant. The index list for any value is sorted in ascending order because you build it by iterating left to right through the array. If your query index sits at position mid inside that sorted list, then by definition every index to the left of mid - 1 is farther away than arr[mid - 1], and every index to the right of mid + 1 is farther away than arr[mid + 1].This means you never need to compare against all duplicates. You only ever need to check the immediate left and right neighbours of your query index within the sorted list.The one subtlety is the circular wrap. Because the array itself is circular, the left neighbour of the very first element in the list is actually the last element in the list, since you can wrap around the ring. This is handled cleanly with modular arithmetic: (mid - 1 + n) % n for the left neighbour and (mid + 1) % n for the right.The Optimized Solution — HashMap + Binary SearchStep 1 — Precompute the index mapIterate through nums once and build a HashMap mapping each value to a list of all indices where it appears. The lists are sorted by construction since you insert indices in order.Step 2 — Binary search to locate the query indexFor a given query at index q, look up the index list for nums[q]. Binary search the list to find the position of q within it. This runs in O(log n) rather than O(n).Step 3 — Check immediate neighbours and compute circular distancesOnce you have the position mid, fetch arr[(mid + 1) % n] and arr[(mid - 1 + n) % n]. For each, compute the circular distance using min(|diff|, totalLength - |diff|). Return the smaller of the two.Full Annotated Java Solutionclass Solution { public List<Integer> solveQueries(int[] nums, int[] queries) { int c = 0; // Precompute: map each value to the sorted list of indices where it appears. // Since we iterate left to right, the list is sorted by construction. HashMap<Integer, List<Integer>> mp = new HashMap<>(); for (int i = 0; i < nums.length; i++) { mp.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i); } List<Integer> lis = new ArrayList<>(); while (c != queries.length) { // Retrieve the sorted index list for the value at the queried position List<Integer> arr = mp.get(nums[queries[c]]); int n = arr.size(); int i = 0; int j = n - 1; int min = -1; while (i <= j) { int mid = i + (j - i) / 2; if (arr.get(mid) == queries[c]) { // Only one occurrence in the entire array — no duplicate exists if (n == 1) { min = -1; } else { // Circular neighbour to the right within the index list int right = arr.get((mid + 1) % n); // Circular neighbour to the left within the index list int left = arr.get((mid - 1 + n) % n); // Compute circular distance to the right neighbour int d1 = Math.abs(right - queries[c]); int distRight = Math.min(d1, nums.length - d1); // Compute circular distance to the left neighbour int d2 = Math.abs(left - queries[c]); int distLeft = Math.min(d2, nums.length - d2); // The answer is the closer of the two neighbours min = Math.min(distLeft, distRight); } break; } else if (arr.get(mid) > queries[c]) { // Query index is smaller — search the left half j = mid - 1; } else { // Query index is larger — search the right half i = mid + 1; } } lis.add(min); c++; } return lis; }}Complexity AnalysisTime Complexity: O(n log n)Building the HashMap takes O(n). For each of the q queries, binary search over the index list takes O(log n) in the worst case. Total: O(n + q log n), which simplifies to O(n log n) given the constraint that q ≤ n.Space Complexity: O(n)The HashMap stores every index exactly once across all its lists, so total space used is O(n).Compared to the brute force O(n × q), this is the difference between ~1.7 million operations and ~10 billion operations at the constraint limits.Common PitfallsMixing up the two values of n. Inside the solution, n refers to arr.size() — the number of occurrences of a particular value. But when computing circular distance, you need nums.length — the full array length. These are different numbers and swapping them silently produces wrong answers.Forgetting the + n in the left neighbour formula. Writing (mid - 1) % n when mid is 0 produces -1 in Java, since Java's modulo preserves the sign of the dividend. Always write (mid - 1 + n) % n.Not handling the single-occurrence case. If a value appears only once, n == 1, and the neighbour formula wraps around to the element itself, giving a distance of zero — which is completely wrong. Guard against this explicitly before running the neighbour logic.What This Problem Teaches YouThe journey from brute force to optimal here follows a pattern worth internalizing.The brute force was correct but repeated work. Recognizing that repeated work and lifting it into a precomputation step is the single move that makes this problem tractable. The HashMap does that.Once you have a sorted structure, binary search is almost always the right tool to find a position within it. And once you have a position in a sorted structure, you only ever need to look at adjacent elements to find the nearest one — checking anything further is redundant by definition.These are not tricks specific to this problem. They are transferable patterns that appear across dozens of medium and hard problems on the platform. Internalizing them — rather than memorizing solutions — is what actually builds problem-solving ability over time.

ArraysHashMapBinary SearchCircular ArraysMediumLeetCodeJava

Understanding HashMap and Hashing Techniques: A Complete Guide

What is HashMap?HashMap is a non-linear data structure that lives inside Java's collection framework, alongside other structures like Trees and Graphs (see the generated image above). What makes it special? It uses a clever technique called hashing to store and retrieve data at blazing speeds.Think of hashing as a smart address system. It converts large keys (like long strings or big numbers) into smaller values that work as array indices. This simple trick transforms your data lookup from slow O(n)O(n) or O(log⁡n)O(logn) operations into lightning-fast O(1)O(1) access times!Understanding Hashing MappingsBefore diving deeper, let's understand the four types of hashing mappings:One-to-one mapping — Each key maps to exactly one indexMany-to-one mapping — Multiple keys can map to the same indexOne-to-many mapping — One key maps to multiple indicesMany-to-many mapping — Multiple keys map to multiple indicesHashMap primarily uses one-to-one and many-to-one mapping strategies to achieve its performance goals.The Problem: Why Not Just Use Arrays?Let's say you want to store 7 elements with keys: 1, 5, 23, 57, 234, 678, and 1000.Using direct indexing (where key = array index), you'd need an array of size 1000 just to store 7 items! That leaves 993 empty slots wasting precious memory. Imagine having a parking lot with 1000 spaces for just 7 cars — totally inefficient!This is the exact problem hash functions solve.Hash Functions: The SolutionA hash function takes your key and calculates which array index to use. The beauty? You can now store those same 7 elements in an array of just size 10!The most common hash function uses the modulus operator:hash(key)=keymod array sizehash(key)=keymodarray sizeExample: With array size = 10:Key 57 → Index: 57mod 10=757mod10=7Key 234 → Index: 234mod 10=4234mod10=4Key 1000 → Index: 1000mod 10=01000mod10=0Now you only need an array of size 10 instead of 1000. Problem solved!Three Popular Hash Function TypesModulus MethodThe most widely used technique. Divide the key by array size (or a prime number) and use the remainder as the index.index=keymod sizeindex=keymodsizeMid Square MethodSquare the key value, then extract the middle digits to form your hash value.Example: Key = 57 → 572=3249572=3249 → Extract middle digits "24"Folding HashingDivide the key into equal parts, add them together, then apply modulus.Example: Key = 123456Split into: 12, 34, 56Sum: 12+34+56=10212+34+56=102Apply modulus: 102mod 10=2102mod10=2The Collision ProblemHere's the catch: sometimes two different keys produce the same index. This is called a collision.Example:Key 27 → 27mod 10=727mod10=7Key 57 → 57mod 10=757mod10=7Both keys want index 7! We need smart strategies to handle this.Collision Resolution: Two Main TechniquesTechnique 1: Open Chaining (Separate Chaining)Mapping Type: Many-to-oneWhen a collision happens, create a linked list at that index and store all colliding values in sorted order.Example: Keys 22 and 32 both map to index 2:Index 2: [22] → [32] → nullAdvantage: Simple and works well in practiceDrawback: If too many collisions occur, the linked list becomes long and searching degrades to O(n)O(n). However, Java's collection framework uses highly optimized hash functions that achieve amortized O(1)O(1) time complexity.Technique 2: Closed Addressing (Open Addressing)Mapping Type: One-to-manyInstead of creating a list, find another empty slot in the array. There are three approaches:Linear ProbingWhen collision occurs, check the next index. If it's occupied, keep checking the next one until you find an empty slot.Hash Function:h(x)=xmod sizeh(x)=xmodsizeOn Collision:h(x)=(h(x)+i)mod sizeh(x)=(h(x)+i)modsizewhere i=0,1,2,3,…i=0,1,2,3,…Example: Keys 22 and 32 both map to index 2:Store 22 at index 2Try 32 at index 2 → occupiedCheck index 3 → empty, store 32 thereProblems:Clustering: Keys bunch together in adjacent indices, slowing down searchesDeleted Slot Problem: When you delete a key, it creates an empty slot that breaks the search chainThe Deleted Slot Problem Explained:Keys 22 and 32 are at indices 2 and 3Delete key 22 from index 2Now when searching for key 32, the algorithm reaches index 2 (empty), thinks key 32 doesn't exist, and stops searching!Solution: Mark deleted slots with a special marker (like -1) or perform rehashing after deletions.Quadratic ProbingSame concept as linear probing, but instead of checking consecutive slots, jump in quadratic increments: 1, 4, 9, 16, 25...Hash Function:h(x)=xmod sizeh(x)=xmodsizeOn Collision:h(x)=(h(x)+i2)mod sizeh(x)=(h(x)+i2)modsizewhere i=0,1,2,3,…i=0,1,2,3,…Advantage: Significantly reduces clusteringDrawback: Still suffers from the deleted slot problemDouble HashingThe most sophisticated approach! Uses two different hash functions to create unique probe sequences for each key.First Hash Function:h1(x)=xmod sizeh1(x)=xmodsizeSecond Hash Function:h2(x)=prime−(xmod prime)h2(x)=prime−(xmodprime)On Collision:h(x)=(h1(x)+i×h2(x))mod sizeh(x)=(h1(x)+i×h2(x))modsizewhere i=0,1,2,3,…i=0,1,2,3,…Advantage: Effectively avoids clustering and provides the best performance among probing techniquesLoad Factor: The Performance IndicatorThe load factor tells you how full your hash table is:Load Factor=Number of elementsArray sizeLoad Factor=Array sizeNumber of elementsPerformance GuidelinesLoad Factor ≤ 0.5 → Good performance, fast operations Load Factor > 0.7 → Poor performance, time to rehash ExamplesBad Load Factor:Array size = 10, Elements = 8Load Factor = 8/10=0.88/10=0.8Action: Rehash the array (typically double the size)Good Load Factor:Array size = 200, Elements = 100Load Factor = 100/200=0.5100/200=0.5Action: No changes needed, performing optimallyWhat is Rehashing?When the load factor exceeds the threshold (usually 0.7), the hash table is resized — typically doubled in size. All existing elements are then rehashed and redistributed into the new larger array. This maintains optimal performance as your data grows.Performance SummaryHashMap delivers exceptional average-case performance:Insertion: O(1)O(1)Deletion: O(1)O(1)Search: O(1)O(1)However, in the worst case (many collisions with poor hash functions), operations can degrade to O(n)O(n).The key to maintaining O(1)O(1) performance:Use a good hash functionChoose an appropriate collision resolution strategyMonitor and maintain a healthy load factorRehash when necessaryConclusionHashMap is one of the most powerful and frequently used data structures in programming. By understanding hashing techniques, collision resolution strategies, and load factors, you can write more efficient code and make better design decisions.Whether you're building a cache, implementing a frequency counter, or solving complex algorithm problems, HashMap is your go-to tool for fast data access!

hashmapdata-structureshashingjavaalgorithmscollision-resolutiontime-complexity

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

Try the ProblemYou can solve the problem here:https://leetcode.com/problems/find-unique-binary-string/Problem DescriptionYou are given an array nums containing n unique binary strings, where each string has length n.Your task is to return any binary string of length n that does not appear in the array.Important ConditionsEach string consists only of '0' and '1'.Every string in the array is unique.The output must be a binary string of length n.If multiple valid answers exist, any one of them is acceptable.ExamplesExample 1Inputnums = ["01","10"]Output"11"ExplanationPossible binary strings of length 2:00011011Since "01" and "10" are already present, valid answers could be:00 or 11Example 2Inputnums = ["00","01"]Output"11"Another valid output could be:10Example 3Inputnums = ["111","011","001"]Output101Other valid answers include:000010100110Constraintsn == nums.length1 <= n <= 16nums[i].length == nnums[i] consists only of '0' and '1'All strings in nums are uniqueImportant ObservationThe total number of binary strings of length n is:2^nBut the array contains only:n stringsSince 2^n grows very quickly and n ≤ 16, there are many possible binary strings missing from the array. Our goal is simply to construct one of those missing strings.Thinking About the ProblemBefore jumping into coding, it's useful to think about different strategies that could help us generate a binary string that does not appear in the array.Possible Ways to Think About the ProblemWhen approaching this problem, several ideas may come to mind:Generate all possible binary strings of length n and check which one is missing.Store all strings in a HashSet or HashMap and construct a candidate string to verify whether it exists.Manipulate existing strings by flipping bits to create new combinations.Use a mathematical trick that guarantees the new string is different from every string in the list.Each of these approaches leads to a different solution strategy.In this article, we will walk through these approaches and understand how they work.Approach 1: Brute Force – Generate All Binary StringsIdeaThe simplest idea is to generate every possible binary string of length n and check whether it exists in the given array.Since there are:2^n possible binary stringsWe can generate them one by one and return the first string that does not appear in nums.StepsConvert numbers from 0 to (2^n - 1) into binary strings.Pad the binary string with leading zeros so its length becomes n.Check if that string exists in the array.If not, return it.Time ComplexityO(2^n * n)This works because n is at most 16, but it is still not the most elegant approach.Approach 2: HashMap + Bit Flipping (My Approach)IdeaWhile solving this problem, another idea is to store all given binary strings inside a HashMap for quick lookup.Then we can try to construct a new binary string by flipping bits from the existing strings.The intuition is simple:If the current character is '0', change it to '1'.If the current character is '1', change it to '0'.By flipping bits at different positions, we attempt to build a new binary combination.Once the string is constructed, we check whether it already exists in the map.If the generated string does not exist, we return it as our answer.Java Implementation (My Solution)class Solution { public String findDifferentBinaryString(String[] nums) { int len = nums[0].length(); // HashMap to store all given binary strings HashMap<String, Integer> mp = new HashMap<>(); for(int i = 0; i < nums.length; i++){ mp.put(nums[i], i); } int cou = 0; String ans = ""; for(int i = 0; i < nums.length; i++){ if(cou < len){ // Flip the current bit if(nums[i].charAt(cou) == '0'){ ans += '1'; cou++; } else{ ans += '0'; cou++; } }else{ // If generated string does not exist in map if(!mp.containsKey(ans)){ return ans; } // Reset and try building again ans = ""; cou = 0; } } return ans; }}Time ComplexityO(n²)Because we iterate through the array and perform string operations.Space ComplexityO(n)For storing the strings in the HashMap.Approach 3: Cantor’s Diagonalization (Optimal Solution)IdeaA clever mathematical observation allows us to construct a string that must differ from every string in the array.We build a new string such that:The first character differs from the first string.The second character differs from the second string.The third character differs from the third string.And so on.By ensuring that the generated string differs from each string at least at one position, it is guaranteed not to exist in the array.This technique is known as Cantor’s Diagonalization.Java Implementationclass Solution { public String findDifferentBinaryString(String[] nums) { int n = nums.length; StringBuilder result = new StringBuilder(); for(int i = 0; i < n; i++){ // Flip the diagonal bit if(nums[i].charAt(i) == '0'){ result.append('1'); } else{ result.append('0'); } } return result.toString(); }}Time ComplexityO(n)We only traverse the array once.Space ComplexityO(n)For storing the resulting string.Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesBrute ForceO(2^n * n)O(n)Simple but inefficientHashMap + Bit FlippingO(n²)O(n)Constructive approachCantor DiagonalizationO(n)O(n)Optimal and elegantKey TakeawaysThis problem highlights an interesting concept in algorithm design:Sometimes the best solution is not searching for the answer but constructing one directly.By understanding the structure of the input, we can generate a result that is guaranteed to be unique.ConclusionThe Find Unique Binary String problem can be solved using multiple strategies, ranging from brute force enumeration to clever mathematical construction.While brute force works due to the small constraint (n ≤ 16), more elegant solutions exist. Using hashing or constructive approaches improves efficiency and demonstrates deeper algorithmic thinking.Among all approaches, the Cantor Diagonalization technique provides the most efficient and mathematically guaranteed solution.Understanding problems like this helps strengthen skills in string manipulation, hashing, and constructive algorithms, which are commonly tested in coding interviews.

Binary StringsHashingCantor DiagonalizationLeetCodeMedium

Find All Duplicates in an Array

LeetCode Problem 448 – Find All Numbers Disappeared in an ArrayProblem Link: LinkProblem StatementYou are given an array nums of length n, where each element nums[i] lies in the range [1, n]. Your task is to return all numbers in the range [1, n] that do not appear in the array.Example 1Inputnums = [4, 3, 2, 7, 8, 2, 3, 1]Output[5, 6]Example 2Inputnums = [1, 1]Output[2]Constraintsn == nums.length1 ≤ n ≤ 10⁵1 ≤ nums[i] ≤ nApproachThe goal is to identify numbers within the range 1 to n that are missing from the given array.One straightforward way to solve this problem is by using a HashMap to track the presence of each number:Traverse the array and store each element in a HashMap.Iterate through the range 1 to n.For each number, check whether it exists in the HashMap.If a number is not present, add it to the result list.This approach ensures that:Each element is processed only once.Lookup operations are efficient.Time and Space ComplexityTime Complexity: O(n)Space Complexity: O(n) (due to the HashMap)Solution Code (Java)public List<Integer> findDisappearedNumbers(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); List<Integer> result = new ArrayList<>(); // Store all elements in the HashMap for (int num : nums) { map.put(num, 0); } // Check for missing numbers in the range [1, n] for (int i = 1; i <= nums.length; i++) { if (!map.containsKey(i)) { result.add(i); } } return result;}Final NotesWhile this solution is simple and easy to understand, it uses additional space.LeetCode also offers a constant space solution by modifying the input array in-place, which is worth exploring for optimization.

LeetCodeMediumHashMap

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

🔗 Problem LinkLeetCode 242 – Valid Anagram 👉 https://leetcode.com/problems/valid-anagram/IntroductionThis is one of the most important string frequency problems in coding interviews.The idea of checking whether two strings are anagrams appears in many variations:Group AnagramsRansom NoteFind the DifferencePermutation in StringIf you master this pattern, you unlock a whole category of problems.Let’s break it down step by step.📌 Problem UnderstandingTwo strings are anagrams if:They contain the same charactersWith the same frequenciesOrder does not matterExample 1Input: s = "anagram" t = "nagaram"Output: trueBoth contain:a → 3n → 1g → 1r → 1m → 1Example 2Input: s = "rat" t = "car"Output: falseDifferent character frequencies.🧠 IntuitionThe core idea:If two strings are anagrams, their character frequencies must match exactly.So we:Check if lengths are equal.Count frequency of characters in first string.Subtract frequencies using second string.If at any point frequency becomes negative → not anagram.💻 Your Codeclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } for(int i =0; i < t.length();i++){ if(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0){ mp.put(t.charAt(i),mp.get(t.charAt(i))-1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Length Checkif(s.length() != t.length()) return false;If lengths differ → cannot be anagrams.2️⃣ Build Frequency Mapmp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);Count occurrences of each character in s.3️⃣ Subtract Using Second Stringif(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0)If character exists and frequency is available → reduce it.Otherwise → return false immediately.🎯 Why This WorksWe treat:First string as frequency builderSecond string as frequency consumerIf all frequencies match perfectly, we return true.⏱ Complexity AnalysisTime Complexity: O(n)One pass to build mapOne pass to compareSpace Complexity: O(26) ≈ O(1)Only lowercase English letters allowed.🔥 Optimized Approach – Using Array Instead of HashMapSince the problem guarantees:s and t consist of lowercase English lettersWe can replace HashMap with an integer array of size 26.This is faster and cleaner.Optimized Versionclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; int[] freq = new int[26]; for(char c : s.toCharArray()){ freq[c - 'a']++; } for(char c : t.toCharArray()){ freq[c - 'a']--; if(freq[c - 'a'] < 0){ return false; } } return true; }}🚀 Why This Is BetterNo HashMap overheadDirect index accessCleaner codeFaster in interviews🏁 Final ThoughtsThis problem teaches:Frequency counting patternEarly exit optimizationUsing arrays instead of HashMap when character set is limitedThinking in terms of resource balanceValid Anagram is a foundation problem.Once you master it, you can easily solve:Ransom NoteFind the DifferenceGroup AnagramsCheck Equal Character Occurrences

HashMapStringFrequency CountArraysLeetCodeEasy

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

IntroductionLeetCode 2958: Length of Longest Subarray With at Most K Frequency is an excellent problem to understand how sliding window with frequency counting works in arrays with duplicates.The problem asks us to find the longest contiguous subarray such that no element occurs more than K times.If you’d like to try solving the problem first, you can attempt it here:Try the problem on LeetCode:https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/Problem UnderstandingYou are given:An integer array numsAn integer kA good subarray is defined as a subarray where the frequency of each element is ≤ k.Goal: Return the length of the longest good subarray.Examples:Input: nums = [1,2,3,1,2,3,1,2], k = 2Output: 6Explanation: Longest good subarray = [1,2,3,1,2,3]Input: nums = [1,2,1,2,1,2,1,2], k = 1Output: 2Explanation: Longest good subarray = [1,2]Input: nums = [5,5,5,5,5,5,5], k = 4Output: 4Explanation: Longest good subarray = [5,5,5,5]A naive approach would check all subarrays and count frequencies →Time Complexity: O(n²) → too slow for nums.length up to 10⁵Key Idea: Sliding Window with Frequency MapInstead of brute-force:Use a sliding window [i, j] to track the current subarrayUse a HashMap mp to store the frequency of each element in the windowExpand j by adding nums[j] to the mapIf mp.get(nums[j]) > k, shrink the window from the left (i) until mp.get(nums[j]) <= kAt each step, update the maximum length of the valid windowIntuition:We allow each element to appear at most K timesBy shrinking the window whenever a frequency exceeds k, we always maintain a valid subarraySliding window ensures linear traversalApproach (Step-by-Step)Initialize i = 0, j = 0 → window pointersInitialize co = 0 → maximum lengthInitialize HashMap mp to store frequencies of elements in the windowIterate j from 0 to nums.length - 1:Increment frequency of nums[j] in mpWhile mp.get(nums[j]) > k:Shrink window from the left by decrementing mp[nums[i]] and incrementing iUpdate co = max(co, j - i + 1)Return co as the length of the longest good subarrayImplementation (Java)class Solution {public int maxSubarrayLength(int[] nums, int k) {int i = 0, j = 0; // window pointersint co = 0; // max length of good subarrayHashMap<Integer, Integer> mp = new HashMap<>(); // frequency mapwhile (j < nums.length) {mp.put(nums[j], mp.getOrDefault(nums[j], 0) + 1);// Shrink window until all frequencies <= kwhile (mp.get(nums[j]) > k) {mp.put(nums[i], mp.get(nums[i]) - 1);i++;}co = Math.max(co, j - i + 1);j++;}return co;}}Dry Run ExampleInput:nums = [1,2,3,1,2,3,1,2], k = 2Execution:Window [i, j]Frequency Map mpValid?Max length co[0,0] → [1]{1:1}Yes1[0,1] → [1,2]{1:1,2:1}Yes2[0,2] → [1,2,3]{1:1,2:1,3:1}Yes3[0,3] → [1,2,3,1]{1:2,2:1,3:1}Yes4[0,4] → [1,2,3,1,2]{1:2,2:2,3:1}Yes5[0,5] → [1,2,3,1,2,3]{1:2,2:2,3:2}Yes6[0,6] → [1,2,3,1,2,3,1]{1:3,2:2,3:2}No → shrink6Output:6Complexity AnalysisTime Complexity: O(n) → Each element enters and leaves the window at most onceSpace Complexity: O(n) → HashMap stores frequencies of elements in the window (worst-case all distinct)Edge Cases ConsideredAll elements occur ≤ k → entire array is validAll elements occur > k → max subarray length = kSingle-element arrays → return 1 if k ≥ 1Large arrays up to 10⁵ elements → O(n) solution works efficientlySliding Window Pattern ImportanceThis problem demonstrates sliding window with frequency map, useful for:Subarrays with frequency constraintsLongest subarray with limited duplicatesSimilar to "max consecutive ones with flips" and "fruit into baskets"By mastering this approach, you can efficiently solve many array and subarray problems with constraints.ConclusionUsing HashMap + sliding window, we reduce a naive O(n²) approach to O(n) while keeping the solution intuitive and easy to implement.Understanding this pattern allows solving complex frequency-constrained subarray problems efficiently in interviews.

SlidingWindowHashMapLeetCodeMedium

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

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

🔗 Problem LinkLeetCode 409 – Longest Palindrome 👉 https://leetcode.com/problems/longest-palindrome/IntroductionThis is one of those problems where you don’t actually need to build the palindrome.You just need to calculate the maximum possible length of a palindrome that can be formed using the given characters.The key idea here is understanding:How palindromes are structured.Once you understand that, the solution becomes straightforward and elegant.📌 Problem UnderstandingYou are given a string s containing:Lowercase lettersUppercase lettersCase-sensitive (meaning 'A' and 'a' are different)You must return:The length of the longest palindrome that can be built using those characters.You can rearrange characters in any order.Example 1Input: s = "abccccdd"Output: 7One possible palindrome:dccaccdLength = 7Example 2Input: s = "a"Output: 1🧠 Key Observation About PalindromesA palindrome:Reads the same forward and backward.Has mirror symmetry.This means:Characters must appear in pairs.At most one character can appear an odd number of times (middle character).🧠 Intuition Behind the ApproachLet’s think step by step:Count frequency of each character.For every character:If frequency is even → use all of them.If frequency is odd → use (frequency - 1).If at least one odd frequency exists → we can place one odd character in the center.That’s it.This is a greedy approach.💻 Your Codeclass Solution { public int longestPalindrome(String s) { if(s.length() == 1) return 1; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0; i < s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } int len =0; boolean odd = false; for(int a : mp.values()){ if(a%2 == 0){ len+=a; }else{ len+=a-1; odd= true; } } if(odd){ return len+1; } return len; }}🔍 Step-by-Step Explanation1️⃣ Edge Caseif(s.length() == 1) return 1;If there is only one character, the answer is 1.2️⃣ Frequency CountingHashMap<Character,Integer> mp = new HashMap<>();for(int i =0; i < s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1);}We count how many times each character appears.3️⃣ Build the Palindrome Lengthint len = 0;boolean odd = false;len → stores palindrome lengthodd → tracks whether any odd frequency exists4️⃣ Process Each Frequencyfor(int a : mp.values()){ if(a % 2 == 0){ len += a; }else{ len += a - 1; odd = true; }}If frequency is even → use all characters.If odd:Use a - 1 (which is even)Keep track that we saw an odd number5️⃣ Add Middle Character If Neededif(odd){ return len + 1;}If at least one odd frequency exists → we can place one character in the center.Otherwise → return len.🎯 Why This WorksIn a palindrome:All characters must appear in pairs (mirrored sides).Only one character can be unpaired (center).So we:Use all even counts.Use even portion of odd counts.Add one center character if possible.⏱ Complexity AnalysisTime Complexity: O(n)One pass to count frequenciesOne pass over map (max 52 characters: A–Z, a–z)Space Complexity: O(52) ≈ O(1)At most 52 distinct characters.🔥 Cleaner Optimization IdeaWe don’t even need a boolean variable.We can simply:Add a / 2 * 2 for every frequencyIf total length < original string length → add 1Example optimized version:class Solution { public int longestPalindrome(String s) { HashMap<Character,Integer> mp = new HashMap<>(); for(char ch : s.toCharArray()){ mp.put(ch, mp.getOrDefault(ch, 0) + 1); } int len = 0; for(int count : mp.values()){ len += (count / 2) * 2; } if(len < s.length()){ len += 1; } return len; }}🏁 Final ThoughtsThis problem teaches:Understanding palindrome structureFrequency countingGreedy logicHandling odd and even countsIt’s a simple but powerful pattern question.If you truly understand this, you can easily solve problems like:Palindrome PermutationLongest Palindrome by Concatenating Two Letter WordsCount Palindromic Subsequences

HashMapStringGreedyFrequency CountLeetCodeEasy

Roman to Integer – Easy Explanation with Java Solution (LeetCode 13)

Try the QuestionYou can try solving the problem here before reading the solution:👉 https://leetcode.com/problems/roman-to-integer/Practicing it yourself first helps you understand the logic better.Roman to Integer – Complete GuideRoman numerals are an ancient numbering system used by the Romans. Instead of digits like 1, 2, 3, they used specific characters to represent values.This problem asks us to convert a Roman numeral string into its corresponding integer value.It is a very common interview question and frequently appears in coding platforms like LeetCode, HackerRank, and coding interviews at product-based companies.Roman Numeral SymbolsRoman numerals consist of seven characters, each representing a fixed value.SymbolValueI1V5X10L50C100D500M1000Example conversions:III = 3 → 1 + 1 + 1XII = 12 → 10 + 1 + 1XXVII = 27 → 10 + 10 + 5 + 1 + 1Normally, Roman numerals are written from largest to smallest from left to right.But there is an important exception.The Subtraction RuleIn some cases, Roman numerals use subtraction instead of addition.If a smaller value appears before a larger value, it means we subtract it.Examples:RomanCalculationResultIV5 − 14IX10 − 19XL50 − 1040XC100 − 1090CD500 − 100400CM1000 − 100900These are the only valid subtraction cases.Example WalkthroughExample 1Inputs = "III"ExplanationI + I + I = 1 + 1 + 1 = 3Output3Example 2Inputs = "LVIII"ExplanationL = 50V = 5III = 350 + 5 + 3 = 58Output58Example 3Inputs = "MCMXCIV"ExplanationM = 1000CM = 900XC = 90IV = 4Total = 1994Output1994Intuition Behind the SolutionThe key idea is to compare each Roman numeral with the numeral to its right.Two situations occur:Case 1 — Normal AdditionIf the current value ≥ next valueWe simply add it to the total.ExampleVI5 + 1 = 6Case 2 — Subtraction CaseIf the current value < next valueWe subtract it.ExampleIV5 - 1 = 4Strategy to SolveCreate a HashMap to store Roman numeral values.Start from the rightmost character.Initialize total with the last character's value.Move from right to left.Compare the current numeral with the next numeral.If smaller → subtract.Otherwise → add.Continue until the beginning of the string.This approach works because Roman numerals follow a local comparison rule.Java Implementationclass Solution { public int romanToInt(String s) { HashMap<Character,Integer> mp = new HashMap<>(); mp.put('I',1); mp.put('V',5); mp.put('X',10); mp.put('L',50); mp.put('C',100); mp.put('D',500); mp.put('M',1000); int tot = mp.get(s.charAt(s.length()-1)); char arr[] = s.toCharArray(); int j = s.length()-2; for(int i = arr.length-1; i >= 0; i--){ if(j >= 0){ if(mp.get(arr[j]) < mp.get(arr[i])){ tot -= mp.get(arr[j]); }else if(mp.get(arr[j]) > mp.get(arr[i])){ tot += mp.get(arr[j]); }else{ tot += mp.get(arr[j]); } } j--; } return tot; }}Code ExplanationStep 1 — Store Roman ValuesWe create a HashMap so we can quickly get the numeric value of each Roman character.I → 1V → 5X → 10...This allows O(1) lookup time.Step 2 — Initialize TotalWe start with the last character.int tot = mp.get(s.charAt(s.length()-1));Why?Because the last numeral is always added, never subtracted.Step 3 — Traverse from Right to LeftWe move backward through the string.for(int i = arr.length-1; i >= 0; i--)And compare with the previous character.Step 4 — Apply Roman RulesIf the previous numeral is smaller than the current numeral:tot -= valueExampleIV5 - 1If it is greater or equal:tot += valueExampleVI5 + 1Time ComplexityO(n)Where n = length of the string.We only traverse the string once.Space ComplexityO(1)The HashMap size is constant (only 7 entries).Key Takeaways✔ Roman numerals mostly use addition✔ Subtraction occurs only in six specific cases✔ Comparing current and next value is the simplest approach✔ A single pass solution (O(n)) is enoughThis is why this problem is commonly used to test string processing and logical reasoning in coding interviews.Final ThoughtsThe Roman to Integer problem is a great beginner-friendly problem that teaches:HashMap usageString traversalConditional logicPattern recognitionMastering these simple problems builds a strong foundation for more complex algorithmic questions.If you're preparing for coding interviews, this is definitely a problem you should practice.

LeetCodeJavaString ProblemsEasyRoman Numerals

Unique Number of Occurrences

LeetCode Problem 1207Link of the Problem to try -: LinkGiven an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.Example 1:Input: arr = [1,2,2,1,1,3]Output: trueExplanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.Example 2:Input: arr = [1,2]Output: falseExample 3:Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]Output: trueConstraints:1 <= arr.length <= 1000-1000 <= arr[i] <= 1000Solution:It is a little bit tricky question as it says you have to return true if the elements frequency contained by the array is distinct and no frequency is same if it is then return true otherwise false. So for solving this we can use HashMap to make frequency of each element then we will create a Set and store all the values of HashMap elements in the Set and then we will simply compare sizes of both Map and Set as we know that if each element frequency is unique then the sizes are same otherwise size are not same and that is a key point to solve this question very easily.Code:HashMap<Integer,Integer> mp = new HashMap<>();Set<Integer> ms = new HashSet<>();for(int i=0;i<arr.length;i++){mp.put(arr[i],mp.getOrDefault(arr[i],0)+1);}for(int u:mp.values()){ms.add(u);}if(ms.size() == mp.size()){return true;}else{return false;}

LeetCodeHashMapHashSet

Majority Element II

LeetCode Problem 229Link of the Problem to try -: LinkGiven an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. Example 1:Input: nums = [3,2,3]Output: [3]Example 2:Input: nums = [1]Output: [1]Example 3:Input: nums = [1,2]Output: [1,2] Constraints:1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109Solution:According to question says we have to create ArrayList in which we have to return those elements whose frequency count is more than array's length divided by 3 and we have to return it simply this is it.And personally if I say this is a very easy question as there you don't need to think very much you can simply create a HashMap in which you maintain frequency of each element and then simply run a for each loop and iterate over the keys by keySet method of HashMap and then get value of each key and check is it greater than array.length/3 or not if it is then simply add in the ArrayList and here you got your ans.Code: public List<Integer> majorityElement(int[] nums) { HashMap<Integer, Integer> mp = new HashMap<>(); List<Integer> lis = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { mp.put(nums[i], mp.getOrDefault(nums[i], 0) + 1); } for (int i : mp.keySet()) { if (mp.get(i) > nums.length / 3) { lis.add(i); } } return lis; }

LeetCodeMediumHashMap

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

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 20: Valid Parentheses — Java Solution Explained

IntroductionLeetCode 20 Valid Parentheses is arguably the single most asked Easy problem in coding interviews. It appears at Google, Amazon, Microsoft, Meta, and virtually every company that does technical interviews. It is the textbook introduction to the Stack data structure and teaches you a pattern that shows up in compilers, code editors, HTML parsers, and mathematical expression evaluators.Here is the Link of Question -: LeetCode 20In this article we cover plain English explanation, real life analogy, the optimal stack solution with detailed dry run, all tricky edge cases, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You are given a string containing only bracket characters — (, ), {, }, [, ]. You need to check if the brackets are correctly matched and nested.Three rules must hold:Every opening bracket must be closed by the same type of closing bracketBrackets must be closed in the correct order — the most recently opened must be closed firstEvery closing bracket must have a corresponding opening bracketReal Life Analogy — Russian Nesting DollsThink of Russian nesting dolls. You open the biggest doll first, then a medium one inside it, then a small one inside that. To close them back, you must close the smallest first, then medium, then biggest. You cannot close the biggest doll while the smallest is still open inside.That is exactly how brackets work. The last opened bracket must be the first one closed. This Last In First Out behavior is precisely what a Stack is built for.Another analogy — think of a text editor like VS Code. When you type (, it automatically adds ). If you try to close with ] instead, the editor highlights an error. This problem is essentially building that validation logic.The Only Approach You Need: StackThe IdeaScan the string left to rightIf you see an opening bracket → push it onto the stackIf you see a closing bracket → check the top of the stack. If the top is the matching opening bracket, pop it. Otherwise the string is invalid.At the end, if the stack is empty → all brackets matched → return true. If stack still has elements → some brackets were never closed → return false.public boolean isValid(String s) {if (s.length() == 1) return false; // single char can never be validStack<Character> st = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(' || c == '{' || c == '[') {st.push(c); // opening bracket — push and wait for its match} else {if (!st.empty()) {// check if top of stack is the matching openerif ((c == ')' && st.peek() != '(') ||(c == '}' && st.peek() != '{') ||(c == ']' && st.peek() != '[')) {return false; // wrong type of closing bracket} else {st.pop(); // matched! remove the opener}} else {return false; // closing bracket with nothing open}}}return st.empty(); // true only if all openers were matched}Detailed Dry Run — s = "([)]"This is the trickiest example. Looks balanced at first glance but is actually invalid.( → opening, push → stack: [(][ → opening, push → stack: [(, []) → closing, peek is [, but ) needs ( → mismatch → return false ✅The stack correctly catches that [ was opened after ( but we tried to close ( before closing [ — wrong order!Dry Run — s = "([{}])"( → push → stack: [(][ → push → stack: [(, []{ → push → stack: [(, [, {]} → peek is {, match! pop → stack: [(, []] → peek is [, match! pop → stack: [(]) → peek is (, match! pop → stack: []Stack is empty → return true ✅Dry Run — s = "(["( → push → stack: [(][ → push → stack: [(, []Loop ends. Stack is NOT empty → return false ✅Two brackets were opened but never closed.All the Edge Cases You Must KnowSingle character like "(" or ")" A single character can never be valid — an opener has nothing to close it, a closer has nothing before it. The early return if (s.length() == 1) return false handles this cleanly.Only closing brackets like "))" The stack is empty when the first ) arrives → return false immediately.Only opening brackets like "(((" All get pushed, nothing gets popped, stack is not empty at end → return false.Interleaved wrong types like "([)]" Caught by the mismatch check when the closing bracket does not match the stack top.Empty string Stack stays empty → st.empty() returns true → returns true. An empty string is technically valid since there are no unmatched brackets. The constraints say length ≥ 1 so this is just good to know.A Cleaner Variation Using HashMapSome developers prefer using a HashMap to store bracket pairs, making the matching condition more readable:public boolean isValid(String s) {Stack<Character> st = new Stack<>();Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put('}', '{');map.put(']', '[');for (char c : s.toCharArray()) {if (map.containsKey(c)) {// closing bracketif (st.empty() || st.peek() != map.get(c)) {return false;}st.pop();} else {st.push(c); // opening bracket}}return st.empty();}The HashMap maps each closing bracket to its expected opening bracket. This makes adding new bracket types trivial — just add one line to the map. Great for extensibility in real world code.Both versions are O(n) time and O(n) space. Choose whichever feels more readable to you.Time Complexity: O(n) — single pass through the string Space Complexity: O(n) — stack holds at most n/2 opening bracketsWhy Stack Is the Perfect Data Structure HereThe key property this problem exploits is LIFO — Last In First Out. The most recently opened bracket must be the first one closed. That is literally the definition of a stack's behavior.Any time you see a problem where the most recently seen item determines what comes next — think Stack immediately. Valid Parentheses is the purest example of this principle.How This Fits Into the Bigger Stack PatternLooking at everything you have solved so far, notice the pattern evolution:844 Backspace String Compare — # pops the last character 1047 Remove Adjacent Duplicates — matching character pops itself 2390 Removing Stars — * pops the last character 3174 Clear Digits — digit pops the last character 20 Valid Parentheses — closing bracket pops its matching openerAll of these are stack simulations. The difference here is that instead of any character being popped, only the correct matching opener is popped. This matching condition is what makes Valid Parentheses a step up in logic from the previous problems.Common Mistakes to AvoidNot checking if stack is empty before peeking If a closing bracket arrives and the stack is empty, calling peek() throws an EmptyStackException. Always check !st.empty() before peeking or popping.Returning true without checking if stack is empty Even if the loop completes without returning false, unclosed openers remain on the stack. Always return st.empty() at the end, not just true.Pushing closing brackets onto the stack Only push opening brackets. Pushing closing brackets gives completely wrong results and is the most common beginner mistake.Not handling odd length strings If s.length() is odd, it is impossible for all brackets to be matched — you can add if (s.length() % 2 != 0) return false as an early exit for a small optimization.FAQs — People Also AskQ1. Why is a Stack used to solve Valid Parentheses? Because the problem requires LIFO matching — the most recently opened bracket must be the first one closed. Stack's Last In First Out behavior maps perfectly to this requirement, making it the natural and optimal data structure choice.Q2. What is the time complexity of LeetCode 20? O(n) time where n is the length of the string. We make a single pass through the string, and each character is pushed and popped at most once. Space complexity is O(n) in the worst case when all characters are opening brackets.Q3. Can LeetCode 20 be solved without a Stack? Technically yes for simple cases using counters, but only when dealing with a single type of bracket. With three types of brackets that can be nested, a Stack is the only clean solution. Counter-based approaches break down on cases like "([)]".Q4. Is LeetCode 20 asked in FAANG interviews? Absolutely. It is one of the most commonly asked problems across all major tech companies. It tests understanding of the Stack data structure and is often used as a warmup before harder stack problems like Largest Rectangle in Histogram or Decode String.Q5. What happens if the input string has an odd length? An odd-length string can never be valid since brackets always come in pairs. You can add if (s.length() % 2 != 0) return false as an early optimization, though the stack logic handles this correctly on its own.Similar LeetCode Problems to Practice Next1047. Remove All Adjacent Duplicates In String — Easy — stack pattern with characters394. Decode String — Medium — nested brackets with encoding678. Valid Parenthesis String — Medium — wildcards added32. Longest Valid Parentheses — Hard — longest valid substring1249. Minimum Remove to Make Valid Parentheses — Medium — remove minimum brackets to make validConclusionLeetCode 20 Valid Parentheses is the definitive introduction to the Stack data structure in competitive programming and technical interviews. The logic is elegant — push openers, pop on matching closers, check empty at the end. Three rules, one data structure, one pass.Master this problem thoroughly, understand every edge case, and you will have a rock-solid foundation for every stack problem that follows — from Decode String to Largest Rectangle in Histogram.

StringStackEasyLeetCode

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

Single Number III

LeetCode Problem 260Link of the Problem to try -: LinkGiven an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.You must write an algorithm that runs in linear runtime complexity and uses only constant extra space. Example 1:Input: nums = [1,2,1,3,2,5]Output: [3,5]Explanation: [5, 3] is also a valid answer.Example 2:Input: nums = [-1,0]Output: [-1,0]Example 3:Input: nums = [0,1]Output: [1,0] Constraints:2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1Each integer in nums will appear twice, only two integers will appear once.Solution:It is a very easy question if we only know about HashMap because it is clearly telling us about to create frequency and to return that number whose frequency is exactly 1 so that's why in this question not a very different or bug thing is there that we have to think about very much.Code: HashMap<Integer,Integer> mp = new HashMap<>(); int ans[] =new int[2]; for(int i=0;i<nums.length;i++){ mp.put(nums[i],mp.getOrDefault(nums[i],0)+1); } int co =0; for(int a:mp.keySet()){ if(mp.get(a) == 1){ ans[co] = a; co++; } } return ans;

LeetCodeMediumHashMapArray

Find All Numbers Disappeared in an Array

LeetCode Problem 448Link of the Problem to try -: LinkGiven an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. Example 1:Input: nums = [4,3,2,7,8,2,3,1]Output: [5,6]Example 2:Input: nums = [1,1]Output: [2] Constraints:n == nums.length1 <= n <= 1051 <= nums[i] <= nSolution:In this question as the question suggests we have to find the missing element from the array that is not in the array but comes in that range of 1 to array.length and we can solve this by creating an HashMap where we simply store all the elements and then run the loop again from 1 to array.length and then check is that element present if not then store it on our ArrayList and return it this is how we can solve this question easily in O(n) Time Complexity.Code: public List<Integer> findDisappearedNumbers(int[] nums) { HashMap<Integer,Integer> mp = new HashMap<>(); List<Integer> lis = new ArrayList<>(); for(int i =0;i<nums.length;i++){ mp.put(nums[i],0); } for(int i = 1;i<=nums.length;i++){ if(!mp.containsKey(i)){ lis.add(i); } } return lis; }

LeetCodeHashMapEasy

Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

IntroductionThe Climbing Stairs problem is one of the most commonly asked coding interview questions for beginners. It is a perfect example to understand recursion, memoization, and dynamic programming (DP).In this article, we will break down the problem step by step and explore multiple approaches—from brute force recursion to an optimized space-efficient solution.Link of Problem: LeetCode – Climbing StairsProblem StatementYou are climbing a staircase that has n steps.Each time, you can either climb 1 step or 2 steps.The goal is to calculate the total number of distinct ways to reach the top.ExampleInput:n = 2Output:2Explanation:1 + 12Input:n = 3Output:3Explanation:1 + 1 + 11 + 22 + 1Key InsightTo reach step n, there are only two possibilities:From step n-1 (taking 1 step)From step n-2 (taking 2 steps)So, the recurrence relation becomes:ways(n) = ways(n-1) + ways(n-2)This is identical to the Fibonacci sequence, making this problem a classic DP question.Approach 1: Recursive Solution (Brute Force)IdeaBreak the problem into smaller subproblems:Count ways to reach n-1Count ways to reach n-2Add both resultsCodeclass Solution { public int climbStairs(int n) { if(n == 0) return 1; if(n < 0) return 0; return climbStairs(n-1) + climbStairs(n-2); }}ComplexityTime Complexity: O(2^n)Space Complexity: O(n)DrawbackThis solution recalculates the same subproblems multiple times, leading to Time Limit Exceeded (TLE) for larger values.Approach 2: Recursion with Memoization (Top-Down DP)IdeaTo optimize recursion, store already computed results using a HashMap.Avoid repeated calculationsConvert exponential time into linear timeCodeimport java.util.HashMap;class Solution { private HashMap<Integer, Integer> memo = new HashMap<>(); public int climbStairs(int n) { if(n == 0) return 1; if(n < 0) return 0; if(memo.containsKey(n)) { return memo.get(n); } int result = climbStairs(n-1) + climbStairs(n-2); memo.put(n, result); return result; }}ComplexityTime Complexity: O(n)Space Complexity: O(n)Why It WorksMemoization ensures each subproblem is solved only once, making recursion efficient and practical.Approach 3: Dynamic Programming (Bottom-Up)IdeaInstead of recursion, build the solution iteratively:Use an array dp[]Store results for each stepBuild from smaller values to larger onesCodeclass Solution { public int climbStairs(int n) { if(n == 1) return n; if(n == 2) return n; if(n == 3) return n; int dp[] = new int[n+1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }}ComplexityTime Complexity: O(n)Space Complexity: O(n)Approach 4: Optimal Solution (Space Optimized)IdeaWe only need the last two values instead of the whole array.Codeclass Solution { public int climbStairs(int n) { if(n <= 2) return n; int prev1 = 1; int prev2 = 2; for(int i = 3; i <= n; i++) { int current = prev1 + prev2; prev1 = prev2; prev2 = current; } return prev2; }}ComplexityTime Complexity: O(n)Space Complexity: O(1)Key TakeawaysThe problem follows a Fibonacci-like patternBrute force recursion is simple but inefficientMemoization converts recursion into an efficient solutionDynamic programming avoids recursion completelySpace optimization reduces memory usage to constant spaceWhen This Problem Is AskedThis question is frequently asked in:Coding interviews (product-based companies)Data Structures & Algorithms examsOnline coding platformsIt evaluates:Problem-solving abilityUnderstanding of recursionOptimization skillsConclusionThe Climbing Stairs problem is a foundational example for learning dynamic programming. Starting with recursion and improving it using memoization and iterative DP demonstrates how to optimize algorithms effectively.Understanding this pattern will help solve many similar problems related to sequences and decision-making.Frequently Asked Questions (FAQs)1. Is this problem related to Fibonacci?Yes, the recurrence relation is exactly the same as the Fibonacci sequence.2. Why does recursion fail for large inputs?Because it recalculates the same values repeatedly, leading to exponential time complexity.3. What is the best approach?The space-optimized approach is the most efficient with O(n) time and O(1) space.

EasyJavaLeetCodeRecursionMemoization

Recursion in Java - Complete Guide With Examples and Practice Problems

IntroductionIf there is one topic in programming that confuses beginners more than anything else, it is recursion. Most people read the definition, nod their head, and then immediately freeze when they have to write recursive code themselves.The problem is not that recursion is genuinely hard. The problem is that most explanations start with code before building the right mental model. Once you have the right mental model, recursion clicks permanently and you start seeing it everywhere — in tree problems, graph problems, backtracking, dynamic programming, divide and conquer, and more.This guide covers everything from the ground up. What recursion is, how the call stack works, how to identify base cases and recursive cases, every type of recursion, common patterns, time and space complexity analysis, the most common mistakes, and the top LeetCode problems to practice.By the end of this article, recursion will not feel like magic anymore. It will feel like a natural tool you reach for confidently.What Is Recursion?Recursion is when a function calls itself to solve a smaller version of the same problem.That is the complete definition. But let us make it concrete.Imagine you want to count down from 5 to 1. One way is a loop. Another way is — print 5, then solve the exact same problem for counting down from 4 to 1. Then print 4, solve for 3. And so on until you reach the base — there is nothing left to count down.void countDown(int n) { if (n == 0) return; // stop here System.out.println(n); countDown(n - 1); // solve the smaller version}The function countDown calls itself with a smaller input each time. Eventually it reaches 0 and stops. That stopping condition is the most important part of any recursive function — the base case.The Two Parts Every Recursive Function Must HaveEvery correctly written recursive function has exactly two parts. Without both, the function either gives wrong answers or runs forever.Part 1: Base CaseThe base case is the condition under which the function stops calling itself and returns a direct answer. It is the smallest version of the problem that you can solve without any further recursion.Without a base case, recursion never stops and you get a StackOverflowError — Java's way of telling you the call stack ran out of memory.Part 2: Recursive CaseThe recursive case is where the function calls itself with a smaller or simpler input — moving closer to the base case with each call. If your recursive case does not make the problem smaller, you have an infinite loop.Think of it like a staircase. The base case is the ground floor. The recursive case is each step going down. Every step must genuinely bring you one level closer to the ground.How Recursion Works — The Call StackThis is the mental model that most explanations skip, and it is the reason recursion confuses people.Every time a function is called in Java, a new stack frame is created and pushed onto the call stack. This frame stores the function's local variables, parameters, and where to return to when the function finishes.When a recursive function calls itself, a new frame is pushed on top. When that call finishes, its frame is popped and execution returns to the previous frame.Let us trace countDown(3) through the call stack:countDown(3) called → frame pushed prints 3 calls countDown(2) → frame pushed prints 2 calls countDown(1) → frame pushed prints 1 calls countDown(0) → frame pushed n == 0, return → frame popped back in countDown(1), return → frame popped back in countDown(2), return → frame popped back in countDown(3), return → frame poppedOutput: 3, 2, 1The call stack grows as calls go deeper, then shrinks as calls return. This is why recursion uses O(n) space for n levels deep — each level occupies one stack frame in memory.Your First Real Recursive Function — FactorialFactorial is the classic first recursion example. n! = n × (n-1) × (n-2) × ... × 1Notice the pattern — n! = n × (n-1)!. The factorial of n is n times the factorial of n-1. That recursive structure makes it perfect for recursion.public int factorial(int n) { // base case if (n == 0 || n == 1) return 1; // recursive case return n * factorial(n - 1);}Dry Run — factorial(4)factorial(4)= 4 * factorial(3)= 4 * 3 * factorial(2)= 4 * 3 * 2 * factorial(1)= 4 * 3 * 2 * 1= 24The call stack builds up going in, then multiplications happen coming back out. This "coming back out" phase is called the return phase or unwinding of the stack.Time Complexity: O(n) — n recursive calls Space Complexity: O(n) — n frames on the call stackThe Two Phases of RecursionEvery recursive function has two phases and understanding both is critical.Phase 1: The Call Phase (Going In)This happens as the function keeps calling itself with smaller inputs. Things you do before the recursive call happen in this phase — in order from the outermost call to the innermost.Phase 2: The Return Phase (Coming Back Out)This happens as each call finishes and returns to its caller. Things you do after the recursive call happen in this phase — in reverse order, from the innermost call back to the outermost.This distinction explains why the output order can be surprising:void printBothPhases(int n) { if (n == 0) return; System.out.println("Going in: " + n); // call phase printBothPhases(n - 1); System.out.println("Coming out: " + n); // return phase}For printBothPhases(3):Going in: 3Going in: 2Going in: 1Coming out: 1Coming out: 2Coming out: 3This two-phase understanding is what makes problems like reversing a string or printing a linked list backwards via recursion feel natural.Types of RecursionRecursion is not one-size-fits-all. There are several distinct types and knowing which type applies to a problem shapes how you write the solution.1. Direct RecursionThe function calls itself directly. This is the most common type — what we have seen so far.void direct(int n) { if (n == 0) return; direct(n - 1); // calls itself}2. Indirect RecursionFunction A calls Function B which calls Function A. They form a cycle.void funcA(int n) { if (n <= 0) return; System.out.println("A: " + n); funcB(n - 1);}void funcB(int n) { if (n <= 0) return; System.out.println("B: " + n); funcA(n - 1);}Used in: state machines, mutual recursion in parsers, certain mathematical sequences.3. Tail RecursionThe recursive call is the last operation in the function. Nothing happens after the recursive call returns — no multiplication, no addition, nothing.// NOT tail recursive — multiplication happens after returnint factorial(int n) { if (n == 1) return 1; return n * factorial(n - 1); // multiply after return — not tail}// Tail recursive — recursive call is the last thingint factorialTail(int n, int accumulator) { if (n == 1) return accumulator; return factorialTail(n - 1, n * accumulator); // last operation}Why does tail recursion matter? In languages that support tail call optimization (like Scala, Kotlin, and many functional languages), tail recursive functions can be converted to iteration internally — no stack frame accumulation, O(1) space. Java does NOT perform tail call optimization, but understanding tail recursion is still important for interviews and functional programming concepts.4. Head RecursionThe recursive call happens first, before any other processing. All processing happens in the return phase.void headRecursion(int n) { if (n == 0) return; headRecursion(n - 1); // call first System.out.println(n); // process after}// Output: 1 2 3 4 5 (processes in reverse order of calls)5. Tree RecursionThe function makes more than one recursive call per invocation. This creates a tree of calls rather than a linear chain. Fibonacci is the classic example.int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // TWO recursive calls}The call tree for fibonacci(4): fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0)Time Complexity: O(2ⁿ) — exponential! Each call spawns two more. Space Complexity: O(n) — maximum depth of the call treeThis is why memoization (caching results) is so important for tree recursion — it converts O(2ⁿ) to O(n) by never recomputing the same subproblem twice.6. Mutual RecursionA specific form of indirect recursion where two functions call each other alternately to solve a problem. Different from indirect recursion in that the mutual calls are the core mechanism of the solution.// Check if a number is even or odd using mutual recursionboolean isEven(int n) { if (n == 0) return true; return isOdd(n - 1);}boolean isOdd(int n) { if (n == 0) return false; return isEven(n - 1);}Common Recursion Patterns in DSAThese are the patterns you will see over and over in interview problems. Recognizing them is more important than memorizing solutions.Pattern 1: Linear Recursion (Do Something, Recurse on Rest)Process the current element, then recurse on the remaining problem.// Sum of arrayint arraySum(int[] arr, int index) { if (index == arr.length) return 0; // base case return arr[index] + arraySum(arr, index + 1); // current + rest}Pattern 2: Divide and Conquer (Split Into Two Halves)Split the problem into two halves, solve each recursively, combine results.// Merge Sortvoid mergeSort(int[] arr, int left, int right) { if (left >= right) return; // base case — single element int mid = (left + right) / 2; mergeSort(arr, left, mid); // sort left half mergeSort(arr, mid + 1, right); // sort right half merge(arr, left, mid, right); // combine}Pattern 3: Backtracking (Try, Recurse, Undo)Try a choice, recurse to explore it, undo the choice when backtracking.// Generate all subsetsvoid subsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { if (index == nums.length) { result.add(new ArrayList<>(current)); return; } // Choice 1: include nums[index] current.add(nums[index]); subsets(nums, index + 1, current, result); current.remove(current.size() - 1); // undo // Choice 2: exclude nums[index] subsets(nums, index + 1, current, result);}Pattern 4: Tree Recursion (Left, Right, Combine)Recurse on left subtree, recurse on right subtree, combine or process results.// Height of binary treeint height(TreeNode root) { if (root == null) return 0; // base case int leftHeight = height(root.left); // solve left int rightHeight = height(root.right); // solve right return 1 + Math.max(leftHeight, rightHeight); // combine}Pattern 5: Memoization (Cache Recursive Results)Store results of recursive calls so the same subproblem is never solved twice.Map<Integer, Integer> memo = new HashMap<>();int fibonacci(int n) { if (n <= 1) return n; if (memo.containsKey(n)) return memo.get(n); // return cached int result = fibonacci(n - 1) + fibonacci(n - 2); memo.put(n, result); // cache before returning return result;}This converts Fibonacci from O(2ⁿ) to O(n) time with O(n) space — a massive improvement.Recursion vs Iteration — When to Use WhichThis is one of the most common interview questions about recursion. Here is a clear breakdown:Use Recursion when:The problem has a naturally recursive structure (trees, graphs, divide and conquer)The solution is significantly cleaner and easier to understand recursivelyThe problem involves exploring multiple paths or choices (backtracking)The depth of recursion is manageable (not too deep to cause stack overflow)Use Iteration when:The problem is linear and a loop is equally clearMemory is a concern (iteration uses O(1) stack space vs O(n) for recursion)Performance is critical and function call overhead mattersJava's stack size limit could be hit (default around 500-1000 frames for deep recursion)The key rule: Every recursive solution can be converted to an iterative one (usually using an explicit stack). But recursive solutions for tree and graph problems are almost always cleaner to write and understand.Time and Space Complexity of Recursive FunctionsAnalyzing complexity for recursive functions requires a specific approach.The Recurrence Relation MethodExpress the time complexity as a recurrence relation and solve it.Factorial:T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) = T(1) + n×O(1) = O(n)Fibonacci (naive):T(n) = T(n-1) + T(n-2) + O(1) ≈ 2×T(n-1) = O(2ⁿ)Binary Search:T(n) = T(n/2) + O(1) = O(log n) [by Master Theorem]Merge Sort:T(n) = 2×T(n/2) + O(n) = O(n log n) [by Master Theorem]Space Complexity Rule for RecursionSpace complexity of a recursive function = maximum depth of the call stack × space per frameLinear recursion (factorial, sum): O(n) spaceBinary recursion (Fibonacci naive): O(n) space (maximum depth, not number of nodes)Divide and conquer (merge sort): O(log n) space (depth of recursion tree)Memoized Fibonacci: O(n) space (memo table + call stack)Classic Recursive Problems With SolutionsProblem 1: Reverse a StringString reverse(String s) { if (s.length() <= 1) return s; // base case // last char + reverse of everything before last char return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));}Dry run for "hello":reverse("hello") = 'o' + reverse("hell")reverse("hell") = 'l' + reverse("hel")reverse("hel") = 'l' + reverse("he")reverse("he") = 'e' + reverse("h")reverse("h") = "h"Unwinding: "h" → "he" → "leh" → "lleh" → "olleh" ✅Problem 2: Power Function (x^n)double power(double x, int n) { if (n == 0) return 1; // base case if (n < 0) return 1.0 / power(x, -n); // handle negative if (n % 2 == 0) { double half = power(x, n / 2); return half * half; // x^n = (x^(n/2))^2 } else { return x * power(x, n - 1); }}This is the fast power algorithm — O(log n) time instead of O(n).Problem 3: Fibonacci With Memoizationint[] memo = new int[100];Arrays.fill(memo, -1);int fib(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib(n - 1) + fib(n - 2); return memo[n];}Time: O(n) — each value computed once Space: O(n) — memo array + call stackProblem 4: Tower of HanoiThe classic recursion teaching problem. Move n disks from source to destination using a helper rod.void hanoi(int n, char source, char destination, char helper) { if (n == 1) { System.out.println("Move disk 1 from " + source + " to " + destination); return; } // Move n-1 disks from source to helper hanoi(n - 1, source, helper, destination); // Move the largest disk from source to destination System.out.println("Move disk " + n + " from " + source + " to " + destination); // Move n-1 disks from helper to destination hanoi(n - 1, helper, destination, source);}Time Complexity: O(2ⁿ) — minimum moves required is 2ⁿ - 1 Space Complexity: O(n) — call stack depthProblem 5: Generate All Subsets (Power Set)void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { result.add(new ArrayList<>(current)); // add current subset for (int i = index; i < nums.length; i++) { current.add(nums[i]); // include generateSubsets(nums, i + 1, current, result); // recurse current.remove(current.size() - 1); // exclude (backtrack) }}For [1, 2, 3] — generates all 8 subsets: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]Time: O(2ⁿ) — 2ⁿ subsets Space: O(n) — recursion depthProblem 6: Binary Search Recursivelyint binarySearch(int[] arr, int target, int left, int right) { if (left > right) return -1; // base case — not found int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right); else return binarySearch(arr, target, left, mid - 1);}Time: O(log n) — halving the search space each time Space: O(log n) — log n frames on the call stackRecursion on Trees — The Natural HabitatTrees are where recursion truly shines. Every tree problem becomes elegant with recursion because a tree is itself a recursive structure — each node's left and right children are trees themselves.// Maximum depth of binary treeint maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}// Check if tree is symmetricboolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);}// Path sum — does any root-to-leaf path sum to target?boolean hasPathSum(TreeNode root, int target) { if (root == null) return false; if (root.left == null && root.right == null) return root.val == target; return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);}Notice the pattern in all three — base case handles null, recursive case handles left and right subtrees, result combines both.How to Think About Any Recursive Problem — Step by StepThis is the framework you should apply to every new recursive problem you encounter:Step 1 — Identify the base case What is the smallest input where you know the answer directly without any recursion? For arrays it is usually empty array or single element. For trees it is null node. For numbers it is 0 or 1.Step 2 — Trust the recursive call Assume your function already works correctly for smaller inputs. Do not trace through the entire recursion mentally — just trust it. This is the Leap of Faith and it is what makes recursion feel natural.Step 3 — Express the current problem in terms of smaller problems How does the answer for size n relate to the answer for size n-1 (or n/2, or subtrees)? This relationship is your recursive case.Step 4 — Make sure each call moves toward the base case The input must become strictly smaller with each call. If it does not, you have infinite recursion.Step 5 — Write the base case first, then the recursive case Always. Writing the recursive case first leads to bugs because you have not defined when to stop.Common Mistakes and How to Avoid ThemMistake 1: Missing or wrong base case The most common mistake. Missing the base case causes StackOverflowError. Wrong base case causes wrong answers.Always ask — what is the simplest possible input, and what should the function return for it? Write that case first.Mistake 2: Not moving toward the base case If you call factorial(n) inside factorial(n) without reducing n, you loop forever. Every recursive call must make the problem strictly smaller.Mistake 3: Trusting your brain to trace deep recursion Do not try to trace 10 levels of recursion in your head. Trust the recursive call, verify the base case, and check that each call reduces the problem. That is all you need.Mistake 4: Forgetting to return the recursive result// WRONG — result is computed but not returnedint sum(int n) { if (n == 0) return 0; sum(n - 1) + n; // computed but discarded!}// CORRECTint sum(int n) { if (n == 0) return 0; return sum(n - 1) + n;}Mistake 5: Modifying shared state without backtracking In backtracking problems, if you add something to a list before a recursive call, you must remove it after the call returns. Forgetting to backtrack leads to incorrect results and is one of the trickiest bugs to find.Mistake 6: Recomputing the same subproblems Naive Fibonacci computes fib(3) multiple times when computing fib(5). Use memoization whenever you notice overlapping subproblems in your recursion tree.Top LeetCode Problems on RecursionThese are organized by pattern — work through them in this order for maximum learning:Pure Recursion Basics:509. Fibonacci Number — Easy — start here, implement with and without memoization344. Reverse String — Easy — recursion on arrays206. Reverse Linked List — Easy — recursion on linked list50. Pow(x, n) — Medium — fast power with recursionTree Recursion (Most Important):104. Maximum Depth of Binary Tree — Easy — simplest tree recursion112. Path Sum — Easy — decision recursion on tree101. Symmetric Tree — Easy — mutual recursion on tree110. Balanced Binary Tree — Easy — bottom-up recursion236. Lowest Common Ancestor of a Binary Tree — Medium — classic tree recursion124. Binary Tree Maximum Path Sum — Hard — advanced tree recursionDivide and Conquer:148. Sort List — Medium — merge sort on linked list240. Search a 2D Matrix II — Medium — divide and conquerBacktracking:78. Subsets — Medium — generate all subsets46. Permutations — Medium — generate all permutations77. Combinations — Medium — generate combinations79. Word Search — Medium — backtracking on grid51. N-Queens — Hard — classic backtrackingMemoization / Dynamic Programming:70. Climbing Stairs — Easy — Fibonacci variant with memoization322. Coin Change — Medium — recursion with memoization to DP139. Word Break — Medium — memoized recursionRecursion Cheat Sheet// Linear recursion templatereturnType solve(input) { if (baseCase) return directAnswer; // process current return solve(smallerInput);}// Tree recursion templatereturnType solve(TreeNode root) { if (root == null) return baseValue; returnType left = solve(root.left); returnType right = solve(root.right); return combine(left, right, root.val);}// Backtracking templatevoid backtrack(choices, current, result) { if (goalReached) { result.add(copy of current); return; } for (choice : choices) { make(choice); // add to current backtrack(...); // recurse undo(choice); // remove from current }}// Memoization templateMap<Input, Output> memo = new HashMap<>();returnType solve(input) { if (baseCase) return directAnswer; if (memo.containsKey(input)) return memo.get(input); returnType result = solve(smallerInput); memo.put(input, result); return result;}FAQs — People Also AskQ1. What is recursion in Java with a simple example? Recursion is when a function calls itself to solve a smaller version of the same problem. A simple example is factorial — factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) and so on until factorial(1) returns 1 directly.Q2. What is the difference between recursion and iteration? Iteration uses loops (for, while) and runs in O(1) space. Recursion uses function calls and uses O(n) stack space for n levels deep. Recursion is often cleaner for tree and graph problems. Iteration is better when memory is a concern or the problem is inherently linear.Q3. What causes StackOverflowError in Java recursion? StackOverflowError happens when recursion goes too deep — too many frames accumulate on the call stack before any of them return. This is caused by missing base case, wrong base case, or input too large for Java's default stack size limit.Q4. What is the difference between recursion and dynamic programming? Recursion solves a problem by breaking it into subproblems. Dynamic programming is recursion plus memoization — storing results of subproblems so they are never computed twice. DP converts exponential recursive solutions into polynomial ones by eliminating redundant computation.Q5. What is tail recursion and does Java support tail call optimization? Tail recursion is when the recursive call is the absolute last operation in the function. Java does NOT support tail call optimization — Java always creates a new stack frame for each call even if it is tail recursive. Languages like Scala and Kotlin (on the JVM) do support it with the tailrec keyword.Q6. How do you convert recursion to iteration? Every recursive solution can be converted to iterative using an explicit stack data structure. The call stack's behavior is replicated manually — push the initial call, loop while stack is not empty, pop, process, and push sub-calls. Tree traversals are a common example of this conversion.ConclusionRecursion is not magic. It is a systematic way of solving problems by expressing them in terms of smaller versions of themselves. Once you internalize the two parts (base case and recursive case), understand the call stack mentally, and learn to trust the recursive call rather than trace it completely, everything clicks.The learning path from here is clear — start with simple problems like Fibonacci and array sum. Move to tree problems where recursion is most natural. Then tackle backtracking. Finally add memoization to bridge into dynamic programming.Every hour you spend understanding recursion deeply pays dividends across the entire rest of your DSA journey. Trees, graphs, divide and conquer, backtracking, dynamic programming — all of them build on this foundation.

RecursionJavaBase CaseCall StackBacktrackingDynamic Programming

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

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

StringMath TrickASCIIBit ManipulationLeetCodeEasy

What Is Dynamic Programming? Origin Story, Real-Life Uses, LeetCode Problems & Complete Beginner Guide

Introduction — Why Dynamic Programming Feels Hard (And Why It Isn't)If you've ever stared at a LeetCode problem, read the solution, understood every single line, and still had absolutely no idea how someone arrived at it — welcome. You've just experienced the classic Dynamic Programming (DP) confusion.DP has a reputation. People treat it like some dark art reserved for competitive programmers or Google engineers. The truth? Dynamic Programming is one of the most logical, learnable, and satisfying techniques in all of computer science. Once it clicks, it really clicks.This guide will take you from zero to genuinely confident. We'll cover where DP came from, how it works, what patterns to learn, how to recognize DP problems, real-world places it shows up, LeetCode problems to practice, time complexity analysis, and the mistakes that trip up even experienced developers.Let's go.The Origin Story — Who Invented Dynamic Programming and Why?The term "Dynamic Programming" was coined by Richard Bellman in the early 1950s while working at RAND Corporation. Here's the funny part: the name was deliberately chosen to sound impressive and vague.Bellman was doing mathematical research that his employer — the US Secretary of Defense, Charles Wilson — would have found difficult to fund if described accurately. Wilson had a well-known distaste for the word "research." So Bellman invented a name that sounded suitably grand and mathematical: Dynamic Programming.In his autobiography, Bellman wrote that he picked the word "dynamic" because it had a precise technical meaning and was also impossible to use negatively. "Programming" referred to the mathematical sense — planning and decision-making — not computer programming.The underlying idea? Break a complex problem into overlapping subproblems, solve each subproblem once, and store the result so you never solve it twice.Bellman's foundational contribution was the Bellman Equation, which underpins not just algorithms but also economics, operations research, and modern reinforcement learning.So the next time DP feels frustrating, remember — even its inventor named it specifically to confuse people. You're in good company.What Is Dynamic Programming? (Simple Definition)Dynamic Programming is an algorithmic technique used to solve problems by:Breaking them down into smaller overlapping subproblemsSolving each subproblem only onceStoring the result (memoization or tabulation)Building up the final solution from those stored resultsThe key insight is overlapping subproblems + optimal substructure.Overlapping subproblems means the same smaller problems come up again and again. Instead of solving them every time (like plain recursion does), DP solves them once and caches the answer.Optimal substructure means the optimal solution to the whole problem can be built from optimal solutions to its subproblems.If a problem has both these properties — it's a DP problem.The Two Approaches to Dynamic Programming1. Top-Down with Memoization (Recursive + Cache)You write a recursive solution exactly as you would naturally, but add a cache (usually a dictionary or array) to store results you've already computed.fib(n):if n in cache: return cache[n]if n <= 1: return ncache[n] = fib(n-1) + fib(n-2)return cache[n]This is called memoization — remember what you computed so you don't repeat yourself.Pros: Natural to write, mirrors the recursive thinking, easy to reason about. Cons: Stack overhead from recursion, risk of stack overflow on large inputs.2. Bottom-Up with Tabulation (Iterative)You figure out the order in which subproblems need to be solved, then solve them iteratively from the smallest up, filling a table.fib(n):dp = [0, 1]for i from 2 to n:dp[i] = dp[i-1] + dp[i-2]return dp[n]This is called tabulation — fill a table, cell by cell, bottom to top.Pros: No recursion overhead, usually faster in practice, easier to optimize space. Cons: Requires thinking about the order of computation upfront.🧩 Dynamic Programming Template CodeBefore diving into how to recognize DP problems, here are ready-to-use Java templates for every major DP pattern. Think of these as your reusable blueprints — every DP problem you ever solve will fit into one of these structures. Just define your state, plug in your recurrence relation, and you are good to go.Template 1 — Top-Down (Memoization)import java.util.HashMap;import java.util.Map;public class TopDownDP {Map<Integer, Integer> memo = new HashMap<>();public int solve(int n) {// Base caseif (n <= 1) return n;// Check cacheif (memo.containsKey(n)) return memo.get(n);// Recurrence relation — change this part for your problemint result = solve(n - 1) + solve(n - 2);// Store in cachememo.put(n, result);return result;}}Template 2 — Bottom-Up (Tabulation)public class BottomUpDP {public int solve(int n) {// Create DP tableint[] dp = new int[n + 1];// Base casesdp[0] = 0;dp[1] = 1;// Fill the table bottom-upfor (int i = 2; i <= n; i++) {// Recurrence relation — change this part for your problemdp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}}Template 3 — Bottom-Up with Space Optimizationpublic class SpaceOptimizedDP {public int solve(int n) {// Only keep last two values instead of full tableint prev2 = 0;int prev1 = 1;for (int i = 2; i <= n; i++) {// Recurrence relation — change this part for your problemint curr = prev1 + prev2;prev2 = prev1;prev1 = curr;}return prev1;}}Template 4 — 2D DP (Two Sequences or Grid)public class TwoDimensionalDP {public int solve(String s1, String s2) {int m = s1.length();int n = s2.length();// Create 2D DP tableint[][] dp = new int[m + 1][n + 1];// Base cases — first row and columnfor (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;// Fill table cell by cellfor (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// Recurrence relation — change this part for your problemif (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j],Math.min(dp[i][j - 1], dp[i - 1][j - 1]));}}}return dp[m][n];}}Template 5 — Knapsack Patternpublic class KnapsackDP {public int solve(int[] weights, int[] values, int capacity) {int n = weights.length;// dp[i][w] = max value using first i items with capacity wint[][] dp = new int[n + 1][capacity + 1];for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {// Don't take item idp[i][w] = dp[i - 1][w];// Take item i if it fitsif (weights[i - 1] <= w) {dp[i][w] = Math.max(dp[i][w],values[i - 1] + dp[i - 1][w - weights[i - 1]]);}}}return dp[n][capacity];}}💡 How to use these templates:Step 1 — Identify which pattern your problem fits into. Step 2 — Define what dp[i] or dp[i][j] means in plain English before writing any code. Step 3 — Write your recurrence relation on paper first. Step 4 — Plug it into the matching template above. Step 5 — Handle your specific base cases carefully.🎥 Visual Learning Resource — Watch This Before Moving ForwardIf you prefer learning by watching before reading, this free full-length course by freeCodeCamp is one of the best Dynamic Programming resources on the internet. Watch it alongside this guide for maximum understanding.Credit: freeCodeCamp — a free, nonprofit coding education platform.How to Recognize a Dynamic Programming ProblemAsk yourself these four questions:1. Can I define the problem in terms of smaller versions of itself? If you can write a recursive formula (recurrence relation), DP might apply.2. Do the subproblems overlap? If a naive recursive solution would recompute the same thing many times, DP is the right tool.3. Is there an optimal substructure? Is the best answer to the big problem made up of best answers to smaller problems?4. Are you looking for a count, minimum, maximum, or yes/no answer? DP problems often ask: "What is the minimum cost?", "How many ways?", "Can we achieve X?"Red flag words in problem statements: minimum, maximum, shortest, longest, count the number of ways, can we reach, is it possible, fewest steps.The Core DP Patterns You Must LearnMastering DP is really about recognizing patterns. Here are the most important ones:Pattern 1 — 1D DP (Linear) Problems where the state depends on previous elements in a single sequence. Examples: Fibonacci, Climbing Stairs, House Robber.Pattern 2 — 2D DP (Grid / Two-sequence) Problems with two dimensions of state, often grids or two strings. Examples: Longest Common Subsequence, Edit Distance, Unique Paths.Pattern 3 — Interval DP You consider all possible intervals or subarrays and build solutions from them. Examples: Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning.Pattern 4 — Knapsack DP (0/1 and Unbounded) You decide whether to include or exclude items under a capacity constraint. Examples: 0/1 Knapsack, Coin Change, Partition Equal Subset Sum.Pattern 5 — DP on Trees State is defined per node; you combine results from children. Examples: Diameter of Binary Tree, House Robber III, Maximum Path Sum.Pattern 6 — DP on Subsets / Bitmask DP State includes a bitmask representing which elements have been chosen. Examples: Travelling Salesman Problem, Shortest Superstring.Pattern 7 — DP on Strings Matching, editing, or counting arrangements within strings. Examples: Longest Palindromic Subsequence, Regular Expression Matching, Wildcard Matching.Top LeetCode Problems to Practice Dynamic Programming (With Links)Here are the essential problems, organized by difficulty and pattern. Solve them in this order.Beginner — Warm UpProblemPatternLinkClimbing Stairs1D DPhttps://leetcode.com/problems/climbing-stairs/Fibonacci Number1D DPhttps://leetcode.com/problems/fibonacci-number/House Robber1D DPhttps://leetcode.com/problems/house-robber/Min Cost Climbing Stairs1D DPhttps://leetcode.com/problems/min-cost-climbing-stairs/Best Time to Buy and Sell Stock1D DPhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock/Intermediate — Core PatternsProblemPatternLinkCoin ChangeKnapsackhttps://leetcode.com/problems/coin-change/Longest Increasing Subsequence1D DPhttps://leetcode.com/problems/longest-increasing-subsequence/Longest Common Subsequence2D DPhttps://leetcode.com/problems/longest-common-subsequence/0/1 Knapsack (via Subset Sum)Knapsackhttps://leetcode.com/problems/partition-equal-subset-sum/Unique Paths2D Grid DPhttps://leetcode.com/problems/unique-paths/Jump Game1D DP / Greedyhttps://leetcode.com/problems/jump-game/Word BreakString DPhttps://leetcode.com/problems/word-break/Decode Ways1D DPhttps://leetcode.com/problems/decode-ways/Edit Distance2D String DPhttps://leetcode.com/problems/edit-distance/Triangle2D DPhttps://leetcode.com/problems/triangle/Advanced — Interview LevelProblemPatternLinkBurst BalloonsInterval DPhttps://leetcode.com/problems/burst-balloons/Regular Expression MatchingString DPhttps://leetcode.com/problems/regular-expression-matching/Wildcard MatchingString DPhttps://leetcode.com/problems/wildcard-matching/Palindrome Partitioning IIInterval DPhttps://leetcode.com/problems/palindrome-partitioning-ii/Maximum Profit in Job SchedulingDP + Binary Searchhttps://leetcode.com/problems/maximum-profit-in-job-scheduling/Distinct Subsequences2D DPhttps://leetcode.com/problems/distinct-subsequences/Cherry Pickup3D DPhttps://leetcode.com/problems/cherry-pickup/Real-World Use Cases of Dynamic ProgrammingDP is not just for coding interviews. It is deeply embedded in the technology you use every day.1. Google Maps & Navigation (Shortest Path) The routing engines behind GPS apps use DP-based algorithms like Dijkstra and Bellman-Ford to find the shortest or fastest path between two points across millions of nodes.2. Spell Checkers & Autocorrect (Edit Distance) When your phone corrects "teh" to "the," it is computing Edit Distance — a classic DP problem — between what you typed and every word in the dictionary.3. DNA Sequence Alignment (Bioinformatics) Researchers use the Needleman-Wunsch and Smith-Waterman algorithms — both DP — to align DNA and protein sequences and find similarities between species or identify mutations.4. Video Compression (MPEG, H.264) Modern video codecs use DP to determine the most efficient way to encode video frames, deciding which frames to store as full images and which to store as differences from the previous frame.5. Financial Portfolio Optimization Investment algorithms use DP to find the optimal allocation of assets under risk constraints — essentially a variant of the knapsack problem.6. Natural Language Processing (NLP) The Viterbi algorithm — used in speech recognition, part-of-speech tagging, and machine translation — is a DP algorithm. Every time Siri or Google Assistant understands your sentence, DP played a role.7. Game AI (Chess, Checkers) Game trees and minimax algorithms with memoization use DP to evaluate board positions and find the best move without recomputing already-seen positions.8. Compiler Optimization Compilers use DP to decide the optimal order of operations and instruction scheduling to generate the most efficient machine code.9. Text Justification (Word Processors) Microsoft Word and LaTeX use DP to optimally break paragraphs into lines — minimizing raggedness and maximizing visual appeal.10. Resource Scheduling in Cloud Computing AWS, Google Cloud, and Azure use DP-based scheduling to assign computational tasks to servers in the most cost-efficient way possible.Time Complexity Analysis of Common DP ProblemsUnderstanding the time complexity of DP is critical for interviews and for building scalable systems.ProblemTime ComplexitySpace ComplexityNotesFibonacci (naive recursion)O(2ⁿ)O(n)Exponential — terribleFibonacci (DP)O(n)O(1) with optimizationLinear — excellentLongest Common SubsequenceO(m × n)O(m × n)m, n = lengths of two stringsEdit DistanceO(m × n)O(m × n)Can optimize space to O(n)0/1 KnapsackO(n × W)O(n × W)n = items, W = capacityCoin ChangeO(n × amount)O(amount)Classic tabulationLongest Increasing SubsequenceO(n²) or O(n log n)O(n)Binary search version is fasterMatrix Chain MultiplicationO(n³)O(n²)Interval DPTravelling Salesman (bitmask)O(2ⁿ × n²)O(2ⁿ × n)Still exponential but manageable for small nThe general rule: DP trades time for space. You use memory to avoid recomputation. The time complexity equals the number of unique states multiplied by the work done per state.How to Learn and Master Dynamic Programming — Step by StepHere is an honest, structured path to mastery:Step 1 — Get recursion absolutely solid first. DP is memoized recursion at its core. If you cannot write clean recursive solutions confidently, DP will remain confusing. Practice at least 20 pure recursion problems first.Step 2 — Start with the classics. Fibonacci → Climbing Stairs → House Robber → Coin Change. These teach you the core pattern of defining state and transition without overwhelming you.Step 3 — Learn to define state explicitly. Before writing any code, ask: "What does dp[i] represent?" Write it in plain English. "dp[i] = the minimum cost to reach step i." This single habit separates good DP thinkers from struggling ones.Step 4 — Write the recurrence relation before coding. On paper or in a comment. Example: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). If you can write the recurrence, the code writes itself.Step 5 — Master one pattern at a time. Don't jump between knapsack and interval DP in the same week. Spend a few days on each pattern until it feels intuitive.Step 6 — Solve the same problem both ways. Top-down and bottom-up. This builds deep understanding of what DP is actually doing.Step 7 — Optimize space after getting correctness. Many 2D DP solutions can use a single row instead of a full matrix. Learn this optimization after you understand the full solution.Step 8 — Do timed practice under interview conditions. Give yourself 35 minutes per problem. Review what you got wrong. DP is a muscle — it builds with reps.Common Mistakes in Dynamic Programming (And How to Avoid Them)Mistake 1 — Jumping to code before defining state. The most common DP error. Always define what dp[i] or dp[i][j] means before writing a single line of code.Mistake 2 — Wrong base cases. A single wrong base case corrupts every answer built on top of it. Trace through your base cases manually on a tiny example before running code.Mistake 3 — Off-by-one errors in indexing. Whether your dp array is 0-indexed or 1-indexed must be 100% consistent throughout. This causes more bugs in DP than almost anything else.Mistake 4 — Confusing top-down with bottom-up state order. In bottom-up DP, you must ensure that when you compute dp[i], all values it depends on are already filled. If you compute in the wrong order, you get garbage answers.Mistake 5 — Memoizing in the wrong dimension. In 2D problems, some people cache only one dimension when the state actually requires two. Always identify all variables that affect the outcome.Mistake 6 — Using global mutable state in recursion. If you use a shared array and don't clear it between test cases, you'll get wrong answers on subsequent inputs. Always scope your cache correctly.Mistake 7 — Not considering the full state space. In problems like Knapsack, forgetting that the state is (item index, remaining capacity) — not just item index — leads to fundamentally wrong solutions.Mistake 8 — Giving up after not recognizing the pattern immediately. DP problems don't announce themselves. The skill is learning to ask "is there overlapping subproblems here?" on every problem. This takes time. Don't mistake unfamiliarity for inability.Frequently Asked Questions About Dynamic ProgrammingQ: Is Dynamic Programming the same as recursion? Not exactly. Recursion is a technique for breaking problems into smaller pieces. DP is recursion plus memoization — or iterative tabulation. All DP can be written recursively, but not all recursion is DP.Q: What is the difference between DP and Divide and Conquer? Divide and Conquer (like Merge Sort) breaks problems into non-overlapping subproblems. DP is used when subproblems overlap — meaning the same subproblem is solved multiple times in a naive approach.Q: How do I know when NOT to use DP? If the subproblems don't overlap (no repeated computation), greedy or divide-and-conquer may be better. If the problem has no optimal substructure, DP won't give a correct answer.Q: Do I need to memorize DP solutions for interviews? No. You need to recognize patterns and be able to derive the recurrence relation. Memorizing solutions without understanding them will fail you in interviews. Focus on the thinking process.Q: How long does it take to get good at DP? Most people start to feel genuinely comfortable after solving 40–60 varied DP problems with deliberate practice. The first 10 feel impossible. The next 20 feel hard. After 50, patterns start feeling obvious.Q: What programming language is best for DP? Any language works. Python is often used for learning because its dictionaries make memoization trivial. C++ is preferred in competitive programming for its speed. For interviews, use whatever language you're most comfortable in.Q: What is space optimization in DP? Many DP problems only look back one or two rows to compute the current row. In those cases, you can replace an n×m table with just two arrays (or even one), reducing space complexity from O(n×m) to O(m). This is called space optimization or rolling array technique.Q: Can DP be applied to graph problems? Absolutely. Shortest path algorithms like Bellman-Ford are DP. Longest path in a DAG is DP. DP on trees is a rich subfield. Anywhere you have states and transitions, DP can potentially apply.Q: Is Greedy a type of Dynamic Programming? Greedy is related but distinct. Greedy makes locally optimal choices without reconsidering. DP considers all choices and picks the globally optimal one. Some DP solutions reduce to greedy when the structure allows, but they are different techniques.Q: What resources should I use to learn DP? For structured learning: Neetcode.io (organized problem list), Striver's DP Series on YouTube, and the book "Introduction to Algorithms" (CLRS) for theoretical depth. For practice: LeetCode's Dynamic Programming study plan and Codeforces for competitive DP.Final Thoughts — Dynamic Programming Is a SuperpowerDynamic Programming is genuinely one of the most powerful ideas in computer science. It shows up in your GPS, your autocorrect, your streaming video, your bank's risk models, and the AI assistants you talk to daily.The path to mastering it is not memorization. It is developing the habit of asking: can I break this into smaller problems that overlap? And then learning to define state clearly, write the recurrence, and trust the process.Start with Climbing Stairs. Write dp[i] in plain English before every problem. Solve everything twice — top-down and bottom-up. Do 50 problems with genuine reflection, not just accepted solutions.The click moment will come. And when it does, you'll wonder why it ever felt hard.

Dynamic ProgrammingMemoizationTabulationJavaOrigin StoryRichard Bellman

Stack Data Structure in Java: The Complete In-Depth Guide

1. What Is a Stack?A Stack is a linear data structure that stores elements in a sequential order, but with one strict rule — you can only insert or remove elements from one end, called the top.It is one of the simplest yet most powerful data structures in computer science. Its strength comes from its constraint. Because everything happens at one end, the behavior of a stack is completely predictable.The formal definition: A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the element inserted last is the first one to be removed.Here is what a stack looks like visually: ┌──────────┐ │ 50 │ ← TOP (last inserted, first removed) ├──────────┤ │ 40 │ ├──────────┤ │ 30 │ ├──────────┤ │ 20 │ ├──────────┤ │ 10 │ ← BOTTOM (first inserted, last removed) └──────────┘When you push 60 onto this stack, it goes on top. When you pop, 60 comes out first. That is LIFO.2. Real-World AnalogiesBefore writing a single line of code, it helps to see stacks in the real world. These analogies will make the concept permanently stick.A Pile of Plates In a cafeteria, clean plates are stacked on top of each other. You always pick the top plate. You always place a new plate on top. You never reach into the middle. This is a stack.Browser Back Button Every time you visit a new webpage, it gets pushed onto a history stack. When you press the Back button, the browser pops the most recent page off the stack and takes you there. The page you visited first is at the bottom — you only reach it after going back through everything else.Undo Feature in Text Editors When you type in a document and press Ctrl+Z, the most recent action is undone first. That is because every action you perform is pushed onto a stack. Undo simply pops from that stack.Call Stack in Programming When a function calls another function, the current function's state is pushed onto the call stack. When the inner function finishes, it is popped off and execution returns to the outer function. This is the literal stack your programs run on.A Stack of Books Put five books on a table, one on top of another. You can only take the top book without knocking the pile over. That is a stack.3. The LIFO Principle ExplainedLIFO stands for Last In, First Out.It means whatever you put in last is the first thing to come out. This is the exact opposite of a Queue (which is FIFO — First In, First Out).Let us trace through an example step by step:Start: Stack is empty → []Push 10 → [10] (10 is at the top)Push 20 → [10, 20] (20 is at the top)Push 30 → [10, 20, 30] (30 is at the top)Pop → returns 30 (30 was last in, first out) Stack: [10, 20]Pop → returns 20 Stack: [10]Peek → returns 10 (just looks, does not remove) Stack: [10]Pop → returns 10 Stack: [] (stack is now empty)Every single operation happens only at the top. The bottom of the stack is never directly accessible.4. Stack Operations & Time ComplexityA stack supports the following core operations:OperationDescriptionTime Complexitypush(x)Insert element x onto the top of the stackO(1)pop()Remove and return the top elementO(1)peek() / top()Return the top element without removing itO(1)isEmpty()Check if the stack has no elementsO(1)isFull()Check if the stack has reached its capacity (Array only)O(1)size()Return the number of elements in the stackO(1)search(x)Find position of element from top (Java built-in only)O(n)All primary stack operations — push, pop, peek, isEmpty — run in O(1) constant time. This is what makes the stack so efficient. It does not matter whether the stack has 10 elements or 10 million — these operations are always instant.Space complexity for a stack holding n elements is O(n).5. Implementation 1 — Using a Static ArrayThis is the most fundamental way to implement a stack. We use a fixed-size array and a variable called top to track where the top of the stack currently is.How it works:top starts at -1 (stack is empty)On push: increment top, then place the element at arr[top]On pop: return arr[top], then decrement topOn peek: return arr[top] without changing it// StackUsingArray.javapublic class StackUsingArray { private int[] arr; private int top; private int capacity; // Constructor — initialize with a fixed capacity public StackUsingArray(int capacity) { this.capacity = capacity; arr = new int[capacity]; top = -1; } // Push: add element to the top public void push(int value) { if (isFull()) { System.out.println("Stack Overflow! Cannot push " + value); return; } arr[++top] = value; System.out.println("Pushed: " + value); } // Pop: remove and return top element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } return arr[top--]; } // Peek: view the top element without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } // Check if stack is full public boolean isFull() { return top == capacity - 1; } // Return current size public int size() { return top + 1; } // Display all elements public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = top; i >= 0; i--) { System.out.print(arr[i] + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArray stack = new StackUsingArray(5); stack.push(10); stack.push(20); stack.push(30); stack.push(40); stack.push(50); stack.push(60); // This will trigger Stack Overflow stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 10Pushed: 20Pushed: 30Pushed: 40Pushed: 50Stack Overflow! Cannot push 60Stack (top → bottom): 50 40 30 20 10Peek: 50Pop: 50Pop: 40Stack (top → bottom): 30 20 10Size: 3Key Points about Array Implementation:Fixed size — you must declare capacity upfrontVery fast — direct array index accessStack Overflow is possible if capacity is exceededMemory is pre-allocated even if stack is not full6. Implementation 2 — Using an ArrayListAn ArrayList-based stack removes the fixed-size limitation. The ArrayList grows dynamically, so you never have to worry about stack overflow due to capacity.How it works:The end of the ArrayList acts as the topadd() is used for pushremove(size - 1) is used for popget(size - 1) is used for peek// StackUsingArrayList.javaimport java.util.ArrayList;public class StackUsingArrayList { private ArrayList<Integer> list; // Constructor public StackUsingArrayList() { list = new ArrayList<>(); } // Push: add to the end (which is our top) public void push(int value) { list.add(value); System.out.println("Pushed: " + value); } // Pop: remove and return the last element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int top = list.get(list.size() - 1); list.remove(list.size() - 1); return top; } // Peek: view the last element public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return list.get(list.size() - 1); } // Check if stack is empty public boolean isEmpty() { return list.isEmpty(); } // Return size public int size() { return list.size(); } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = list.size() - 1; i >= 0; i--) { System.out.print(list.get(i) + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArrayList stack = new StackUsingArrayList(); stack.push(5); stack.push(15); stack.push(25); stack.push(35); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Is Empty: " + stack.isEmpty()); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 5Pushed: 15Pushed: 25Pushed: 35Stack (top → bottom): 35 25 15 5Peek: 35Pop: 35Pop: 25Stack (top → bottom): 15 5Is Empty: falseSize: 2Key Points about ArrayList Implementation:Dynamic size — grows automatically as neededNo overflow riskSlight overhead compared to raw array due to ArrayList internalsExcellent for most practical use cases7. Implementation 3 — Using a LinkedListA LinkedList-based stack is the most memory-efficient approach when you do not know the stack size in advance. Each element (node) holds data and a pointer to the next node. The head of the LinkedList acts as the top of the stack.How it works:Each node stores a value and a reference to the node below itPush creates a new node and makes it the new headPop removes the head node and returns its valuePeek returns the head node's value without removing it// StackUsingLinkedList.javapublic class StackUsingLinkedList { // Inner Node class private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } private Node top; // Head of the linked list = top of stack private int size; // Constructor public StackUsingLinkedList() { top = null; size = 0; } // Push: create new node and link it to top public void push(int value) { Node newNode = new Node(value); newNode.next = top; // new node points to current top top = newNode; // new node becomes the new top size++; System.out.println("Pushed: " + value); } // Pop: remove and return top node's data public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int value = top.data; top = top.next; // move top pointer to next node size--; return value; } // Peek: return top node's data without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return top.data; } // Check if empty public boolean isEmpty() { return top == null; } // Return size public int size() { return size; } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); Node current = top; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingLinkedList stack = new StackUsingLinkedList(); stack.push(100); stack.push(200); stack.push(300); stack.push(400); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 100Pushed: 200Pushed: 300Pushed: 400Stack (top → bottom): 400 300 200 100Peek: 400Pop: 400Pop: 300Stack (top → bottom): 200 100Size: 2Key Points about LinkedList Implementation:Truly dynamic — each node allocated only when neededNo wasted memory from pre-allocationSlightly more memory per element (each node carries a pointer)Ideal for stacks where size is completely unknown8. Java's Built-in Stack ClassJava provides a ready-made Stack class inside java.util. It extends Vector and is thread-safe by default.// JavaBuiltinStack.javaimport java.util.Stack;public class JavaBuiltinStack { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // Push elements stack.push(10); stack.push(20); stack.push(30); stack.push(40); System.out.println("Stack: " + stack); // Peek — look at top without removing System.out.println("Peek: " + stack.peek()); // Pop — remove top System.out.println("Pop: " + stack.pop()); System.out.println("After pop: " + stack); // Search — returns 1-based position from top System.out.println("Search 20: position " + stack.search(20)); // isEmpty System.out.println("Is Empty: " + stack.isEmpty()); // Size System.out.println("Size: " + stack.size()); }}```**Output:**```Stack: [10, 20, 30, 40]Peek: 40Pop: 40After pop: [10, 20, 30]Search 20: position 2Is Empty: falseSize: 3Important Note: In modern Java development, it is often recommended to use Deque (specifically ArrayDeque) instead of Stack for better performance, since Stack is synchronized and carries the overhead of Vector.// Using ArrayDeque as a stack (modern preferred approach)import java.util.ArrayDeque;import java.util.Deque;public class ModernStack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // pushes to front stack.push(20); stack.push(30); System.out.println("Top: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Stack: " + stack); }}9. Comparison of All ImplementationsFeatureArrayArrayListLinkedListJava StackArrayDequeSizeFixedDynamicDynamicDynamicDynamicStack Overflow RiskYesNoNoNoNoMemory UsagePre-allocatedAuto-growsPer-node overheadAuto-growsAuto-growsPush TimeO(1)O(1) amortizedO(1)O(1)O(1)Pop TimeO(1)O(1)O(1)O(1)O(1)Peek TimeO(1)O(1)O(1)O(1)O(1)Thread SafeNoNoNoYesNoBest ForKnown size, max speedGeneral useUnknown/huge sizeLegacy codeModern Java10. Advantages & DisadvantagesAdvantagesAdvantageExplanationSimple to implementVery few rules and operations to worry aboutO(1) operationsPush, pop, and peek are all constant timeMemory efficientNo extra pointers needed (array-based)Supports recursionThe call stack is itself a stackEasy undo/redoNatural fit for reversible action trackingBacktrackingPerfectly suited for maze, puzzle, and game solvingExpression evaluationPowers compilers and calculatorsDisadvantagesDisadvantageExplanationLimited accessCannot access elements in the middle directlyFixed size (array)Array-based stacks overflow if size is exceededNo random accessYou cannot do stack[2] — only top is accessibleMemory waste (array)Pre-allocated array wastes space if underusedNot suitable for all problemsMany problems need queues, trees, or graphs insteadStack overflow in recursionVery deep recursion can overflow the JVM call stack11. Real-World Use Cases of StackUnderstanding when to use a stack is just as important as knowing how to implement one. Here is where stacks show up in real software:Function Call Management (Call Stack) Every time your Java program calls a method, the JVM pushes that method's frame onto the call stack. When the method returns, the frame is popped. This is why you see "StackOverflowError" when you write infinite recursion.Undo and Redo Operations Text editors, image editors (Photoshop), and IDEs use two stacks — one for undo history and one for redo history. Every action pushes onto the undo stack. Ctrl+Z pops from it and pushes to the redo stack.Browser Navigation Your browser maintains a back-stack and a forward-stack. Visiting a new page pushes to the back-stack. Pressing Back pops from it and pushes to the forward-stack.Expression Evaluation and Conversion Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notations. For example: 3 + 4 * 2 must be evaluated considering operator precedence — this is done with a stack.Balanced Parentheses Checking Linters, compilers, and IDEs use stacks to check if brackets are balanced: {[()]} is valid, {[(])} is not.Backtracking Algorithms Maze solving, N-Queens, Sudoku solvers, and depth-first search all use stacks (explicitly or via recursion) to backtrack to previous states when a path fails.Syntax Parsing Compilers parse source code using stacks to match opening and closing constructs like if/else, try/catch, { and }.12. Practice Problems with Full SolutionsHere is where things get really interesting. These problems will sharpen your stack intuition and prepare you for coding interviews.Problem 1 — Reverse a String Using a StackDifficulty: EasyProblem: Write a Java program to reverse a string using a Stack.Approach: Push every character of the string onto a stack, then pop them all. Since LIFO reverses the order, the characters come out reversed.// ReverseString.javaimport java.util.Stack;public class ReverseString { public static String reverse(String str) { Stack<Character> stack = new Stack<>(); // Push all characters for (char c : str.toCharArray()) { stack.push(c); } // Pop all characters to build reversed string StringBuilder reversed = new StringBuilder(); while (!stack.isEmpty()) { reversed.append(stack.pop()); } return reversed.toString(); } public static void main(String[] args) { System.out.println(reverse("hello")); // olleh System.out.println(reverse("java")); // avaj System.out.println(reverse("racecar")); // racecar (palindrome) System.out.println(reverse("datastructure")); // erutcurtasatad }}Problem 2 — Check Balanced ParenthesesDifficulty: Easy–MediumProblem: Given a string containing (, ), {, }, [, ], determine if the brackets are balanced.Approach: Push every opening bracket onto the stack. When you see a closing bracket, check if it matches the top of the stack. If it does, pop. If it does not, the string is unbalanced.// BalancedParentheses.javaimport java.util.Stack;public class BalancedParentheses { public static boolean isBalanced(String expr) { Stack<Character> stack = new Stack<>(); for (char c : expr.toCharArray()) { // Push all opening brackets if (c == '(' || c == '{' || c == '[') { stack.push(c); } // For closing brackets, check the top of stack else if (c == ')' || c == '}' || c == ']') { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == '}' && top != '{') return false; if (c == ']' && top != '[') return false; } } // Stack must be empty at the end for a balanced expression return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isBalanced("{[()]}")); // true System.out.println(isBalanced("{[(])}")); // false System.out.println(isBalanced("((()))")); // true System.out.println(isBalanced("{]")); // false System.out.println(isBalanced("")); // true (empty is balanced) }}Problem 3 — Reverse a Stack (Without Extra Data Structure)Difficulty: Medium–HardProblem: Reverse all elements of a stack using only recursion — no array or extra stack allowed.Approach: This is a classic recursion problem. You need two recursive functions:insertAtBottom(stack, item) — inserts an element at the very bottom of the stackreverseStack(stack) — pops all elements, reverses, and uses insertAtBottom to rebuild// ReverseStack.javaimport java.util.Stack;public class ReverseStack { // Insert an element at the bottom of the stack public static void insertAtBottom(Stack<Integer> stack, int item) { if (stack.isEmpty()) { stack.push(item); return; } int top = stack.pop(); insertAtBottom(stack, item); stack.push(top); } // Reverse the stack using insertAtBottom public static void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); reverseStack(stack); // reverse the remaining stack insertAtBottom(stack, top); // insert popped element at bottom } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println("Before: " + stack); // [1, 2, 3, 4, 5] reverseStack(stack); System.out.println("After: " + stack); // [5, 4, 3, 2, 1] }}Problem 4 — Evaluate a Postfix ExpressionDifficulty: MediumProblem: Evaluate a postfix (Reverse Polish Notation) expression. Example: "2 3 4 * +" should return 14 because it is 2 + (3 * 4).Approach: Scan left to right. If you see a number, push it. If you see an operator, pop two numbers, apply the operator, and push the result.// PostfixEvaluation.javaimport java.util.Stack;public class PostfixEvaluation { public static int evaluate(String expression) { Stack<Integer> stack = new Stack<>(); String[] tokens = expression.split(" "); for (String token : tokens) { // If it's a number, push it if (token.matches("-?\\d+")) { stack.push(Integer.parseInt(token)); } // If it's an operator, pop two and apply else { int b = stack.pop(); // second operand int a = stack.pop(); // first operand switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } } return stack.pop(); } public static void main(String[] args) { System.out.println(evaluate("2 3 4 * +")); // 14 → 2 + (3*4) System.out.println(evaluate("5 1 2 + 4 * + 3 -")); // 14 → 5+((1+2)*4)-3 System.out.println(evaluate("3 4 +")); // 7 }}Problem 5 — Next Greater ElementDifficulty: MediumProblem: For each element in an array, find the next greater element to its right. If none exists, output -1.Example: Input: [4, 5, 2, 10, 8] → Output: [5, 10, 10, -1, -1]Approach: Iterate right to left. Maintain a stack of candidates. For each element, pop all stack elements that are smaller than or equal to it — they can never be the answer for any element to the left. The top of the stack (if not empty) is the next greater element.// NextGreaterElement.javaimport java.util.Stack;import java.util.Arrays;public class NextGreaterElement { public static int[] nextGreater(int[] arr) { int n = arr.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); // stores elements, not indices // Traverse from right to left for (int i = n - 1; i >= 0; i--) { // Pop elements smaller than or equal to current while (!stack.isEmpty() && stack.peek() <= arr[i]) { stack.pop(); } // Next greater element result[i] = stack.isEmpty() ? -1 : stack.peek(); // Push current element for future comparisons stack.push(arr[i]); } return result; } public static void main(String[] args) { int[] arr1 = {4, 5, 2, 10, 8}; System.out.println(Arrays.toString(nextGreater(arr1))); // [5, 10, 10, -1, -1] int[] arr2 = {1, 3, 2, 4}; System.out.println(Arrays.toString(nextGreater(arr2))); // [3, 4, 4, -1] int[] arr3 = {5, 4, 3, 2, 1}; System.out.println(Arrays.toString(nextGreater(arr3))); // [-1, -1, -1, -1, -1] }}Problem 6 — Sort a Stack Using RecursionDifficulty: HardProblem: Sort a stack in ascending order (smallest on top) using only recursion — no loops, no extra data structure.// SortStack.javaimport java.util.Stack;public class SortStack { // Insert element in correct sorted position public static void sortedInsert(Stack<Integer> stack, int item) { if (stack.isEmpty() || item > stack.peek()) { stack.push(item); return; } int top = stack.pop(); sortedInsert(stack, item); stack.push(top); } // Sort the stack public static void sortStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); sortStack(stack); // sort remaining sortedInsert(stack, top); // insert top in sorted position } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(34); stack.push(3); stack.push(31); stack.push(98); stack.push(92); stack.push(23); System.out.println("Before sort: " + stack); sortStack(stack); System.out.println("After sort: " + stack); // smallest on top }}13. Summary & Key TakeawaysA stack is a simple, elegant, and powerful data structure. Here is everything in one place:What it is: A linear data structure that follows LIFO — Last In, First Out.Core operations: push (add to top), pop (remove from top), peek (view top), isEmpty — all in O(1) time.Three ways to implement it in Java:Array-based: fast, fixed size, risk of overflowArrayList-based: dynamic, easy, slightly more overheadLinkedList-based: truly dynamic, memory-efficient per-element, best for unknown sizesWhen to use it:Undo/redo systemsBrowser navigationBalancing brackets and parenthesesEvaluating mathematical expressionsBacktracking problemsManaging recursive function callsDepth-first searchWhen NOT to use it:When you need random access to elementsWhen insertion/deletion is needed from both ends (use Deque)When you need to search efficiently (use HashMap or BST)Modern Java recommendation: Prefer ArrayDeque over the legacy Stack class for non-thread-safe scenarios. Use Stack only when you need synchronized access.The stack is one of those data structures that once you truly understand, you start seeing it everywhere — in your browser, in your IDE, in recursive algorithms, and deep within the operating system itself.This article covered everything from the fundamentals of the Stack data structure to multiple Java implementations, time complexity analysis, real-world applications, and six practice problems of increasing difficulty. Bookmark it as a reference and revisit the practice problems regularly — they are the real test of your understanding.

DataStructuresJavaStackDataStructureLIFO