Solved LeetCode 704: Binary Search with Python

🌳 DSA Challenge – Day 99 Problem: Balanced Binary Tree ⚖️🌲 This classic tree problem tests your understanding of recursion, depth-first search, and how to efficiently check balance conditions in binary trees. 🧠 Problem Summary: A height-balanced binary tree is one in which the height of the two subtrees of every node never differs by more than 1. Your task: Given the root of a binary tree, determine whether it is height-balanced. ⚙️ My Approach: 1️⃣ Use a recursive DFS helper util() to traverse the tree. 2️⃣ For each node, compute: Whether its left and right subtrees are balanced. The maximum depth of its left and right subtrees. 3️⃣ If at any point the height difference exceeds 1, return False. 4️⃣ The function returns both a boolean (isBalanced) and an integer (height). 💡 Optimization Insight: Instead of computing the height in a separate pass (which would make it O(n²)), this approach combines balance checking and height calculation in one DFS traversal, resulting in O(n) time complexity. 📈 Complexity Analysis: Time Complexity: O(n) — Each node is visited once. Space Complexity: O(h) — Recursion stack, where h is the height of the tree. ✨ Key Takeaway: Efficient recursion patterns often come from returning multiple values — combining partial results avoids redundant computation and keeps solutions elegant. 🔖 #DSA #100DaysOfCode #BinaryTree #LeetCode #ProblemSolving #CodingChallenge #Python #Algorithms #Recursion #TreeTraversal #TechCommunity #LearningEveryday

🚀 DSA Challenge – Day 84 Problem: Reachable Nodes in a Restricted Tree 🌲🚫 This problem was a perfect blend of graph traversal and constraint handling, where we must carefully explore a tree while avoiding restricted nodes. 🧠 Problem Summary: You are given a tree with n nodes (0-indexed) and a list of edges that describe the connections between them. Some nodes are restricted, meaning you cannot visit or pass through them. Starting from node 0, the goal is to determine how many nodes are reachable without visiting any restricted ones. ⚙️ My Approach: 1️⃣ Build an adjacency list representation of the tree. 2️⃣ Store all restricted nodes in a set for quick lookup. 3️⃣ Use Depth-First Search (DFS) to traverse the graph, skipping restricted or already visited nodes. 4️⃣ Accumulate a count of all valid reachable nodes. 📈 Complexity: Time: O(n) → Each node and edge is processed once. Space: O(n) → For adjacency list, recursion stack, and visited set. ✨ Key Takeaway: Even simple DFS problems become interesting when constraints are introduced. Efficient use of sets and recursion can elegantly handle conditions like restricted traversal in trees or graphs. 🌿 🔖 #DSA #100DaysOfCode #LeetCode #GraphTheory #TreeTraversal #DFS #Python #ProblemSolving #CodingChallenge #InterviewPrep #Algorithms #EfficientCode #TechCommunity #CodeEveryday #LearningByBuilding

#LLMHolywarChronicles The SWE-ReBench leaderboard was updated yesterday with 51 new tasks from October. For anyone who hasn’t been following: the team pulls recent PRs from Python repositories that meet certain criteria and evaluates them with a simple agent across different models. Sonnet 4.5 is still in the lead… but I won’t repeat the whole article here (https://swe-rebench.com/ ); feel free to read it if you’re interested. The only thing really worth highlighting is this: “* MiniMax M2 is the most cost-efficient open-source model among the top performers. Its pricing is $0.255 / $1.02 per 1M input/output tokens, whereas gpt-5-codex costs $1.25 / $10.00– with cached input available at just $0.125. In agentic workflows, where large trajectory prefixes are reused, this cache advantage can make models with cheap cache reads more beneficial even if their raw input/output prices are higher. In case of gpt-5-codex, it has approximately the same Cost per Problem as MiniMax M2 ($0.51 vs $0.44), being yet much more powerful.”

🚀 DSA Challenge – Day 90 Problem: Single Element in a Sorted Array ⚙️🔍 This problem was a clever application of binary search where understanding the index patterns of paired elements was the key to achieving logarithmic efficiency. 🧠 Problem Summary: You are given a sorted array where every element appears exactly twice, except for one element that appears only once. Your task: return that single element in O(log n) time and O(1) space. ⚙️ My Approach: 1️⃣ Used binary search to narrow down the segment containing the single element. 2️⃣ Checked if the middle element breaks the pairing rule — if so, that’s our unique number. 3️⃣ Observed the pattern: Before the single element, pairs start at even indices. After it, pairs start at odd indices. 4️⃣ Used this parity observation to adjust the search boundaries efficiently. 📈 Complexity: Time: O(log n) → Binary search halves the search space each step. Space: O(1) → Constant space used. ✨ Key Takeaway: Sometimes, the structure of sorted pairs reveals more than meets the eye — a small parity trick transforms a linear scan into a logarithmic search. ⚡ 🔖 #DSA #100DaysOfCode #LeetCode #ProblemSolving #BinarySearch #Algorithms #CodingChallenge #Python #Optimization #EfficientCode #TechCommunity #InterviewPrep #LearningByBuilding #CodeEveryday

