Search Blogs

Showing results for "Hashing"

Found 12 results

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

LeetCode 3838: Weighted Word Mapping – Java Solution Explained with Multiple Approaches

IntroductionLeetCode 3838, Weighted Word Mapping, is a straightforward yet interesting problem that combines several fundamental programming concepts:Character mappingHashingModular arithmeticString processingOptimization techniquesAt first glance, the problem appears to be a simple implementation exercise. However, it provides a great opportunity to discuss different approaches and understand how fixed-size alphabets can help us write more efficient code.In this article, we'll explore the problem step-by-step, discuss multiple solutions, perform a dry run, and analyze the complexity of each approach.Problem Link -: Weighted Word MappingProblem StatementYou are given:An array of strings wordsAn integer array weights of length 26Each index in the weights array corresponds to a lowercase English letter.For every word:Calculate the sum of character weights.Take the result modulo 26.Convert the modulo result into a letter using reverse alphabetical order:0 → z1 → y2 → x...25 → aReturn a string formed by concatenating all mapped letters.ExampleInputwords = ["abcd", "def", "xyz"]Output"rij"ExplanationFor the word "abcd":a = 5b = 3c = 12d = 14Total Weight = 3434 % 26 = 88 → rFor "def":14 + 1 + 2 = 1717 % 26 = 1717 → iFor "xyz":7 + 7 + 2 = 1616 % 26 = 1616 → jFinal Answer:"rij"Understanding the Core IdeaThe problem consists of three independent operations:Step 1: Calculate Word WeightFor each word:Weight(word) = Sum of character weightsExample:abca = 5b = 3c = 12Weight = 20Step 2: Apply Modulo 26The problem requires:Weight % 26This guarantees that the result always lies between:0 and 25Step 3: Reverse Alphabet MappingUnlike normal alphabet indexing:0 → a1 → b2 → cthe problem uses:0 → z1 → y2 → x...25 → aThis reverse mapping generates the final encoded character.Approach 1: HashMap-Based SolutionIntuitionCreate:Map 1Character → WeightExample:a → 5b → 3c → 12Map 2Modulo Value → CharacterExample:0 → z1 → y2 → xThen process each word and build the answer.Java Implementationclass Solution { public String mapWordWeights(String[] words, int[] weights) { HashMap<Character,Integer> weightMap = new HashMap<>(); HashMap<Integer,Character> reverseMap = new HashMap<>(); for(int i = 0; i < 26; i++) { char letter = (char)('a' + i); char reverseLetter = (char)('z' - i); weightMap.put(letter, weights[i]); reverseMap.put(i, reverseLetter); } StringBuilder answer = new StringBuilder(); for(String word : words) { int sum = 0; for(char ch : word.toCharArray()) { sum += weightMap.get(ch); } answer.append(reverseMap.get(sum % 26)); } return answer.toString(); }}Approach 2: Optimized Array SolutionObservationThe English alphabet contains only 26 letters.Instead of using HashMaps:weightMap.get(ch)we can directly access:weights[ch - 'a']This eliminates hashing overhead entirely.Why Is This Better?HashMap operations are O(1) on average, but they still involve:Hash computationBucket lookupInternal object handlingArray indexing is faster because it directly accesses memory.Optimized Java Solutionclass Solution { public String mapWordWeights(String[] words, int[] weights) { StringBuilder answer = new StringBuilder(); for(String word : words) { int sum = 0; for(char ch : word.toCharArray()) { sum += weights[ch - 'a']; } int mod = sum % 26; answer.append((char)('z' - mod)); } return answer.toString(); }}Dry RunInputwords = ["abcd"]Assume:a = 7b = 5c = 3d = 4Calculate Weight7 + 5 + 3 + 4 = 19Apply Modulo19 % 26 = 19Reverse Mapping0 → z1 → y2 → x...19 → gResult:"g"Complexity AnalysisHashMap SolutionTime ComplexityO(T)where T is the total number of characters across all words.Space ComplexityO(1)Only fixed-size maps of 26 elements are stored.Optimized Array SolutionTime ComplexityO(T)Space ComplexityO(1)No additional data structures are required.Which Solution Should You Use?ApproachTimeSpaceInterview PreferenceHashMapO(T)O(1)GoodDirect ArrayO(T)O(1)BestBoth solutions are efficient.However, the array-based approach is typically preferred in coding interviews because:Simpler implementationFaster executionLower memory overheadNo unnecessary hashingInterview DiscussionA common follow-up question is:Can we eliminate both HashMaps?Yes.Since:'a' to 'z'are contiguous ASCII characters, we can directly compute:weights[ch - 'a']Similarly:(char)('z' - mod)can generate the reverse mapping without storing another lookup table.This reduces code complexity while maintaining the same asymptotic performance.Key TakeawaysFixed-size alphabets often allow array-based optimizations.HashMaps improve readability but may not always be necessary.Modular arithmetic is useful for reducing values into a bounded range.Character arithmetic can replace lookup tables in many string problems.Always look for opportunities to replace generic data structures with direct indexing when the input domain is small and fixed.ConclusionLeetCode 3838: Weighted Word Mapping is an excellent beginner-friendly problem that demonstrates the practical use of hashing, modular arithmetic, and character manipulation.While a HashMap-based solution is intuitive and easy to understand, recognizing that the alphabet size is fixed allows us to develop a cleaner and more optimized array-based solution.Understanding both approaches not only helps solve this problem efficiently but also strengthens the problem-solving mindset needed for technical interviews and competitive programming.

