How Merge Sort Works: A Step-by-Step Guide

Day 57: Binary Tree Zigzag Level Order Traversal 🎢 I'm continuing my journey with an advanced tree traversal problem on Day 57 of #100DaysOfCode: "Binary Tree Zigzag Level Order Traversal." The challenge is to return the nodes of a binary tree level by level, alternating the direction of traversal (left-to-right, then right-to-left, and so on). My solution builds upon the standard Breadth-First Search (BFS) algorithm, using a queue (deque): Level Traversal: I process the tree level by level, finding the level_size in each iteration. Direction Toggle: I use a boolean flag (left_to_right) to track the current direction. Zigzag Logic: Inside the level loop, I use a simple conditional: if left_to_right is true, I append the node value normally. If it's false, I insert the node value at the beginning of the current level's list (current_level.insert(0, node.val)). Optimal Flip: After processing the entire level, I flip the left_to_right flag (left_to_right = not left_to_right) for the next level. This single-pass BFS approach ensures all nodes are visited exactly once, achieving an optimal O(n) time complexity and O(n) space complexity. My solution was accepted with 100% runtime efficiency! #Python #DSA #Algorithms #Trees #BFS #100DaysOfCode #ProblemSolving #Zigzag

🚀 DSA Challenge – Day 89 Problem: Subsets II (Handling Duplicates in Power Set) ⚙️✨ This problem was a great exploration of recursion, backtracking, and how to systematically avoid duplicate subsets using careful pruning. 🧠 Problem Summary: You are given an integer array nums that may contain duplicates. Your goal: return all possible subsets (the power set) without including any duplicate subsets. ⚙️ My Approach: 1️⃣ First, sort the array — this step helps group duplicates together, which is crucial for skipping them efficiently. 2️⃣ Use recursive backtracking to explore all possible inclusion/exclusion combinations. 3️⃣ Whenever a duplicate element is found (i.e., nums[i] == nums[i-1]), skip it if it’s at the same recursion depth — ensuring unique subset generation. 4️⃣ Keep track of the current subset and add a copy to the result whenever we reach a new state. 📈 Complexity: Time: O(2ⁿ) → Each element can be either included or excluded. Space: O(n) → For recursion and temporary subset storage. ✨ Key Takeaway: Sorting before recursion is often the simplest way to handle duplicates in backtracking problems. With one small condition check, you can turn exponential chaos into structured exploration. ⚡ 🔖 #DSA #100DaysOfCode #LeetCode #ProblemSolving #Recursion #Backtracking #Algorithms #CodingChallenge #Python #TechCommunity #InterviewPrep #EfficientCode #LearningByBuilding #CodeEveryday

