Sorting Array with Dutch National Flag Algorithm

🚀 #100DaysOfCode – Day 16 | DSA Practice Continuing my 100 Days Data Structures and Algorithms challenge, today I solved a popular problem based on arrays and two-pointer technique. 📌 Problem: Move Zeroes Given an integer array nums, move all 0’s to the end while maintaining the relative order of non-zero elements. The operation must be done in-place. Example: Input: nums = [0,1,0,3,12] Output → [1,3,12,0,0] 🧠 Approach / Logic: 1️⃣ Use two pointers: • i → to traverse the array • j → to track the position for non-zero elements 2️⃣ Traverse the array from left to right. 3️⃣ If the current element is non-zero, swap it with the element at index j. 4️⃣ Increment j to point to the next position. 5️⃣ Continue this process for the entire array. 6️⃣ At the end, all non-zero elements will be at the front, and all zeros will be shifted to the end. 📊 Time Complexity: O(n) 📦 Space Complexity: O(1) 🎯 Key Learning: This problem demonstrates how the two-pointer technique can efficiently solve in-place array problems while maintaining order. Consistency is the key to growth. Let’s keep improving every day! 💪 #100DaysOfCode #DSA #CodingJourney #ProblemSolving #CPP #LearningInPublic

Day 22 Today I solved “Missing Number” on LeetCode. The problem is to find the missing number from an array containing distinct numbers in the range [0, n]. At first, we might think of sorting or using a HashSet — but there’s a more elegant approach. 💡 Mathematical Approach (Gauss Formula) Idea: The sum of first n natural numbers = n(n+1)/2 Calculate expected sum Subtract actual sum of array The difference is the missing number Approach: Compute expected sum using formula Iterate through array to get actual sum Return the difference This gives: Time Complexity: O(n) Space Complexity: O(1) 💡 Key takeaway: Sometimes the best solution comes from mathematical observation, not data structures. #LeetCode #DSA #LearnInPublic

🚀 #100DaysOfCode – Day 15 | DSA Practice Continuing my 100 Days Data Structures and Algorithms challenge, today I solved an interesting problem based on numbers and digit manipulation. 📌 Problem: Check if The Number is Fascinating Given a 3-digit number n, we need to check whether it is fascinating or not. A number is called fascinating if: 👉 Concatenate n, 2*n, and 3*n 👉 The resulting number contains all digits from 1 to 9 exactly once 👉 It should not contain 0 Example: Input: n = 192 Concatenation → 192384576 Output → true 🧠 Approach / Logic: 1️⃣ Convert the numbers n, 2*n, and 3*n into strings and concatenate them. 2️⃣ Check if the total length of the string is 9. 3️⃣ Traverse the string and count the frequency of each digit. 4️⃣ If any digit is 0, return false. 5️⃣ Ensure each digit from 1 to 9 appears exactly once. 6️⃣ If all conditions are satisfied, the number is fascinating. 📊 Time Complexity: O(1) 📦 Space Complexity: O(1) 🎯 Key Learning: This problem highlights how string manipulation and frequency counting can be used to validate patterns in numbers. Consistency is the key to growth. Let’s keep improving every day! 💪 #100DaysOfCode #DSA #CodingJourney #ProblemSolving #CPP #LearningInPublic

🚀 Day 98 of 100 Days of DSA 📌 LeetCode #279 (Perfect Squares) 📈 "Consistency over motivation, Progress over perfection" A fascinating problem where math + pattern recognition beats traditional DP. 🧩 Problem Statement Given an integer n: Find the minimum number of perfect squares that sum up to n A perfect square = number like 1, 4, 9, 16, ... 🧠 Thought Process Initial thinking: - Try all combinations of perfect squares - Minimize the count But quickly: - Too many combinations - Overlapping subproblems This feels like a DP problem… but there’s more. 🚫 Brute Force Approach 1. Try every square ≤ n 2. Recursively subtract and explore Problems: • Massive recursion tree • Repeated calculations Time Complexity → Exponential ❌ 🔄 Better Approach (Dynamic Programming) Define: dp[i] = minimum number of squares to form i For each i: • Try all squares ≤ i • Take minimum Complexity: • Time → O(n√n) • Works, but not optimal 🔍 Key Insight This problem has a hidden mathematical structure: Every number can be represented as the sum of at most 4 perfect squares This comes from Lagrange’s Four Square Theorem 💡 Observations 1. If n itself is a perfect square → answer = 1 2. If n = a² + b² → answer = 2 3. Reduce n: • Remove factors of 4 • If n % 8 == 7 → answer = 4 4. Otherwise → answer = 3 ✅ Approach Used Math + Number Theory Optimization ⚙️ Strategy 1. Check if n is a perfect square → return 1 2. Check if n can be written as sum of 2 squares → return 2 3. Reduce n by removing powers of 4 4. If n % 8 == 7 → return 4 5. Else → return 3 💡 Intuition Instead of building the answer: Use mathematical guarantees to classify the answer directly This avoids unnecessary computation. ⏱ Complexity Analysis Time Complexity: O(√n) Space Complexity: O(1) 💡 Key Learnings - Some DP problems have mathematical shortcuts - Recognizing patterns can drastically reduce complexity - Number theory can outperform brute force and DP - Always question: “Can this be solved without building everything?” #100DaysOfDSA #Day98 #LeetCode #Math #NumberTheory #DynamicProgramming #Algorithms #DSA #CodingJourney