LeetCodeEasyArrayHashMapStringFrequencyJava

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

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

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

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

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

JavaSliding WindowMedium

LeetCode 3120: Count the Number of Special Characters I – Java HashSet Solution Explained

IntroductionLeetCode 3120 – Count the Number of Special Characters I is a beginner-friendly string and hashing problem.This problem focuses on:Character manipulationUppercase and lowercase conversionHashSet usageString traversalBasic optimization techniquesIt is a good interview problem for testing:Understanding of ASCII charactersJava Character methodsSet operationsProblem-solving logicProblem Link🔗 https://leetcode.com/problems/count-the-number-of-special-characters-i/Problem StatementYou are given a string:wordA character is called:specialif it appears in both:LowercaseUppercaseReturn:Total number of special charactersExample 1Inputword = "aaAbcBC"Output3ExplanationCharacters:'a' and 'A''b' and 'B''c' and 'C'All appear in both cases.So answer is:3Example 2Inputword = "abc"Output:0No uppercase letters exist.Example 3Inputword = "abBCab"Output:1Only:'b' and 'B'appear in both forms.IntuitionWe need to check:For every lowercase character:Does its uppercase version exist?Using HashSet makes lookup very fast.Brute Force ApproachIdeaFor every character:Traverse entire stringSearch for uppercase/lowercase pairCount valid matchesBrute Force ComplexityTime ComplexityO(N²)because nested traversal is required.Space ComplexityO(1)Optimized HashSet ApproachIdeaUse two sets:One for lowercase lettersOne for uppercase lettersThen check matching pairs.Java Solutionclass Solution {public int numberOfSpecialChars(String word) {HashSet<Character> lower = new HashSet<>();HashSet<Character> upper = new HashSet<>();for(int i = 0; i < word.length(); i++) {if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') {lower.add(word.charAt(i));}else {upper.add(word.charAt(i));}}int ans = 0;for(int i = 0; i < word.length(); i++) {char up = Character.toUpperCase(word.charAt(i));if(lower.contains(word.charAt(i)) && upper.contains(up)) {ans++;lower.remove(word.charAt(i));upper.remove(up);}}return ans;}}Cleaner Optimized Versionclass Solution {public int numberOfSpecialChars(String word) {HashSet<Character> lower = new HashSet<>();HashSet<Character> upper = new HashSet<>();for(char ch : word.toCharArray()) {if(Character.isLowerCase(ch)) {lower.add(ch);}else {upper.add(ch);}}int count = 0;for(char ch : lower) {if(upper.contains(Character.toUpperCase(ch))) {count++;}}return count;}}Why This WorksWe separate:Lowercase charactersUppercase charactersThen for every lowercase letter:We check whether uppercase version exists.HashSet lookup works in:O(1)average time.Dry RunInputword = "aaAbcBC"Step 1Lowercase set:[a, b, c]Uppercase set:[A, B, C]Step 2Check:'a' → 'A' exists'b' → 'B' exists'c' → 'C' existsCount becomes:3Final Answer3Time Complexity AnalysisOptimized HashSet SolutionTime ComplexityO(N)because string traversal happens only once.Space ComplexityO(1)Maximum alphabet size is fixed:26 lowercase + 26 uppercaseBrute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashSet ApproachO(N)O(1)Interview ExplanationIn interviews, explain:We use two HashSets to separately store lowercase and uppercase letters. Then we check whether a lowercase character has its uppercase counterpart.This demonstrates:Efficient lookup usageHashing knowledgeCharacter manipulation skillsCommon Mistakes1. Double Counting CharactersWithout removing counted characters:same letter may be counted multiple times2. Forgetting Case ConversionAlways convert:Character.toUpperCase(ch)before comparison.3. Using Nested Loops UnnecessarilyHashSet reduces lookup complexity significantly.FAQsQ1. Why use HashSet?Because lookup operations are very fast.Q2. Can this be solved without extra space?Yes.Using arrays of size 26 is also possible.Q3. Why remove characters after counting?To avoid duplicate counting.Q4. Is this problem important for interviews?Yes.It tests:String handlingCharacter conversionHashSet usageOptimization thinkingRelated ProblemsPractice these next:Valid AnagramFirst Unique Character in a StringRansom NoteConclusionLeetCode 3120 is a simple but effective problem for learning:HashSet operationsString traversalCase conversionEfficient lookup techniquesThe key idea is:Store lowercase and uppercase letters separately, then check matching pairs efficiently.Once this pattern becomes clear, many string hashing problems become much easier.

