Search Blogs

Showing results for "Frequency Count"

Found 19 results

LeetCode 1189: Maximum Number of Balloons – Java HashMap and Frequency Counting Solution

IntroductionLeetCode 1189, Maximum Number of Balloons, is a beginner-friendly string and frequency-counting problem that teaches an important interview concept:Count only the characters that matter and determine the limiting factor.The challenge is to find how many times the word "balloon" can be formed using the characters available in a given string. Each character can be used at most once.This problem is an excellent introduction to:HashMap frequency countingCharacter frequency analysisGreedy counting techniquesFinding bottleneck charactersProblem StatementProblem Link -: Maximum Number of BalloonsGiven a string:textDetermine the maximum number of times the word:ballooncan be formed.Each character from the original string can only be used once.Return the maximum number of complete instances of the word.Example 1Inputtext = "nlaebolko"Output1ExplanationAvailable characters:b = 1a = 1l = 2o = 2n = 1Exactly one "balloon" can be formed.Example 2Inputtext = "loonbalxballpoon"Output2ExplanationThe string contains enough characters to create:balloonballoonTwo complete words can be formed.Example 3Inputtext = "leetcode"Output0ExplanationThe required characters for "balloon" are not all present.Key ObservationThe target word is:balloonCharacter requirements:CharacterRequired Countb1a1l2o2n1Notice:l appears twiceo appears twiceThese characters become important because they require more occurrences than the others.Approach 1: Simulate Building BalloonsIdeaCount occurrences of relevant characters.Continuously check whether a complete "balloon" can be formed.If possible:Increment answer.Remove required characters.Repeat until impossible.Java Solutionclass Solution { public int maxNumberOfBalloons(String text) { HashMap<Character, Integer> mp = new HashMap<>(); for (int i = 0; i < text.length(); i++) { if (text.charAt(i) == 'b' || text.charAt(i) == 'a' || text.charAt(i) == 'l' || text.charAt(i) == 'o' || text.charAt(i) == 'n') { mp.put(text.charAt(i), mp.getOrDefault(text.charAt(i), 0) + 1); } } int ans = 0; for (int i = 0; i < text.length(); i++) { if (mp.containsKey('b') && mp.containsKey('a') && mp.containsKey('l') && mp.containsKey('o') && mp.containsKey('n')) { if (mp.get('b') > 0 && mp.get('a') > 0 && mp.get('l') >= 2 && mp.get('o') >= 2 && mp.get('n') > 0) { ans++; mp.put('b', mp.get('b') - 1); mp.put('a', mp.get('a') - 1); mp.put('l', mp.get('l') - 2); mp.put('o', mp.get('o') - 2); mp.put('n', mp.get('n') - 1); } } } return ans; }}Dry RunInputtext = "loonbalxballpoon"Frequency Countb = 2a = 2l = 4o = 4n = 2First BalloonConsume:b = 1a = 1l = 2o = 2n = 1Answer:1Second BalloonConsume again:b = 0a = 0l = 0o = 0n = 0Answer:2No more balloons can be formed.Final result:2Can We Optimize Further?Yes.Your solution repeatedly removes characters to form balloons.But we don't actually need simulation.Instead, we can directly calculate the maximum number of balloons.Approach 2: Frequency Division (Optimal)Key InsightSuppose frequencies are:b = 5a = 3l = 8o = 4n = 2Since:balloon = b×1 a×1 l×2 o×2 n×1Possible balloons:b → 5a → 3l → 8/2 = 4o → 4/2 = 2n → 2The smallest value determines the answer:min(5,3,4,2,2) = 2Therefore:answer =min(freq['b'],freq['a'],freq['l']/2,freq['o']/2,freq['n'])Optimized Java Solutionclass Solution { public int maxNumberOfBalloons(String text) { int[] freq = new int[26]; for (char ch : text.toCharArray()) { freq[ch - 'a']++; } return Math.min( Math.min(freq['b' - 'a'], freq['a' - 'a']), Math.min( freq['l' - 'a'] / 2, Math.min( freq['o' - 'a'] / 2, freq['n' - 'a'] ) ) ); }}Approach 3: HashMap + Minimum FormulaIf you prefer HashMaps:HashMap<Character,Integer> map = new HashMap<>();Count frequencies and apply the same minimum formula.This keeps the logic intuitive while avoiding repeated simulation.Complexity AnalysisSimulation ApproachTime ComplexityO(n)The second loop runs at most n times.Space ComplexityO(1)Only a few characters are stored.Optimal Frequency Division ApproachTime ComplexityO(n)Single traversal.Space ComplexityO(1)Fixed-size frequency array.Interview DiscussionAn interviewer may ask:Why divide l and o by 2?Because the word contains:balloonand requires:2 l's2 o'sfor every single occurrence.Therefore:available balloons from l = lCount / 2available balloons from o = oCount / 2Common MistakesForgetting Duplicate LettersMany candidates count:balonand forget that:l = 2o = 2are required.Using Total Frequency OnlyHaving:l = 1does not allow even one balloon.Simulating UnnecessarilyWhile simulation works, the minimum-frequency formula is cleaner and more efficient.Key TakeawaysThis problem is based on frequency counting.Only five characters matter:balonCharacters l and o require special handling because they appear twice.The optimal solution uses a frequency array and a minimum calculation.Understanding bottleneck resources is a common interview pattern.ConclusionLeetCode 1189: Maximum Number of Balloons is a simple but powerful frequency-counting problem. While a simulation-based approach works correctly, the most elegant solution comes from recognizing that the answer is determined by the limiting character count.Mastering this pattern will help you solve many string, HashMap, and counting-based interview questions efficiently.