🚀 Day 114 of My DSA Problem Solving Journey - The Grind Continues! 🎉 After tackling some quick string manipulation yesterday, today I shifted gears to Stack data structures! I took on LeetCode's "Min Stack" (Medium) in C++. The Problem: We need to design a custom stack that supports the usual operations (push, pop, top) BUT with a catch—we also need to retrieve the minimum element in constant O(1) time! My Approach: The tricky part is figuring out how to get the minimum value instantly without scanning the entire stack. To achieve this, I used a classic Two-Stack Approach. 🧠 The Logic: Two Stacks: I initialized a main stack (st) to store all the elements and an auxiliary stack (minSt) specifically to keep track of the minimum values at any given point. Push Operation: When pushing a new value, it always goes into the main stack. If the minSt is empty, OR if the new value is less than or equal to the current minimum (the top element of minSt), I push it onto minSt as well. Pop Operation: When popping, I check if the element being removed from the main stack is exactly the same as the current minimum at the top of the auxiliary stack. If it matches, I pop it from both stacks! Otherwise, just pop from the main stack. Retrieving Min: Because of how we maintained the auxiliary stack, calling getMin() is as simple as returning the top value of minSt. Zero searching required! Takeaway: This problem is a brilliant example of a Space-Time Tradeoff. By sacrificing a little bit of memory to maintain a second stack, we successfully optimized our time complexity to a strict O(1) for every single operation! ⚡ Keep pushing! 💻🔥 #Day114 #CPP #Stack #LeetCode #DataStructures #Algorithms #DSA #ProblemSolving #CodingJourney #ContinuousLearning #REGexSoftwareServices

🚀 Day 117 of My DSA Problem Solving Journey - The Grind Continues! 🎉 After conquering Monotonic Stacks, today I tackled an interesting array and Hash Map problem on LeetCode: "Minimum Distance Between Three Equal Elements I" in C++. The Problem: Given an array, we need to find three identical elements at distinct indices (i, j, k) such that their "distance" abs(i - j) + abs(j - k) + abs(k - i) is minimized. If no such tuple exists, return -1. My Approach: Instead of a brute-force O(N^3) loop to find triplets, I optimized the solution using a Hash Map (unordered_map)! 🧠 The Logic: Math Simplification: The distance formula abs(i - j) + abs(j - k) + abs(k - i) actually simplifies to 2 \times (k - i) assuming i < j < k. This was the "Aha!" moment! I didn't even need the middle index j for the calculation, just the first and third indices of the triplet. Tracking Indices: I used a hash map where the key is the array element and the value is a vector storing all the indices where this element appears. On-the-Fly Calculation: As I iterate through the array, the moment a number appears for the third time (or more), I grab its current index (i3) and the index from two occurrences ago (i1). I calculate the distance as 2 times (i3 - i1) and update my minimum answer. Sliding Window Feel: By always checking the latest index (n-1) and the index two steps back (n-3), I ensure I'm always calculating the tightest possible distance for any three consecutive occurrences of a number. Takeaway: This problem is a great reminder of how mathematical simplification combined with Hash Maps can turn an intimidating problem into an elegant O(N) Time and Space complexity solution. Keep an eye out for those hidden formulas! ⚡ Keep pushing! 💻🔥 #Day117 #CPP #HashMap #Arrays #LeetCode #DataStructures #Algorithms #DSA #ProblemSolving #CodingJourney #ContinuousLearning #REGexSoftwareServices

🚀 Day 92 of 100 Days of DSA 📌 LeetCode #162 (Find Peak Element) 📈 "Consistency over motivation, Progress over perfection" A problem that beautifully demonstrates how binary search isn’t just for sorted arrays. 🧩 Problem Statement Given an array nums: A peak element is one that is strictly greater than its neighbors Return the index of any one peak element Constraints: • nums[-1] = nums[n] = -∞ (imaginary boundaries) • Required time complexity → O(log n) 🧠 Thought Process Initial instinct: Compare each element with its neighbors Return the one that satisfies peak condition But: Linear scan gives O(n), not acceptable here So the real question becomes: How to reduce this to logarithmic time? 🚫 Brute Force Approach 1. Traverse entire array 2. For each element: • Check left and right neighbors Time Complexity → O(n) Space → O(1) Simple but does not meet constraints ❌ 🔍 Key Insight Instead of searching for the peak directly: Observe the trend (increasing or decreasing) At any index mid: • If nums[mid] < nums[mid + 1] → Peak must exist on the right side • If nums[mid] > nums[mid + 1] → Peak lies on the left side (including mid) 🤯 Why This Works Think of the array like a mountain landscape: • If moving upward → peak ahead • If moving downward → already crossed or at peak There is always at least one peak due to boundaries being -∞ ✅ Approach Used Binary Search on Answer Space ⚙️ Strategy 1. Maintain two pointers → left and right 2. Find mid 3. Compare nums[mid] with nums[mid + 1]: • Increasing → move right • Decreasing → move left 4. Continue until left == right That index is a peak 💡 Intuition Binary search here is not about finding a value It’s about finding a direction where a peak must exist This guarantees convergence. ⏱ Complexity Analysis Time Complexity: O(log n) Space Complexity: O(1) 💡 Key Learnings - Binary search can be applied on unsorted arrays using properties - Focus on monotonic behavior, not exact values - Local comparisons can guide global decisions - Problems with guarantees (like “peak exists”) simplify logic #100DaysOfDSA #Day92 #LeetCode #BinarySearch #Algorithms #DSA #CodingJourney