🚀 DSA Progress – Day 109 ✅ Problem #880: Decoded String at Index 🧠 Difficulty: Medium | Topics: String, Math, Simulation, Reverse Traversal 🔍 Approach: Implemented a mathematical reverse-traversal approach to find the K-th character in a decoded string without actually expanding it. Step 1 (Compute Length): Iterate through the encoded string S. If the character is a letter → increment the total size by 1. If it’s a digit d → multiply size by d, since the current decoded string repeats d times. Step 2 (Reverse Simulation): Traverse the string in reverse order to "undo" the decoding. Use K = K % size to keep K within the current string's bounds. If K == 0 and the character is a letter → return that letter (it’s the answer). If the character is a letter → decrement size by 1. If it’s a digit → divide size by that digit to revert the last expansion. This avoids building the huge decoded string and instead works through mathematical reasoning. 🕒 Time Complexity: O(n) — One forward pass to compute size + one backward pass to locate the K-th character. 💾 Space Complexity: O(1) — Uses only a few variables for tracking. 📁 File: https://lnkd.in/gQT35qnU 📚 Repo: https://lnkd.in/g8Cn-EwH 💡 Learned: This problem taught me how to simulate decoding in reverse using math and modular reasoning instead of actual string building. It reinforced the power of thinking backwards and optimizing memory for string problems. Handling such problems made me more comfortable with simulation techniques, modulo arithmetic, and efficient string logic. ✅ Day 109 complete — decoded a massive virtual string using pure logic, no brute force! 🧮✨ #LeetCode #DSA #Python #String #Math #Simulation #ReverseTraversal #100DaysOfCode #DailyCoding #InterviewPrep #GitHubJourney

🚀 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

💼 LeetCode Daily Challenge: 3354. Make Array Elements Equal to Zero Today I worked on an interesting simulation based problem that combines logical movement with mathematical reasoning. 🔍 Problem Overview: - You are given an integer array containing non-negative elements. - The task is to determine the number of valid starting positions (and directions) such that all elements become zero after performing a series of operations. - The movement involves direction reversals and decrements, making direct simulation tricky. 💡 Key Observations: - Instead of brute force simulation, prefix sum analysis helps determine valid balance points. - Each zero acts as a potential pivot; by analyzing prefix and total sums, we can efficiently identify valid selections. - The solution leverages mathematical balance conditions to avoid unnecessary computation. 📊 Complexity: Time Complexity: O(n) Space Complexity: O(1) 🎯 Takeaways: - Simulation problems often hide elegant mathematical patterns. - Prefix sums are powerful tools for deriving insights without explicit iteration over all possibilities. #LeetCode #ProblemSolving #Python #DSA #Algorithm #CodingChallenge #PrefixSum #DataStructures #LearningEveryday #Efficiency

🚀 DSA Challenge – Day 80 Problem: Maximum Distance Between Valid Pairs 🌊📏 Today’s problem tested the combination of binary search and array monotonicity — finding the farthest valid pair between two non-increasing arrays! 🧠 Problem Summary: We’re given two non-increasing arrays, nums1 and nums2. A pair (i, j) is valid if: i ≤ j, and nums1[i] ≤ nums2[j]. The goal is to find the maximum distance (j - i) among all valid pairs. ⚙️ My Approach: 1️⃣ Iterate through each element in nums1. 2️⃣ Use binary search on nums2 to find the farthest valid index satisfying the condition. 3️⃣ Keep track of the maximum j - i distance encountered. This solution leverages the sorted (non-increasing) property of arrays for logarithmic efficiency. 📈 Complexity: Time: O(n log m) → For each element in nums1, a binary search on nums2. Space: O(1) → Only a few variables used. ✨ Key Takeaway: Sometimes, monotonic properties allow you to blend binary search with iteration — turning what looks like a brute-force problem into a clean and efficient search-based solution. ⚡ 🔖 #DSA #100DaysOfCode #LeetCode #ProblemSolving #Algorithms #BinarySearch #TwoPointers #CodingChallenge #Python #InterviewPrep #TechCommunity #Optimization #EfficientCode #CodeEveryday

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

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