LeetCodeJavaHashSetStringEasy

LeetCode 3121: Count the Number of Special Characters II – Java HashMap Solution Explained

IntroductionLeetCode 3121 – Count the Number of Special Characters II is an interesting string and hashing problem that extends the logic of the previous Special Characters problem.This problem tests:Character indexingString traversalHashMap usageUppercase and lowercase handlingOrder-based conditionsUnlike Part I, this version adds an important restriction:Every lowercase occurrence must appear before the first uppercase occurrence.This additional condition makes the problem more challenging and interview-relevant.Problem Link🔗 https://leetcode.com/problems/count-the-number-of-special-characters-ii/Problem StatementYou are given a string:wordA character is called:specialif:It appears in both lowercase and uppercaseEvery lowercase occurrence appears before the first uppercase occurrenceReturn:Number of special charactersExample 1Inputword = "aaAbcBC"Output3ExplanationSpecial characters:'a''b''c'because:Lowercase letters appear firstUppercase letters appear laterExample 2Inputword = "abc"Output:0No uppercase letters exist.Example 3Inputword = "AbBCab"Output:0Explanation:Lowercase letters appear after uppercase letters.Condition fails.Key ObservationFor a character to be special:Last lowercase index < First uppercase indexThis is the entire logic of the problem.IntuitionWe need two pieces of information.For every character:Last occurrence of lowercase letterFirst occurrence of uppercase letterIf:lastLowercase < firstUppercasethen character is special.Brute Force ApproachIdeaFor every character:Traverse entire stringFind lowercase occurrencesFind uppercase occurrencesVerify ordering conditionBrute Force ComplexityTime ComplexityO(N²)because repeated traversal is required.Space ComplexityO(1)Optimized HashMap ApproachIdeaUse two HashMaps:Lowercase map stores last indexUppercase map stores first indexThen compare indices.Java Solutionclass Solution { public int numberOfSpecialChars(String word) { HashMap<Character, Integer> lower = new HashMap<>(); HashMap<Character, Integer> upper = new HashMap<>(); for(int i = 0; i < word.length(); i++) { if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') { lower.put(word.charAt(i), i); } else { if(!upper.containsKey(word.charAt(i))) { upper.put(word.charAt(i), i); } } } int ans = 0; for(int i = 0; i < word.length(); i++) { char up = Character.toUpperCase(word.charAt(i)); if(lower.containsKey(word.charAt(i)) && upper.containsKey(up)) { if(lower.get(word.charAt(i)) < upper.get(up)) { ans++; lower.remove(word.charAt(i)); upper.remove(up); } } } return ans; }}Cleaner Optimized Versionclass Solution { public int numberOfSpecialChars(String word) { int[] lastLower = new int[26]; int[] firstUpper = new int[26]; Arrays.fill(lastLower, -1); Arrays.fill(firstUpper, Integer.MAX_VALUE); for(int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if(Character.isLowerCase(ch)) { lastLower[ch - 'a'] = i; } else { firstUpper[ch - 'A'] = Math.min(firstUpper[ch - 'A'], i); } } int count = 0; for(int i = 0; i < 26; i++) { if(lastLower[i] != -1 && firstUpper[i] != Integer.MAX_VALUE && lastLower[i] < firstUpper[i]) { count++; } } return count; }}Why This WorksFor every character:We store:last lowercase positionand:first uppercase positionThen simply check:lastLowercase < firstUppercaseIf true:Character satisfies problem condition.Dry RunInputword = "aaAbcBC"Step 1: Store IndicesLowercase positions:'a' → 1'b' → 3'c' → 4Uppercase positions:'A' → 2'B' → 5'C' → 6Step 2: Compare1 < 2 → valid3 < 5 → valid4 < 6 → validCount becomes:3Final Answer3Time Complexity AnalysisOptimized HashMap SolutionTime ComplexityO(N)because string traversal happens once.Space ComplexityO(1)Maximum alphabet size remains fixed.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashMap / Array ApproachO(N)O(1)Interview ExplanationIn interviews, explain:A character is special only if its last lowercase occurrence appears before its first uppercase occurrence. We track indices efficiently using HashMaps or arrays.This demonstrates:String manipulation skillsIndex trackingHashing knowledgeOptimization thinkingCommon Mistakes1. Checking Only PresenceMany solutions only verify:lowercase exists && uppercase existsBut ordering condition is also required.2. Storing Wrong IndicesWe need:Last lowercase indexFirst uppercase indexnot the opposite.3. Double Counting CharactersAlways remove counted characters or use controlled traversal.4. Ignoring Case ConversionAlways convert correctly using:Character.toUpperCase(ch)FAQsQ1. Why store last lowercase occurrence?Because all lowercase letters must appear before uppercase.Q2. Why store first uppercase occurrence?Because it defines the earliest uppercase appearance.Q3. Can arrays replace HashMaps?Yes.Arrays are even more optimized because alphabet size is fixed.Q4. Is this problem interview important?Yes.It tests:String traversalIndex trackingCharacter handlingOptimization techniquesRelated ProblemsPractice these next:Count the Number of Special Characters IFirst Unique Character in a StringValid AnagramConclusionLeetCode 3121 is an excellent medium-level hashing and string problem.It teaches:Efficient index trackingHashMap usageOrder-based validationCharacter manipulationThe key insight is:A character is special only if its last lowercase occurrence appears before its first uppercase occurrence.Once this pattern becomes clear, many advanced string indexing problems become much easier.