🚀 Day 118 of My DSA Problem Solving Journey - The Grind Continues! 🎉 Today, I tackled an interesting array problem on LeetCode: "Shortest Distance to Target String in a Circular Array" in C++. The Problem: We are given a 0-indexed circular string array (where the end of the array connects back to the beginning) and a target string. Starting from a given startIndex, we need to find the shortest distance to reach the target, moving one step at a time either forward or backward. If the target does not exist, we return -1. My Approach: Instead of overcomplicating things with BFS or graph traversals, I used a clean and efficient O(N) approach leveraging basic mathematics! 🧠 The Logic: Iterative Search: I looped through the entire array to find all occurrences of the target string (words[i] == target). Two Paths: In a circular array, there are always two ways to travel between any two indices: Direct Distance: The straightforward path, calculated as the absolute difference: abs(i - startIndex). Wrap-around Distance: The path going the opposite way around the circle, calculated by subtracting the direct distance from the array's total length: n - dist. Finding the Minimum: Every time the target is found, I calculate the minimum of these two paths using min(dist, n - dist) and update my global shortest distance variable. Edge Case Handling: If the loop finishes and the minimum distance remains at its initial maximum value (INT_MAX), it means the target was never found, so I simply return -1. Takeaway: Circular arrays can seem tricky at first, but mastering the "wrap-around" logic makes them incredibly straightforward. This approach keeps the time complexity at O(N) and space complexity at a highly optimized O(1). Always look for the simple math before jumping into complex data structures! ⚡ Keep pushing! 💻🔥 #Day118 #CPP #Arrays #LeetCode #DataStructures #Algorithms #DSA #ProblemSolving #CodingJourney #ContinuousLearning #REGexSoftwareServices REGex Software Services

🚀 Day 77 of 100 Days of DSA 📌 LeetCode #79 (Word Search) 📈 "Consistency over motivation, Progress over perfection" A classic backtracking + DFS problem that tests grid traversal and pruning skills. 🧩 Problem Statement Given an m x n grid of characters and a string word: • Return true if the word exists in the grid • The word must be formed by adjacent cells (up, down, left, right) • Each cell can be used only once 🧠 Thought Process This problem is about: - Exploring paths in a grid - Matching characters sequentially This immediately suggests: DFS + Backtracking The challenge is: • Avoid revisiting the same cell • Explore all valid paths efficiently • Stop early when mismatch occurs 🚫 Brute Force Approach 1. Generate all possible paths from each cell 2. Check if any path forms the given word Problems: • Huge number of paths → exponential explosion • Recomputations across overlapping paths • Very inefficient without pruning ✅ Approach Used Optimized DFS + Backtracking + Pruning ⚙️ Strategy 1. Start DFS from every cell matching first character 2. At each step: • Check bounds and character match • Temporarily mark cell as visited • Explore all 4 directions • Restore cell after recursion (backtrack) 3. Stop immediately when full word is matched 🚀 Optimization Tricks - Frequency pruning If grid doesn’t contain enough characters - return early - Reverse word optimization Start from the rarer character (reduces search space) - Early stopping As soon as match is found → terminate search ⏱ Complexity Analysis Time Complexity: O(m × n × 4^L) L = length of word Space Complexity: O(L) Recursion stack depth 💡 Key Learnings - Backtracking is essential for path-based problems - Marking + restoring state is crucial - Small optimizations (like frequency check) make big impact - DFS becomes powerful when combined with pruning #100DaysOfDSA #Day77 #LeetCode #Backtracking #DFS #Algorithms #CodingJourney #DSA

Day 16/50 – DSA Challenge Today was about designing something smarter, not just solving. ->Min Stack This problem looks simple… until you realize: “getMin() must be O(1)” That’s where the real thinking starts. What I learned today: • Using an extra stack to track minimums is a design decision, not just coding • Every push/pop must maintain consistency between two stacks • This problem is less about loops and more about data structure design Key Insight: Good programmers solve problems. Better programmers design systems that make problems easier. ⚙️ From brute force → optimized → now smart data structure design That’s real progress. #DSA #LeetCode #DataStructures #CodingJourney #KeepLearning