Solved Binary Tree Zigzag Level Order Traversal with BFS

Day 72: Partition List 🔗 I'm back to linked lists on Day 72 of #100DaysOfCode by solving "Partition List." The challenge is to rearrange a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x, while preserving the original relative order within each partition. My solution uses a two-list approach with dummy nodes: Creation of Two Lists: I initialize two separate dummy nodes: less_dummy and greater_dummy. Partitioning: I iterate through the original list once. If a node's value is less than x, I append it to the less list; otherwise, I append it to the greater list. This inherently preserves the relative order within each group. Merging: After the single pass, I set the next pointer of the tail of the less list to the head of the greater list (less_tail.next = greater_dummy.next). Crucially, I set the tail of the greater list to None to prevent cycles (greater_tail.next = None). This single-pass method achieves an optimal O(n) time complexity and O(1) extra space complexity (excluding the new nodes being rearranged). My solution was accepted with 100% runtime efficiency! #Python #DSA #Algorithms #LinkedList #100DaysOfCode #ProblemSolving

Day 62: Recover Binary Search Tree (BST) 🌳 I'm continuing my journey on Day 62 of #100DaysOfCode with a challenging BST problem: "Recover Binary Search Tree." The task is to fix a BST where exactly two nodes have been swapped by mistake, all without changing the tree's structure. The key insight relies on the property of Inorder Traversal of a BST, which always yields nodes in ascending order. Inorder Traversal: I first perform a standard inorder traversal (using recursion) to store the node values in an ascending list (inorder). Finding Swapped Nodes: I then iterate through the inorder list to find the two misplaced nodes. A violation occurs when inorder[i-1] > inorder[i]. The first misplaced node (first) is the larger element of the first violation. The second misplaced node (second) is the smaller element of the last violation. Correction: Finally, I swap the values of the two nodes found in the original tree. This method achieves an O(n) time complexity and O(n) space complexity (due to storing the inorder array). My solution was accepted with 100% runtime efficiency! #Python #DSA #Algorithms #BST #InorderTraversal #100DaysOfCode #ProblemSolving

🧩 Day 30 — 4Sum (LeetCode 18) 📝 Problem -Given an integer array nums, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: -a, b, c, and d are distinct indices -nums[a] + nums[b] + nums[c] + nums[d] == target -Return the answer in any order. 🔁 Approach -Sort the array to handle duplicates efficiently. -Use a recursive k-sum approach that generalizes 2-sum, 3-sum, and 4-sum problems. -For k > 2, recursively reduce the problem: -Fix one number and call kSum for k - 1 on the remaining array. -Skip duplicates to avoid repeating quadruplets. -For k = 2, use the two-pointer technique: -Move pointers inward based on the sum comparison with the target. -Add valid pairs to the result and skip duplicates. -Backtrack after each recursive call to explore all possible combinations. 📊 Complexity -Time Complexity : O(n³) -Space Complexity : O(k) 🔑 Concepts Practiced -Recursive K-Sum pattern -Two-pointer technique -Sorting and duplicate handling -Backtracking with controlled search space #python #DSA #4Sum #ProblemSolving #Leetcode

🚀 𝐃𝐚𝐲 𝟏𝟑 𝐨𝐟 #𝟏𝟔𝟎𝐃𝐚𝐲𝐬𝐎𝐟𝐂𝐨𝐝𝐞 — 𝐏𝐚𝐥𝐢𝐧𝐝𝐫𝐨𝐦𝐞 𝐍𝐮𝐦𝐛𝐞𝐫 | 𝐒𝐭𝐫𝐢𝐧𝐠𝐬 🧩 Today’s focus was on a simple yet classic logic check — determining if a number reads the same forward and backward. While it looks straightforward, it’s a great reminder that elegant solutions often come from clarity, not complexity. Problem: 𝐂𝐡𝐞𝐜𝐤 𝐢𝐟 𝐚𝐧 𝐢𝐧𝐭𝐞𝐠𝐞𝐫 𝐢𝐬 𝐚 𝐩𝐚𝐥𝐢𝐧𝐝𝐫𝐨𝐦𝐞. Approach: Convert the integer to a string and compare it with its reverse. Time Complexity: O(n) Space Complexity: O(n) This small exercise reinforces foundational reasoning that scales up when designing more complex systems — where reversing, mirroring, or symmetry detection shows up in data validation, pattern recognition, and even natural language tasks. 🔗 GitHub: https://lnkd.in/gaim_PJS #Python #LeetCode #CodingChallenge #160DaysOfCode #ProblemSolving #DSA #AIEngineerJourney