LeetCodeJavaHashMapStringMedium

LeetCode 36: Valid Sudoku Explained – Java Solutions, Intuition & Formula Dry Run

IntroductionSudoku is a universally beloved puzzle, but validating a Sudoku boardalgorithmically is a classic technical interview question. In this post, we aregoing to dive deep into LeetCode 36: Valid Sudoku.We won't just look at the code; we will explore the intuition behind the problemso you don't have to memorize anything. We’ll cover an ingenious in-placevalidation approach, break down the complex math formula used to check3 \times 3 sub-boxes, and look at an alternative optimal solution usingHashSets.Let's dive in!Understanding the ProblemThe problem asks us to determine if a partially filled 9 \times 9 Sudoku boardis valid. To be valid, the filled cells must follow three straightforward rules:1. Each row must contain the digits 1-9 without repetition.2. Each column must contain the digits 1-9 without repetition.3. Each of the nine 3 \times 3 sub-boxes must contain the digits 1-9 withoutrepetition.Important Note: A valid board doesn't mean the board is fully solvable! We onlycare about checking the numbers that are currently on the board.Intuition: How to Think About the ProblemBefore writing code, how do we, as humans, check if a Sudoku board is valid? Ifyou place a 5 in a cell, you quickly scan horizontally (its row), vertically(its column), and within its small 3 \times 3 square. If you see another 5, theboard is invalid.To translate this to code, we have two choices:1. The Simulation Approach: Go cell by cell. Pick up the number, hide it, andcheck its row, column, and 3 \times 3 box to see if that number existsanywhere else. (This is the approach we will look at first).2. The Memory Approach: Go cell by cell, but keep a "notebook" (like a HashTable) of everything we have seen so far. If we see a number we've alreadywritten down for a specific row, column, or box, it's invalid.Approach 1: The In-Place Validation (Space-Optimized)Here is a brilliant solution that validates the board without using any extradata structures.The Logic: Iterate through every cell on the board. When we find a number, wetemporarily replace it with a . (empty space). Then, we iterate 9 times to checkits entire row, column, and sub-box. If the number is found, we return false.Otherwise, we put the number back and move to the next cell.The Java Codeclass Solution {public boolean isvalid(char[][] board, int i, int j, char k) {for(int m = 0; m < 9; m++) {// Check rowif(board[i][m] == k) return false;// Check columnif(board[m][j] == k) return false;// Check 3x3 sub-boxif(board[3 * (i / 3) + m / 3][3 * (j / 3) + m % 3] == k) return false;}return true;}public boolean isValidSudoku(char[][] board) {for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(board[i][j] != '.') {char temp = board[i][j];board[i][j] = '.'; // Temporarily remove the numberif(!isvalid(board, i, j, temp)) {return false;}board[i][j] = temp; // Put the number back}}}return true;}}The Math Breakdown: Demystifying the 3 \times 3 Grid FormulaThe hardest part of this code to understand is this exact line: board[3*(i/3) +m/3][3*(j/3) + m%3]How does a single loop variable m (from 0 to 8) traverse a 3 \times 3 grid?Let’s do a dry run.Step 1: Finding the Starting Point of the BoxThe grid is 9 \times 9, broken into nine 3 \times 3 boxes. If we are at a randomcell, say row i = 4, col j = 5, which box are we in? Because integer division inJava drops the decimal:i / 3 = 4 / 3 = 1j / 3 = 5 / 3 = 1Now multiply by 3 to get the actual starting coordinates (top-left corner) ofthat specific sub-box:3 * 1 = 3 (Row offset)3 * 1 = 3 (Col offset) So, the 3 \times 3 box starts at row 3, col 3.Step 2: Traversing the Box (Dry Run)Now, as m goes from 0 to 8, we use m / 3 for rows and m % 3 for columns:m = 0: row offset 0/3 = 0, col offset 0%3 = 0 \rightarrow Checks (3+0, 3+0) = (3, 3)m = 1: row offset 1/3 = 0, col offset 1%3 = 1 \rightarrow Checks (3+0, 3+1) = (3, 4)m = 2: row offset 2/3 = 0, col offset 2%3 = 2 \rightarrow Checks (3+0, 3+2) = (3, 5)m = 3: row offset 3/3 = 1, col offset 3%3 = 0 \rightarrow Checks (3+1, 3+0) = (4, 3)m = 4: row offset 4/3 = 1, col offset 4%3 = 1 \rightarrow Checks (3+1, 3+1) = (4, 4)...and so on up to m = 8.This brilliant math formula maps a 1D loop (0 to 8) directly onto a 2D3 \times 3 grid perfectly! No nested loops needed inside the isvalid function.Approach 2: The HashSet Solution (Single Pass)While the first approach is highly space-efficient, it does a bit of redundantchecking. An alternative approach that interviewers love is using a HashSet.Instead of checking rows and columns every time we see a number, we generate aunique "string signature" for every number and attempt to add it to a HashSet.If we see a 5 at row 0 and col 1, we create three strings:1. "5 in row 0"2. "5 in col 1"3. "5 in block 0-0"The HashSet.add() method returns false if the item already exists in the set. Ifit returns false, we instantly know the board is invalid!HashSet Java Code:class Solution {public boolean isValidSudoku(char[][] board) {HashSet<String> seen = new HashSet<>();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char number = board[i][j];if (number != '.') {// HashSet.add() returns false if the element already existsif (!seen.add(number + " in row " + i) ||!seen.add(number + " in col " + j) ||!seen.add(number + " in block " + i/3 + "-" + j/3)) {return false;}}}}return true;}}Notice how we use i/3 + "-" + j/3 to identify the blocks. Top-left is block 0-0,bottom-right is block 2-2.Time and Space Complexity BreakdownInterviewers will always ask for your complexity analysis. Because a Sudokuboard is strictly fixed at 9 \times 9, the strict Big-O is actually constant.However, let's look at it conceptually as if the board were N \times N.Approach 1: In-Place Validation (Your Solution)Time Complexity: O(1) (Strictly speaking). We traverse 81 cells, and foreach cell, we do at most 9 iterations. 81 \times 9 = 729 operations. Since729 is a constant, it's O(1). (If the board was N \times N, time complexitywould be O(N^3) because for N^2 cells, we iterate N times).Space Complexity: O(1). We only use primitive variables (i, j, k, m, temp).No extra memory is allocated.Approach 2: HashSet ApproachTime Complexity: O(1). We traverse the 81 cells exactly once. Generatingstrings and adding to a HashSet takes O(1) time. (If the board wasN \times N, time complexity would be O(N^2)).Space Complexity: O(1). The HashSet will store a maximum of81 \times 3 = 243 strings. Since this upper limit is fixed, space isconstant.ConclusionThe Valid Sudoku problem is a fantastic exercise in matrix traversal andcoordinate math.When solving this in an interview:1. Use the first approach if you want to impress the interviewer with O(1)space complexity and your deep understanding of math formulas (the /3 and %3trick).2. Use the second approach (HashSet) if you want to show off your knowledge ofdata structures and write highly readable, clean, and clever code.I hope this breakdown gives you the intuition needed so you never have tomemorize the code for LeetCode 36!Happy Coding! Keep Learning🤟

LeetCodeJavaMatrixHash TableRecursionBacktrackingMedium

LeetCode 3612: Process String with Special Operations I – Java StringBuilder Solution Explained

IntroductionLeetCode 3612, Process String with Special Operations I, is an excellent string simulation problem that tests your ability to process characters sequentially while maintaining a dynamic result string.The challenge introduces three special operations:* → Delete the last character# → Duplicate the current string% → Reverse the current stringAlthough the problem appears simple, it teaches an important interview concept:Simulate operations exactly as described while efficiently modifying a string.In this article, we'll break down the intuition, explore the optimal approach, perform a dry run, and analyze the time and space complexity.Problem link :- Process String with Special Operations IProblem StatementYou are given a string s containing:Lowercase English letters*#%Process the string from left to right according to the following rules:Lowercase LetterAppend it to the result.a → result += 'a'Asterisk (*)Remove the last character if one exists.abc*becomesabHash (#)Duplicate the current string.abc#becomesabcabcPercent (%)Reverse the current string.abc%becomescbaReturn the final string after processing all characters.Example 1Inputs = "a#b%*"Step-by-Step ExecutionCharacterOperationResultaAppenda#DuplicateaabAppendaab%Reversebaa*Remove lastbaOutput"ba"Key ObservationThe operations always modify the current result.We need a data structure that supports:Appendappend()Delete Last CharacterdeleteCharAt()Reversereverse()Duplicateappend(currentString)A StringBuilder supports all of these efficiently.This makes it the perfect choice for the problem.Approach 1: StringBuilder SimulationIntuitionProcess each character one by one.If it is a letterAppend it.If it is *Delete the last character.If it isDuplicate the entire current string.If it is %Reverse the current string.Continue until all characters are processed.Java Solutionclass Solution { public String processStr(String q) { StringBuilder s = new StringBuilder(); for(int i =0;i < q.length();i++){ if(q.charAt(i) != '#'&&q.charAt(i) != '*'&& q.charAt(i) != '%'){ s.append(q.charAt(i)); }else if(q.charAt(i) == '#'&& s.length()>=1){ s.append(s); }else if(q.charAt(i) == '*' && s.length()>=1){ s.deleteCharAt(s.length()-1); }else{ s.reverse(); } } return s.toString(); }}Dry RunInputs = "abc#%"Step 1aResult:aStep 2bResult:abStep 3cResult:abcStep 4#Duplicate:abcabcStep 5%Reverse:cbacbaFinal Answer:cbacbaWhy StringBuilder Is Better Than StringSuppose we use:result += ch;Every append creates a brand-new string.For large inputs this becomes inefficient.StringBuilder modifies the same object in memory.Benefits:Faster appendFaster deletionBuilt-in reverse operationLower memory overheadThis is why StringBuilder is the preferred interview solution.Complexity AnalysisLet:n = length of input stringTime ComplexityAppendO(1)Delete LastO(1)ReverseO(m)where m is current result length.DuplicateO(m)because the entire string is copied.Overall:O(n × m)In this problem:n ≤ 20so this is perfectly acceptable.Alternative Approach: Using a StackAnother way is storing characters inside a stack.Advantages:Easy handling of *Natural last-in-first-out behaviorDisadvantages:Reversing becomes expensiveDuplicating requires rebuilding dataTherefore, StringBuilder remains the cleaner solution.Interview DiscussionA common interview follow-up is:Why not use String?Because Strings are immutable.Every operation like:result += ch;creates a new object.StringBuilder avoids repeated object creation and is significantly more efficient.Edge CasesCase 1s = "z*#"Process:z → "z"* → ""# → ""Output:""Case 2s = "%"Output:""Reversing an empty string changes nothing.Case 3s = "*"Output:""Nothing exists to delete.Key TakeawaysStringBuilder is ideal for string simulation problems.Process operations strictly from left to right.append(), deleteCharAt(), and reverse() make implementation simple.Always look for mutable string structures when frequent modifications are required.Simulation problems often test implementation accuracy more than algorithmic complexity.ConclusionLeetCode 3612: Process String with Special Operations I is a clean simulation problem that demonstrates how powerful StringBuilder can be for handling dynamic string transformations.By processing each character sequentially and applying the required operation immediately, we can solve the problem efficiently with a straightforward and readable solution.This problem is an excellent exercise for improving string manipulation skills and understanding when to choose mutable data structures over immutable strings.

LeetcodeJavaStringString BuilderMedium