LeetcodeEasyJavaHashMapFrequency Count

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

LeetCode 387: First Unique Character in a String – Java HashMap Solution Explained

IntroductionLeetCode 387 – First Unique Character in a String is one of the most common beginner-friendly string and hashing interview problems.This problem helps developers understand:Frequency countingHashMap usageString traversalCharacter manipulationEfficient lookup techniquesIt is frequently asked in coding interviews because it tests both:Logical thinkingTime complexity optimizationProblem Link🔗 https://leetcode.com/problems/first-unique-character-in-a-string/Problem StatementGiven a string:sReturn:Index of the first non-repeating characterIf no unique character exists:Return -1Example 1Inputs = "leetcode"Output0Explanation:'l'appears only once and is the first unique character.Example 2Inputs = "loveleetcode"Output2Explanation:'v'is the first character that appears only once.Example 3Inputs = "aabb"Output-1All characters repeat.IntuitionTo identify the first unique character:We first need to know:How many times every character appearsA HashMap is perfect for frequency counting.After counting:We traverse the string again and return the first character whose frequency is:1Brute Force ApproachIdeaFor every character:Traverse the entire stringCount occurrencesReturn the first character with count = 1Brute Force ComplexityTime ComplexityO(N²)because nested traversal is required.Space ComplexityO(1)Optimized HashMap ApproachIdeaUse a HashMap to store:character → frequencyThen scan the string again.The first character with frequency:1is the answer.Java Solutionclass Solution {public int firstUniqChar(String s) {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 < s.length(); i++) {if(mp.get(s.charAt(i)) == 1) {return i;}}return -1;}}Cleaner Optimized Versionclass Solution {public int firstUniqChar(String s) {int[] freq = new int[26];for(char ch : s.toCharArray()) {freq[ch - 'a']++;}for(int i = 0; i < s.length(); i++) {if(freq[s.charAt(i) - 'a'] == 1) {return i;}}return -1;}}Why This WorksThe algorithm works in two passes.First PassStore frequency of every character.Example:"leetcode"Frequency map:l → 1e → 3t → 1c → 1o → 1d → 1Second PassTraverse string from left to right.The first character whose frequency equals:1is returned.Dry RunInputs = "loveleetcode"Step 1: Frequency Countingl → 2o → 2v → 1e → 4t → 1c → 1d → 1Step 2: Traverse AgainIndex 0:'l' → frequency 2Index 1:'o' → frequency 2Index 2:'v' → frequency 1Return:2Time Complexity AnalysisOptimized HashMap SolutionTime ComplexityO(N)because string traversal happens twice.Space ComplexityO(1)Only lowercase English letters exist.Maximum storage remains fixed.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashMap / Frequency ArrayO(N)O(1)Interview ExplanationIn interviews, explain:We use a frequency map to count occurrences of every character. Then we scan the string again to locate the first character whose frequency is exactly one.This demonstrates:Hashing knowledgeFrequency countingEfficient lookup usageOptimization skillsCommon Mistakes1. Returning Character Instead of IndexThe problem asks for:indexnot the character itself.2. Using Nested LoopsNested traversal increases complexity unnecessarily.3. Forgetting Second TraversalHashMap only stores frequencies.You still need:left-to-right traversalto find the first unique character.FAQsQ1. Why use HashMap?Because frequency lookup becomes very efficient.Q2. Can we use arrays instead?Yes.Since only lowercase letters exist:int[26]works perfectly.Q3. Why traverse the string twice?First pass counts frequency.Second pass preserves original order.Q4. Is this problem important for interviews?Yes.It is one of the most common hashing interview questions.Related ProblemsPractice these next:Valid AnagramRansom NoteCount the Number of Special CharactersConclusionLeetCode 387 is an excellent beginner-level problem for learning:Frequency countingHashMap usageString traversalEfficient lookup techniquesThe key insight is:Count character frequencies first, then find the first character with frequency equal to one.This pattern is widely used in many real interview problems involving strings and hashing.