🧩 Day 29 — 3Sum Closest (LeetCode 16) 📝 Problem Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. 🔁 Approach -Sort the array to use the two-pointer technique effectively. -Iterate through each element nums[i] (except the last two) and treat it as the first element of the triplet. -For each i, set two pointers: -left = i + 1 -right = len(nums) - 1 -Compute the sum of the three numbers: -total = nums[i] + nums[left] + nums[right] -If total == target, return total immediately (perfect match). -Otherwise, compare the absolute difference between total and target to update the closestSum. -Adjust pointers: -If total < target, move left pointer right to increase sum. -If total > target, move right pointer left to decrease sum. -Continue until all triplets are checked. -Return the final closestSum. 📊 Complexity -Time Complexity: O(n²)  -Space Complexity: O(1) 🔑 Concepts Practiced -Sorting and two-pointer pattern -Optimization using sorted array and pointer movement -Handling duplicates efficiently -Absolute difference comparison for closest value #Leetcode #python #DSA #Sorting #problemSolving

✅ Day 96 Completed – Inorder Traversal Today’s challenge was all about performing Inorder Traversal on a binary tree — a fundamental operation in tree data structures. 🧩 Concept: Inorder traversal visits nodes in the Left → Root → Right order. The task was to implement it without using recursion or an explicit stack, making it an interesting optimization problem. 💡 Approach: The solution uses the Morris Traversal algorithm, which cleverly utilizes threaded binary trees to achieve traversal in O(1) space complexity. It creates temporary links (threads) to predecessor nodes. Once a node’s left subtree is visited, the link is removed, ensuring no extra memory usage. ⚙️ Key Highlights: Space-efficient (no recursion/stack) Time complexity: O(N) All test cases passed ✅ (1111/1111 with 100% accuracy) 🌱 Takeaway: This problem deepened my understanding of space-optimized tree traversal techniques and their practical applications. #100DaysOfCode #Day96 #GeeksforGeeks #Python #DataStructures #BinaryTree #InorderTraversal

🚀 DSA Progress – Day 112 ✅ Problem #560: Subarray Sum Equals K 🧠 Difficulty: Medium | Topics: Array, Prefix Sum, Hash Map 🔍 Approach: Implemented the Prefix Sum + Hash Map technique to efficiently count subarrays whose sum equals k. Step 1 (Prefix Sum): Maintain a running sum (prefix_sum) as we iterate through the array. Step 2 (Check for Required Sum): For each prefix_sum, check if (prefix_sum - k) exists in the hashmap. If yes → it means a subarray ending at the current index sums to k. Step 3 (Store Frequency): Use a dictionary (mp) to store how many times each prefix sum has appeared. This allows counting multiple subarrays efficiently. 🕒 Time Complexity: O(n) 💾 Space Complexity: O(n) (for hashmap storage) 📁 File: https://lnkd.in/g7acMKiA 📚 Repo: https://lnkd.in/g8Cn-EwH 💡 Learned: This problem strengthened my understanding of how prefix sums can simplify subarray-related questions. Instead of manually checking every subarray, we convert the problem into recognizing a pattern using previous sums. This is a powerful technique that shows up frequently in interview-level array problems. ✅ Day 112 complete — counted hidden subarrays like a pro! 🔢🎯✨ #LeetCode #DSA #Python #Arrays #PrefixSum #HashMap #Algorithm #DailyCoding #InterviewPrep #GitHubJourney #ProblemSolving

🚀 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

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

🚀 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