💡 Day 43 / 100 – Search in Rotated Sorted Array (LeetCode #33) Today’s problem was a twist on the classic binary search — quite literally! The challenge was to find a target element in a rotated sorted array. At first glance, the array looks unsorted, but there’s actually a pattern. By identifying which part of the array is properly sorted at every step, we can still apply binary search logic efficiently — achieving O(log n) time complexity. This problem beautifully blends pattern recognition with logical precision. 🔍 Key Learnings Even when data looks “unsorted,” patterns often exist beneath. Modified binary search can adapt to many problem variations. Understanding midpoint relationships helps in avoiding brute force. 💭 Thought of the Day Adaptability is key — in coding and in life. Just like binary search adjusts to a rotated array, we can adjust to challenges by recognizing the underlying order in the chaos. Clear logic turns confusion into clarity. 🔗 Problem Link: https://lnkd.in/gS8FcbeE #100DaysOfCode #Day43 #LeetCode #Python #BinarySearch #ProblemSolving #Algorithms #CodingChallenge #DataStructures #CodingJourney #PythonProgramming #LogicBuilding #KeepLearning #TechGrowth #Motivation

🚀 LeetCode #1611 – Minimum One Bit Operations to Make Integers Zero Today, I tackled one of the more fascinating bit-manipulation problems on LeetCode — "Minimum One Bit Operations to Make Integers Zero". 🧩 Problem Overview Given an integer n, you must transform it into 0 using two operations: Flip the rightmost (0th) bit. Flip the ith bit if the (i−1)th bit is 1 and all lower bits are 0. The goal is to find the minimum number of operations required. The challenge is to transform an integer n into 0 using specific bit operations that flip bits based on certain constraints. At first glance, it seems like a complex recursive search problem, but the key insight lies in recognizing the pattern of Gray codes. 🔍 Key Insight: The problem follows the structure of reflected Gray code transformations. By analyzing how bits flip in the Gray code sequence, we can derive a recursive relationship that efficiently computes the minimum operations. 💡 Recursive Relation: If f(n) is the minimum number of operations for integer n: f(0) = 0 f(n) = (1 << (k + 1)) - 1 - f(n ^ (1 << k)) where k is the position of the most significant bit (MSB) in n. 🧠 Example Walkthrough n = 3 → binary 11 → result = 2 n = 6 → binary 110 → result = 4 ⚙️ Complexity Time: O(log n) Space: O(log n) (due to recursion depth) 🧩 Takeaway This problem was a great reminder that: Many bit-manipulation problems have elegant recursive or mathematical patterns hidden beneath them. Recognizing symmetry and recursion in binary transformations often leads to O(log n) solutions. #LeetCode #Python #BitManipulation #GrayCode #Algorithms #DataScience

⚡ Understanding Quick Sort 🎯 Problem: Given an array of numbers, sort them in ascending order using the Quick Sort algorithm. 🧠 Concept: - Quick Sort is a powerful Divide & Conquer algorithm that sorts by selecting a pivot and placing it in its correct position. - Once the pivot settles, elements smaller than it move to the left, and larger ones move to the right — forming two sub-arrays that get sorted recursively. 🔹 Select a pivot (commonly the first, last, or a random element). 🔹 Move all smaller elements to the left of the pivot. 🔹 Move all larger elements to the right. 🔹 Recursively sort the left and right sub-arrays. 🔹 The array becomes fully sorted after all pivots settle into their correct spots. ⚙️ How the Partitioning Works: - Two pointers i (from the left) and j (from the right) move inward. - i moves until it finds an element greater than the pivot. - j moves until it finds an element smaller than the pivot. - If i < j, the elements are swapped. - Finally, the pivot is swapped into its correct position (j). - This makes j the partition index, and sorting continues around it. 🕒 Time Complexity: Average / Best: O(N log N) – Efficient due to effective partitioning. Worst: O(N²) – Happens when pivots are chosen poorly (like already sorted arrays without randomization). 💾 Space Complexity: O(1) – Only in-place swaps are used (excluding recursion stack). #Python #DSA #DsaStriver #LearnDaily #Share #ProblemSolving

Day 50: Binary Search Tree Iterator (BST) 🌲 I'VE HIT THE HALFWAY MARK! Day 50 of #100DaysOfCode is dedicated to mastering the "Binary Search Tree Iterator." This challenge requires designing a class that enables in-order traversal of a BST using constant time complexity for the key operations. The key insight is using an Iterative Inorder Traversal with a Stack: __init__ (Initialization): The constructor doesn't traverse the whole tree. It uses a helper function (_push_left) to initially push the root and all its left descendants onto the stack. This positions the stack to start at the smallest element. next(): This method retrieves the next smallest element. It simply pops the top element from the stack, and then immediately checks if that popped node has a right child. If it does, it calls _push_left on the right child to load the next set of smallest elements onto the stack. Efficiency: The design ensures that while an element is pushed and popped exactly once overall (O(n) total time), the amortized time complexity for both next() and hasNext() is O(1). This was a perfect problem to mark the halfway point—combining Data Structures and Algorithmic Design! #Python #DSA #Algorithms #BST #Iterator #Stack #100DaysOfCode

🚀 Solving Binary Subarray With Sum — From Brute Force to Optimal I recently solved LeetCode 930: Binary Subarray With Sum, and it turned out to be a great learning path across multiple techniques 💡 Problem: Count subarrays in a binary array whose sum equals a target (goal). My approach evolution: 1️⃣ Brute Force (O(n²)) – Check all (i, j) pairs. 2️⃣ Prefix Sum Array – Simplified sum calculation but still O(n²). 3️⃣ Prefix Sum + HashMap (O(n)) – Store prefix frequencies to count valid subarrays efficiently. 4️⃣ Sliding Window – For binary arrays, maintain subarray sum dynamically. 5️⃣ Special Case (goal == 0) – Count zero stretches combinatorially: k * (k + 1) / 2. ✅ Final solution combines: Prefix Sum Frequency (for goal > 0) Zero Stretch Counting (for goal = 0) Key takeaway: From brute force to optimized O(n), this problem teaches how prefix sums, hash maps, and combinatorics work together for elegant problem-solving. #LeetCode #ProblemSolving #DataStructures #Algorithms #CodingJourney #PrefixSum #SlidingWindow #Python

A Great Lesson in Optimization: From O(n^2) to O(n) with "Two Sum" My initial instinct was to develop a brute-force solution. This approach, which involved two nested loops, correctly found the answer but had a time complexity of O(n^2). I knew there had to be a more efficient method. This prompted me to explore optimization, and I soon discovered the power of using a HashMap (or Dictionary). By leveraging this data structure, I could store the values I had already encountered and their indices. This new approach allowed me to find the solution in a single Loop, completely eliminating the nested loop and achieving a linear time complexity of O(n). Valuable lesson:- the first solution that comes to mind isn't always the best one. It highlighted the critical importance of analyzing time complexity and selecting the right data structure for the job. A simple change in approach can be the difference between a functional solution and a truly efficient one. #DataStructures #Algorithms #ProblemSolving #Optimization #Python #SoftwareDevelopment #LearningJourney

🌙 Day 41 of LeetCode Challenge Problem: 1625. Lexicographically Smallest String After Applying Operations Difficulty: 🟠 Medium 🧩 Problem Summary: We are given a numeric string s (even length) and two integers a and b. We can: 1️⃣ Add a to all digits at odd indices (mod 10). 2️⃣ Rotate the string to the right by b positions. The goal is to find the lexicographically smallest string possible after performing these operations any number of times. 💡 Approach: The problem is based on exploring all possible transformations of the string. Since both operations can be applied infinitely, we use BFS (Breadth-First Search) to systematically try every possible state of the string. At each step: Apply the “add to odd indices” operation. Apply the “rotate by b” operation. Add new unique strings to a queue for further exploration. We also keep track of the smallest string found so far. The process continues until all possible states are explored. 🧠 Key Insights: There are only a finite number of unique strings possible because digits wrap around (mod 10) and rotations eventually repeat. BFS ensures we don’t miss any possible transformation. The smallest string is found naturally during the traversal. 🕹 Example: Input → s = "5525", a = 9, b = 2 After applying multiple add and rotate operations, the smallest string obtained is "2050". ⏱ Complexity: Time Complexity: O(10 × n²) Space Complexity: O(n × 10) 🔥 Takeaway: This problem beautifully combines string manipulation, mathematical operations, and graph traversal (BFS). Even simple operations can lead to complex state spaces — mastering how to explore them systematically is the key! #LeetCode #Day41 #Python #BFS #StringManipulation #CodingJourney 🚀