LeetCodeJavaHashMapStringEasy

LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

IntroductionLeetCode 2784 – Check if Array is Good is a beginner-friendly array and hashing problem that tests your understanding of:Frequency countingHashMap usageArray validationPermutation logicEdge case handlingAlthough the problem looks simple initially, many candidates fail because they misunderstand the exact structure of the required array.This problem is commonly asked to test:Attention to detailLogical validationCounting techniquesHashing fundamentalsProblem Link🔗 https://leetcode.com/problems/check-if-array-is-good/Problem StatementAn array is considered good if it is a permutation of:base[n] = [1, 2, 3, ..., n-1, n, n]Meaning:Numbers from:1 to n-1appear exactly once.Number:nappears exactly twice.You need to return:trueif the given array is good, otherwise:falseUnderstanding the PatternA valid good array must follow:[1, 2, 3, ..., n-1, n, n]Examples:[1,1][1,2,3,3][1,2,3,4,4]Invalid examples:[1,2,2][1,2,4,4][1,1,2,2]Key ObservationsObservation 1The maximum element determines:nObservation 2Array size must be:n + 1because:1 to n-1 => n-1 elementsn appears twice => 2 elementsTotal = n + 1Observation 3Frequency conditions:NumberFrequency1 to n-1Exactly 1nExactly 2Brute Force ApproachIdeaSort arrayCompare with expected arrayReturn resultBrute Force AlgorithmStep 1Find maximum element:nStep 2Create expected array:[1,2,3,...,n,n]Step 3Sort both arrays and compare.Brute Force ComplexityTime ComplexityO(N log N)due to sorting.Space ComplexityO(N)Optimized HashMap ApproachInstead of sorting:Count frequencies directlyValidate conditionsThis makes the solution faster and cleaner.Intuition Behind HashMap SolutionWe store frequency of every number.Then verify:Maximum element appears twiceEvery other number appears onceArray length equals:max + 1Java HashMap Solutionclass Solution { public boolean isGood(int[] nums) { if(nums.length == 1) return false; int maxElement = Integer.MIN_VALUE; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { map.put(nums[i], map.getOrDefault(nums[i], 0) + 1); maxElement = Math.max(maxElement, nums[i]); } int n = maxElement; if(nums.length != n + 1) { return false; } for(int i = 1; i <= n; i++) { if(!map.containsKey(i)) { return false; } if(i == n) { if(map.get(i) != 2) return false; } else { if(map.get(i) != 1) return false; } } return true; }}Dry RunInputnums = [1,3,3,2]Step 1 – Find MaximumMaximum element:3So:n = 3Step 2 – Length CheckExpected length:n + 1 = 4Actual length:4Valid.Step 3 – Frequency CountFrequency map:NumberCount112132Step 4 – Validate ConditionsNumbers 1 and 2 appear once ✅Number 3 appears twice ✅Return:trueEdge CasesCase 1[1]Invalid because:base[1] = [1,1]Case 2[1,1]Valid.Case 3[1,2,2]Invalid because:n = 2Expected:[1,2,2]Actually valid.Case 4[3,4,4,1,2,1]Invalid because:length != max + 1Optimized Alternative Using SortingAnother clean solution:Sort arrayVerify:nums[i] == i + 1for all except last.Last two elements should be equal.Java Sorting Solutionclass Solution { public boolean isGood(int[] nums) { Arrays.sort(nums); int n = nums.length - 1; for(int i = 0; i < n; i++) { if(nums[i] != i + 1) return false; } return nums[n] == n; }}Time Complexity AnalysisHashMap SolutionTime ComplexityO(N)Space ComplexityO(N)Sorting SolutionTime ComplexityO(N log N)Space ComplexityO(1)excluding sorting overhead.HashMap vs SortingApproachTime ComplexitySpace ComplexityHashMapO(N)O(N)SortingO(N log N)O(1)Interview ExplanationIn interviews, explain:A good array must follow the exact pattern [1,2,3,...,n,n]. The maximum element determines n, and frequency counting helps verify whether all required numbers appear correctly.This demonstrates strong understanding of:Frequency countingValidation logicEdge case handlingCommon Mistakes1. Forgetting Length CheckAlways verify:length == max + 12. Ignoring Missing NumbersArray must contain:1 to ncompletely.3. Wrong Frequency ValidationOnly maximum element should appear twice.All others must appear once.FAQsQ1. Why does maximum element determine n?Because:base[n]always ends with:n,nQ2. Why should array size be n + 1?Because:1 to n-1 => n-1 elementsn repeated twice => 2 elementsTotal = n+1Q3. Which approach is better?HashMap solution is faster.Sorting solution is simpler.Q4. Is this problem important for interviews?Yes.It tests:HashingValidation logicEdge case thinkingRelated ProblemsAfter mastering this problem, practice:Contains DuplicateFind All Duplicates in an ArrayValid AnagramConclusionLeetCode 2784 is a great beginner-friendly hashing problem.It teaches:Frequency countingValidation logicHashMap usageEdge case handlingThe key insight is:A good array must exactly match the structure [1,2,3,...,n,n].Once you understand this pattern, the problem becomes straightforward and easy to implement.

