Kth Missing Positive Number LeetCode 1539 Binary Search

🔥 DSA Challenge – Day 119/360 🚀 📌 Topic: Recursion / Math 🧩 Problem: Pow(x, n) Problem Statement: Find x raised to the power n (xⁿ) efficiently, even for large values of n. 🔍 Example: Input: x = 2, n = 5 Output: 32 💡 Approach: Optimized (Binary Exponentiation) 1️⃣ Step 1 – If n is negative, convert → x = 1/x and n = -n 2️⃣ Step 2 – Recursively calculate half = power(x, n/2) 3️⃣ Step 3 – • If n is even → return half × half • If n is odd → return half × half × x ⏱ Complexity: Time: O(log n) Space: O(log n) 📚 Key Learning: Breaking a problem into halves can drastically improve performance 🚀 #DSA #Java #Coding #InterviewPrep #ProblemSolving #TechJourney #119DaysOfCode #LeetCode

🔥 Day 83 of my LeetCode Journey 🔥 📘 Problem: 367. Valid Perfect Square 🎯 Difficulty: Easy 🔹 Problem Statement: Given a positive integer num, return true if num is a perfect square, otherwise return false. A perfect square is an integer that is the square of another integer. You must not use any built-in library function like sqrt. 🔹 Approach Used: Apply Binary Search on range 0 to num Find mid and compute mid * mid If equal to num → return true If mid * mid is greater → search left half If smaller → search right half Repeat until condition satisfies or range ends 🔹 Key Concepts: Binary Search Handling large numbers (use long to avoid overflow) Mathematical reasoning Efficient searching 🔹 Learning: This problem shows how binary search can be applied beyond arrays to mathematical problems. It also emphasizes handling overflow carefully when dealing with large 📌 Think beyond arrays — binary search works on answer space too 🚀 #LeetCode #Day83 #Java #BinarySearch #Math #DSA #ProblemSolving

🚀 DSA Preparation 💪 Solved a fundamental Binary Search problem, a key concept for efficient searching. Focused on reducing search space by half in each step to achieve optimal performance 🔥 🧠 Problem 🔎 Binary Search Given a sorted array nums and a target value, return its index if found. If the target does not exist, return -1. 👉 The solution must run in O(log n) time complexity. Example Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 ⚡ Key Learning 📌 Binary Search works only on sorted arrays 📌 Each step halves the search space → highly efficient 📌 Time Complexity: O(log n) 📌 Space Complexity: O(1) Improving DSA with strong fundamentals 🚀 #DSA #LeetCode #BinarySearch #Algorithms #Java #ProblemSolving #Consistency

🚀 Day 22 of My DSA Journey Today I solved an important Binary Search problem: 👉 Find First and Last Position of Element in Sorted Array 🧩 Problem Understanding Given a sorted array and a target value, we need to find the starting and ending position of the target element. If the target is not present, return [-1, -1]. 🔍 Approach I Used (Binary Search x2) Instead of linear search, I used Binary Search twice: ✔️ First Binary Search → to find the first occurrence ✔️ Second Binary Search → to find the last occurrence 💡 Trick: Even after finding the target, we don’t stop — we continue searching on left/right side to get the boundary indices. ⚡ Why this approach? Because the array is sorted → Binary Search reduces time complexity drastically. ⏱ Time Complexity: O(log n) 📦 Space Complexity: O(1) 🔥 Key Learning Binary Search is not just for finding elements — it can also be used to find boundaries, ranges, and conditions. Consistency is the real game changer 💪 One problem at a time! #DSA #BinarySearch #LeetCode #Java #ProblemSolving #100DaysOfCode #CodingJourney #LearningInPublic

📘 DSA Journey — Day 34 Today’s focus: Binary Search on answer space. Problem solved: • Arranging Coins (LeetCode 441) Concepts used: • Binary Search • Mathematical observation • Search space reduction Key takeaway: The goal is to find how many complete rows of coins can be formed, where the i-th row requires i coins. This forms a sequence: 1 + 2 + 3 + ... + k ≤ n Instead of iterating linearly, we use binary search on k: Check if: k * (k + 1) / 2 ≤ n • If true → try larger k • Else → reduce k This allows us to find the maximum valid k in O(log n) time. Continuing to strengthen fundamentals and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