LeetCodeJavaHashMapArrayFrequency CountEasy

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

LeetCode 2657: Find the Prefix Common Array of Two Arrays – Java Hashing Solution Explained

IntroductionLeetCode 2657 – Find the Prefix Common Array of Two Arrays is an interesting prefix and hashing problem that tests your understanding of:Prefix processingHashingFrequency countingSet operationsArray traversalAt first glance, the problem may look confusing because of the term:Prefix Common ArrayBut once you understand the meaning of prefixes and common elements, the problem becomes straightforward.This problem is useful for improving:Prefix-based thinkingHashing intuitionOptimization skillsInterview problem-solving abilityProblem Link🔗 Find the prefix Common Array of Two ArraysProblem StatementYou are given two permutations:A and BBoth arrays contain numbers:1 to nexactly once.You need to create an array:Cwhere:C[i]represents:Count of numbers present in both arrays from index 0 to i.Understanding Prefix Common ArraySuppose:A = [1,3,2,4]B = [3,1,2,4]Prefix at Index 0A Prefix = [1]B Prefix = [3]Common numbers:NoneSo:C[0] = 0Prefix at Index 1A Prefix = [1,3]B Prefix = [3,1]Common numbers:1, 3So:C[1] = 2Final Output[0,2,3,4]Key ObservationBoth arrays are permutations.This means:Every number appears exactly once.Once a number appears in both prefixes, it remains common forever.This simplifies the logic significantly.Brute Force ApproachIntuitionFor every index:Build prefixesCompare elementsCount common numbersBrute Force AlgorithmFor each index:Traverse all previous elementsCheck whether numbers exist in both prefixesCount matchesBrute Force ComplexityTime ComplexityO(N²)because for every index we may scan previous elements.Space ComplexityO(N)Understanding ApproachThis approach uses:HashMapPrefix trackingCounting common valuesThe idea is:Store prefix elements from BTraverse A prefixCount matching numbersThis works because prefixes gradually expand.Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int j = 0; int[] ans = new int[A.length]; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < A.length; i++) { map.put(B[i], i); int counter = 0; int c = 0; for(int a : map.keySet()) { if(map.containsKey(A[c])) { counter++; } c++; } ans[j] = counter; j++; } return ans; }}Better Optimized ApproachWe can solve this more cleanly using:HashSetor frequency counting.Optimized IntuitionAt every index:Add A[i]Add B[i]Track which numbers appearedIf a number appears in both arrays, increase common countBest Optimized Approach Using Frequency ArrayBecause values are from:1 to nwe can use a frequency array.Optimized Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; int[] ans = new int[n]; int[] freq = new int[n + 1]; int common = 0; for(int i = 0; i < n; i++) { freq[A[i]]++; if(freq[A[i]] == 2) common++; freq[B[i]]++; if(freq[B[i]] == 2) common++; ans[i] = common; } return ans; }}Why Does This Work?Every number appears once in A and once in B.So:First appearance → frequency becomes 1Second appearance → frequency becomes 2When frequency becomes:2it means the number has appeared in both prefixes.So we increase:commonDry RunInputA = [1,3,2,4]B = [3,1,2,4]Step 1Index:0Add:1 and 3Frequencies:1 → 13 → 1No common elements.ans[0] = 0Step 2Add:3 and 1Frequencies:1 → 23 → 2Two common elements found.ans[1] = 2Step 3Add:2 and 2Frequency:2 → 2Common becomes:3ans[2] = 3Step 4Add:4 and 4Frequency:4 → 2Common becomes:4ans[3] = 4Final Output[0,2,3,4]Time Complexity AnalysisTime ComplexityO(N²)Nested traversal inside loop.Space ComplexityO(N)Optimized Frequency ApproachTime ComplexityO(N)Single traversal.Space ComplexityO(N)Frequency array.HashMap vs Frequency ArrayApproachTime ComplexitySpace ComplexityHashMapO(N²)O(N)Frequency ArrayO(N)O(N)Interview ExplanationIn interviews, explain:Since both arrays are permutations, every number appears exactly twice overall — once in A and once in B. Using frequency counting, whenever a number’s frequency becomes 2, it means it has appeared in both prefixes.This demonstrates:Prefix understandingOptimization thinkingHashing skillsCommon Mistakes1. Recalculating Common Elements Every TimeThis causes:O(N²)complexity.2. Forgetting Arrays Are PermutationsThis special condition allows frequency optimization.3. Incorrect Prefix LogicRemember:Prefix means elements from 0 to i.FAQsQ1. Why is this called Prefix Common Array?Because:C[i]stores common elements between prefixes ending at index:iQ2. Why does frequency 2 mean common?Because every number appears once in each array.Q3. Which approach is best?Frequency array approach is the most optimized.Q4. Is this problem important for interviews?Yes.It tests:Prefix logicHashingOptimizationArray traversalRelated ProblemsAfter mastering this problem, practice:Intersection of Two ArraysIntersection of Two Arrays IIContains DuplicateSubarray Sum Equals KPrefix SumFind the Difference of Two ArraysConclusionLeetCode 2657 is an excellent prefix and hashing problem.It teaches:Prefix processingFrequency countingOptimization techniquesHashing fundamentalsThe key insight is:A number becomes common exactly when its frequency becomes 2.Once you understand this observation, the optimized solution becomes very simple and efficient.

LeetCodePrefix Common ArrayJavaHashMapHashSetArrayPrefixArrayMedium

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

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

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

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

StringMath TrickASCIIBit ManipulationLeetCodeEasy

LeetCode 1833: Maximum Ice Cream Bars – Java Greedy & Counting Sort Solution Explained

LeetCode 1833: Maximum Ice Cream Bars – Java Greedy Solution ExplainedBuy the Maximum Number of Ice Cream Bars Using Sorting and Greedy StrategyIntroductionLeetCode 1833, Maximum Ice Cream Bars, is a classic Greedy Algorithm problem that teaches an important optimization principle:When you want to maximize the number of items purchased with a limited budget, always buy the cheapest items first.Although the problem statement specifically mentions solving it using Counting Sort, understanding the Greedy approach first helps build intuition before moving to the optimized counting-sort solution.In this article, we'll cover:Problem intuitionGreedy strategySorting-based solutionCounting Sort optimizationDry run examplesComplexity analysisInterview insightsProblem StatementProblem Link -: Maximum Ice Cream BarsA boy has a fixed number of coins.You are given:costs[i]which represents the price of the ith ice cream bar.The boy can purchase ice cream bars in any order.Your task is to determine the maximum number of ice cream bars that can be bought without exceeding the available coins.Example 1Inputcosts = [1,3,2,4,1]coins = 7Output4ExplanationSort the costs:[1,1,2,3,4]Buy in order:1 → remaining 61 → remaining 52 → remaining 33 → remaining 0Total bars purchased:4Example 2Inputcosts = [10,6,8,7,7,8]coins = 5Output0Even the cheapest ice cream costs more than the available coins.Example 3Inputcosts = [1,6,3,1,2,5]coins = 20Output6The boy can purchase every ice cream bar.Key ObservationSuppose you have:Coins = 10and:Costs = [1,2,8]Buying:8 firstallows only:8 + 1 = 9Total bars:2But buying cheapest first:1 + 2 + 8 = 11Not possible.Try:1 + 2 = 3Still leaves room for more purchases in many cases.To maximize quantity:Always buy the cheapest available ice cream first.This immediately suggests a Greedy strategy.Approach 1: Sorting + GreedyStepsSort the array.Buy ice creams from cheapest to most expensive.Stop when coins run out.Return the count.Java Solutionclass Solution { public int maxIceCream(int[] costs, int coins) { Arrays.sort(costs); int count = 0; for (int cost : costs) { if (coins >= cost) { coins -= cost; count++; } } return count; }}Dry RunInputcosts = [1,3,2,4,1]coins = 7After Sorting[1,1,2,3,4]Purchase ProcessBuy first:coins = 7 - 1 = 6count = 1Buy second:coins = 6 - 1 = 5count = 2Buy third:coins = 5 - 2 = 3count = 3Buy fourth:coins = 3 - 3 = 0count = 4Cannot buy:4Final answer:4Why Greedy WorksThe goal is:Maximize quantitynot:Maximize money spentChoosing a more expensive ice cream earlier can only reduce the number of future purchases.Therefore:Picking the cheapest available option is always optimal.This makes Greedy the correct strategy.Follow-Up: Counting Sort SolutionThe problem explicitly asks:You must solve it using Counting Sort.Why?Because:1 <= costs[i] <= 100000The cost values have a bounded range.Instead of sorting:O(n log n)we can count frequencies.Counting Sort ApproachStep 1Create frequency array.int[] freq = new int[100001];Step 2Count occurrences.for (int cost : costs) { freq[cost]++;}Step 3Process costs from smallest to largest.for (int price = 1; price <= 100000; price++) { while (freq[price] > 0 && coins >= price) { coins -= price; freq[price]--; count++; }}Optimized Counting Sort Solutionclass Solution { public int maxIceCream(int[] costs, int coins) { int[] freq = new int[100001]; for (int cost : costs) { freq[cost]++; } int count = 0; for (int price = 1; price <= 100000; price++) { while (freq[price] > 0 && coins >= price) { coins -= price; freq[price]--; count++; } } return count; }}Complexity AnalysisSorting SolutionTime ComplexityO(n log n)Space ComplexityO(1)(ignoring sorting implementation details)Counting Sort SolutionTime ComplexityO(n + 100000)Effectively linear.Space ComplexityO(100000)for the frequency array.Which Solution Should You Use?ApproachTimeSpaceSorting + GreedyO(n log n)O(1)Counting SortO(n + 100000)O(100000)For interviews:Explain the Greedy idea first.Mention Sorting solution.Then discuss Counting Sort because the problem explicitly requires it.This demonstrates both problem-solving ability and optimization awareness.Common MistakesMistake 1Buying expensive bars first.Reduces total quantity purchased.Mistake 2Stopping after a single unaffordable item in an unsorted array.Always sort or process costs in increasing order.Mistake 3Ignoring the Counting Sort requirement.The online judge may accept sorting, but interviewers may specifically ask for the linear-time optimization.Key TakeawaysThe problem is based on Greedy selection.To maximize purchases, buy the cheapest items first.Sorting provides a simple solution.Counting Sort satisfies the problem's follow-up requirement.Greedy works because every expensive purchase reduces future buying power.Counting Sort improves performance when value ranges are bounded.ConclusionLeetCode 1833: Maximum Ice Cream Bars is an excellent Greedy Algorithm problem that demonstrates how local optimal choices can lead to a globally optimal solution.The sorting-based approach is intuitive and easy to implement, while the counting-sort optimization leverages the bounded range of costs to achieve near-linear performance.Understanding both approaches prepares you not only for coding interviews but also for real-world optimization problems involving budgets, resources, and constrained selections.