🚀 Solved a neat Difference Array problem today! 💡 Problem: Given an array and a set of range queries, determine whether it’s possible to make the entire array zero using the allowed operations. 🧠 Approach: Instead of applying each query directly (which would be slow), I used: • Difference Array for efficient range updates • Prefix Sum to compute actual impact at each index ⚡ Key Idea: Each query contributes to a range. By marking where the effect starts and ends, we can efficiently calculate how many times each index can be reduced. Then, for every index: • Compare available operations with required value • If available < required → not possible 📈 Complexity: O(n + q) — efficient and scalable 🔥 Key Learning: Using a Difference Array avoids repeated work and helps optimize range-based problems significantly. #LeetCode #DSA #Java #Coding #ProblemSolving #Arrays #Algorithms

🚀 DSA Preparation 💪 Solved an advanced Binary Search problem on a rotated sorted array. Learned how to identify the sorted half and efficiently narrow down the search space 🔥 🧠 Problem 🔎 Search in Rotated Sorted Array Given a sorted array nums that is rotated at an unknown index, and a target value: 👉 Return the index of the target if found, otherwise return -1. 👉 The solution must run in O(log n) time complexity. Example Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Input: nums = [1], target = 0 Output: -1 ⚡ Key Learning 📌 Even after rotation, one half of the array is always sorted 📌 Use Binary Search to decide which half to explore 📌 Time Complexity: O(log n) → reduces search space by half in each step, making it highly efficient even for large inputs 📌 Space Complexity: O(1) Improving DSA with advanced searching techniques 🚀 #DSA #LeetCode #BinarySearch #Algorithms #Java #ProblemSolving #Consistency

🔥 DSA Challenge – Day 131/360 🚀 📌 Topic: Backtracking / Recursion 🧩 Problem: N-Queens Problem Statement: Place N queens on an N×N chessboard such that no two queens attack each other. 🔍 Example: Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]] 💡 Approach: Optimized Backtracking (Hashing) 1️⃣ Step 1 – Try placing a queen column by column 2️⃣ Step 2 – Use arrays to check if row & diagonals are safe in O(1) 3️⃣ Step 3 – Place queen → recurse → backtrack if needed ⏱ Complexity: Time: O(N!) Space: O(N) + recursion stack 📚 Key Learning: Using hashing for rows & diagonals avoids repeated checks and makes backtracking much faster ⚡ #DSA #Java #Coding #InterviewPrep #ProblemSolving #TechJourney #131DaysOfCode #LeetCode

🚀 LeetCode Challenge 27/50 💡 Approach: Classic Binary Search The problem itself demands O(log n) — no room for linear search! Binary Search is one of the most fundamental algorithms in computer science, and mastering it is non-negotiable for every developer. 🔍 Key Insight: → Maintain left and right pointers on the sorted array → Calculate mid = left + (right - left) / 2 — NOT (left+right)/2 → Why? (left+right) can cause INTEGER OVERFLOW for large values! → nums[mid] == target → found! → nums[mid] < target → search right half (left = mid+1) → nums[mid] > target → search left half (right = mid-1) 📈 Complexity: ❌ Linear Search → O(n) Time ✅ Binary Search → O(log n) Time, O(1) Space Real impact: For n=1,000,000 → Linear needs 1M comparisons, Binary Search needs just 20! That's the power of logarithms. 🔥 #LeetCode #DSA #BinarySearch #Java #ADA #PBL2 #LeetCodeChallenge #Day27of50 #CodingJourney #ComputerEngineering #AlgorithmDesign #SearchAlgorithm

🚀 LeetCode Challenge 33/50 💡 Approach: Math (Digit Extraction + Overflow Check) Can't use 64-bit long — the problem forbids it! So we reverse digit by digit using modulo, but check for overflow BEFORE it happens using Integer.MAX_VALUE and MIN_VALUE bounds! 🔍 Key Insight: → Extract last digit: digit = x % 10, then x /= 10 → Build reversed number: result = result * 10 + digit → Before appending, check overflow: • result > MAX_VALUE / 10 → overflow! • result == MAX_VALUE / 10 && digit > 7 → overflow! • Same logic for negative (MIN_VALUE, digit < -8) → Return 0 if overflow detected 📈 Complexity: ✅ Time: O(log x) — number of digits in x ✅ Space: O(1) — only integer variables used The real challenge wasn't reversing — it was handling overflow WITHOUT using long. Edge cases are what separate good solutions from great ones! 🎯 #LeetCode #DSA #Math #Java #ADA #PBL2 #LeetCodeChallenge #Day33of50 #CodingJourney #ComputerEngineering #AlgorithmDesign #ReverseInteger