LeetCodeMediumJavaSortingGreedy ApproachCounting Sort

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

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

LeetCodeEasyTwo PointerArrayJava

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

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

Sort Colors

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

LeetCodeMediumTwo PointerDutchman Flag Algorithm

Max Consecutive Ones III – Sliding Window with Limited Flips

IntroductionLeetCode 1004: Max Consecutive Ones III is a classic sliding window problem that challenges your understanding of arrays, window manipulation, and frequency counting.The goal is to find the longest subarray of consecutive 1's in a binary array if you are allowed to flip at most K zeros to 1’s.This problem is an excellent example of transforming a brute-force solution into a linear-time efficient approach using the sliding window pattern.If you’d like to try solving the problem first, you can attempt it here: Try the problem on LeetCode: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A binary array nums containing only 0's and 1'sAn integer k representing the maximum number of zeros you can flipYou need to return the length of the longest contiguous subarray of 1's after flipping at most k zeros.Examples:Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Output: 6Explanation: Flip two zeros to get [1,1,1,0,0,1,1,1,1,1,1].Longest consecutive ones = 6.Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3Output: 10Explanation: Flip three zeros to get longest consecutive ones of length 10.A naive approach would check every possible subarray, flip zeros, and count consecutive ones:Time Complexity: O(n²) → too slow for large arraysInefficient for constraints up to 10⁵ elementsKey Idea: Sliding Window with Zero CountInstead of brute-force, notice that:We only care about how many zeros are in the current windowWe can maintain a sliding window [i, j]Keep a counter z for zeros in the windowExpand the window by moving jIf z exceeds k, shrink the window from the left by moving i and decrementing z for each zero removedIntuition:The window always contains at most k zerosThe length of the window gives the maximum consecutive ones achievable with flipsThis allows linear traversal of the array with O(1) space, making it optimal.Approach (Step-by-Step)Initialize pointers: i = 0, j = 0Initialize z = 0 (zeros count in current window) and co = 0 (max length)Iterate j from 0 to nums.length - 1:If nums[j] == 0, increment zCheck z:If z <= k: window is valid → update co = max(co, j - i + 1)Else: shrink window by moving i until z <= k, decrement z for zeros leaving windowContinue expanding window with jReturn co as the maximum consecutive onesOptimization:Only need one variable for zeros countAvoids recomputing sums or scanning subarrays repeatedlyImplementation (Java)class Solution { public int longestOnes(int[] nums, int k) { int co = 0; // maximum length of valid window int i = 0, j = 0; // window pointers int z = 0; // count of zeros in current window while (j < nums.length) { if (nums[j] == 0) { z++; // increment zeros count } if (z <= k) { co = Math.max(co, j - i + 1); // valid window j++; } else { // shrink window until zeros <= k while (z > k) { if (nums[i] == 0) { z--; } i++; } co = Math.max(co, j - i + 1); j++; } } return co; }}Dry Run ExampleInput:nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Execution:Window [i, j]Zeros zValid?Max length co[0,0] → [1]0Yes1[0,2] → [1,1,1]0Yes3[0,3] → [1,1,1,0]1Yes4[0,4] → [1,1,1,0,0]2Yes5[0,5] → [1,1,1,0,0,0]3No → shrink i5[3,8] → [0,0,1,1,1,1]2Yes6Output:6Complexity AnalysisTime Complexity: O(n) → Each element is visited at most twice (once when j moves, once when i moves)Space Complexity: O(1) → Only counters and pointers usedEdge Cases Consideredk = 0 → cannot flip any zeros, just count consecutive onesArray with all 1’s → return full lengthArray with all 0’s → return min(k, length)Single element arrays → works correctlySliding Window Pattern ImportanceThis problem is a perfect example of the sliding window pattern:Use a window to track a condition (max zeros allowed)Expand and shrink dynamically based on constraintsEfficiently computes maximum/minimum contiguous subarray lengthsIt also demonstrates counting with limited violations – a key interview concept.ConclusionBy tracking zeros with a sliding window, we convert a naive O(n²) problem into O(n) linear time.Understanding this pattern allows you to solve:Max consecutive ones/zeros problemsLongest substring/subarray with constraintsSubarray problems with limited replacements or violationsOnce mastered, this approach applies to many binary array and string problems efficiently.

SlidingWindowBinaryArrayLeetCodeMedium

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

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

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

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