Prefix Sum + HashMap solves LeetCode 525

📅 Day 7 of My DSA Journey Today I solved the “Search Insert Position” problem on LeetCode using Java. This problem introduced me to the concept of Binary Search, one of the most important searching techniques in algorithms. 💡 Problem Overview Given a sorted array and a target value: If the target exists → return its index. If it does not exist → return the index where it should be inserted to keep the array sorted. Instead of checking every element (linear search), I used Binary Search to reduce the search space by half in every step. ⚙️ Approach I Used Defined two pointers: start (si) and end (ei) Calculated the middle index (mid) Compared nums[mid] with the target Adjusted the search range accordingly If the target was not found, returned the correct insert position This approach is efficient because it avoids unnecessary comparisons. ⚡ Challenges I Faced The tricky part was understanding what value to return when the element is not present in the array. I had to carefully track where the target should logically be inserted while adjusting the pointers. 🛠 How I Solved It I performed several dry runs and visualized how the pointers move in each iteration. This helped me understand how binary search naturally leads to the correct insertion index. 📊 Complexity Analysis Time Complexity: O(log n) Because Binary Search divides the array into halves each iteration. Space Complexity: O(1) Only a few variables are used, so no extra memory is required. 📚 Key Learnings Deep understanding of Binary Search How to handle edge cases when the target is not present Improved ability to analyze time and space complexity Every day I realize that DSA is not just about coding — it’s about thinking smarter and optimizing solutions. On to Day 8 tomorrow. The consistency continues. 💪 #DSA #100DaysOfCode #LeetCode #BinarySearch #ProblemSolving #CodingJourney #Java #LearningInPublic #Consistency #SoftwareDevelopment

🚀 Day 2/30 – Java DSA Challenge 🔎 Problem 13: 912. Sort an Array (LeetCode – Medium) Solved a fundamental sorting problem today 🔥 Sorting is one of the most important concepts in Data Structures and Algorithms. 🧠 Problem Statement Given an integer array nums, sort the array in ascending order and return it. ⚠ Constraint: Time complexity should be O(n log n) Avoid using built-in sorting functions 💡 Example Input: [5,2,3,1] Output: [1,2,3,5] ✅ Input: [5,1,1,2,0,0] Output: [0,0,1,1,2,5] 👨💻 Approach Used – Bubble Sort ✔ Compare adjacent elements ✔ Swap if they are in wrong order ✔ Repeat for n-1 passes This is a simple and beginner-friendly sorting algorithm. ⏱ Time Complexity: O(n²) – Nested loops 📦 Space Complexity: O(1) – In-place sorting 📌 Key Learning: Bubble Sort is simple but not efficient for large inputs. To meet the O(n log n) requirement, algorithms like Merge Sort or Quick Sort are better choices. Day 2 learning progressing to Medium level 💪🔥 Step by step towards stronger DSA fundamentals 🚀 #Day2 #30DaysOfCode #Java #DSA #LeetCode #Sorting #BubbleSort #CodingJourney #Consistency

🚀 Day 90 of My 100 Days LeetCode Challenge | Java Today’s challenge was a fascinating logic + mathematical insight problem. The task was to generate a binary string that does not exist in a given list of binary strings, where all strings have the same length. Instead of trying every possible combination, the solution becomes much simpler when you use the idea of diagonal flipping. By flipping the i-th bit of the i-th string, we guarantee that the newly created string differs from every string in the list at least in one position. This clever trick ensures the generated string is always unique. ✅ Problem Solved: Find Unique Binary String ✔️ All test cases passed (186/186) ⏱️ Runtime: 0 ms 🧠 Approach: Mathematical Insight (Diagonal Construction) 🧩 Key Learnings: ● Sometimes the smartest solutions come from mathematical reasoning rather than brute force. ● The diagonalization technique guarantees uniqueness. ● Understanding problem constraints can drastically simplify the approach. ● Logical insights can reduce exponential possibilities to linear solutions. ● Elegant algorithms often come from simple observations. This problem was a great reminder that a small logical trick can outperform complex algorithms. 🔥 Day 90 complete — sharpening my problem-solving intuition and algorithmic thinking. #LeetCode #100DaysOfCode #Java #Math #Algorithms #ProblemSolving #DSA #CodingJourney #Consistency

🚀 Day 5 – LeetCode Practice Today, I solved the Generate Parentheses problem on LeetCode: 🎯 Difficulty: Medium 💻 Language Used: Java 💡 Approach: • Given an integer n, the task was to generate all combinations of well-formed parentheses of length 2n. • I applied a backtracking technique to build combinations by adding ( and ) step by step. • Ensured the number of closing parentheses never exceeded opening ones during recursion. • Backtracking pruned invalid paths and constructed only valid sequences. ⏱ Complexity: • Time Complexity: O(Cn) (Catalan number of combinations) • Space Complexity: O(n) (for recursion stack) 📚 Key Takeaway: This problem strengthened my understanding of recursive backtracking and how constraints can guide efficient exploration of combinatorial solutions. Consistent problem-solving practice improves both logic and implementation confidence. 💪 #LeetCode #Java #DSA #Backtracking #Algorithms #ProblemSolving #100DaysOfCode #SoftwareDeveloper

🚀 DSA Learning Journey | Day 2 | Java Solved “Search in Rotated Sorted Array.” 💡 Key Idea: Applied Binary Search by determining which half of the array is sorted and narrowing the search space. ⚙ Implementation • Language: Java • Time Complexity: O(log n) • Space Complexity: O(1) 📚 Learning how binary search can be adapted to work with rotated sorted arrays. #Java #DSA #LeetCode #ProblemSolving #BinarySearch #JavaDeveloper

🚀 Day 6/30 – Java DSA Challenge 🔎 Problem 46: 704. Binary Search (LeetCode – Easy) Today I revised one of the most fundamental and important algorithms in DSA — Binary Search 🔥 🧠 Problem Summary Given: A sorted array nums (ascending order) A target value 🎯 Return the index of the target if found Otherwise return -1 ⚠️ Required Time Complexity: O(log n) 💡 Key Insight Since the array is sorted, we can: ✅ Eliminate half of the search space in every step. That’s the power of Binary Search. 🔄 Approach 1️⃣ Initialize two pointers: low = 0 high = n - 1 2️⃣ While low <= high: Find mid If arr[mid] == target → return mid If arr[mid] < target → search right half Else → search left half 3️⃣ If not found → return -1 ⏱ Time Complexity O(log n) 📦 Space Complexity O(1) 📌 Pattern Used ✔ Divide and Conquer ✔ Binary Search on Sorted Array ✔ Logarithmic Search Optimization 🎯 Key Learning Always use safe mid calculation: mid = low + (high - low) / 2 (prevents integer overflow) Binary Search is the foundation for: Lower Bound / Upper Bound Search in Rotated Array Peak Element First/Last Occurrence Search on Answer problems 🔥 46 Problems Completed Day 6 = Strong fundamentals reinforced 💪 Master basics → Master advanced problems 🚀 #Day6 #30DaysOfCode #Java #DSA #LeetCode #BinarySearch #InterviewPrep #ProblemSolving #Consistency

✨ Consistency beats intensity — and this week proved it again. ✨ 🚀 DSA Journey | Week 3 Update — Strings & StringBuilder (Java) This week marked an important milestone in my Decode Java + DSA journey at PW Skills. Under the guidance of Raghav Garg Sir, I dived deep into one of the most fundamental yet powerful topics in Java — Strings & StringBuilder. 📚 What I worked on this week: ✔️ Core understanding of Strings in Java ✔️ Immutability & Interning — why Strings behave the way they do ✔️ Difference between == and equals() ✔️ Hands-on with StringBuilder for performance-optimized operations ✔️ Mastered key methods like charAt(), substring(), compareTo(), reverse(), append() ✔️ Solved real DSA problems including: Anagrams Toggle case Substring generation String compression Reverse words in a sentence Frequency-based problems 🧠 Learning takeaway: Understanding when to use String vs StringBuilder is not just theory — it directly impacts performance and clean code. 💻 Practice & Problem Solving: I actively solved problems on trusted platforms to strengthen concepts: 🔗 GeeksforGeeks Profile: https://lnkd.in/gbejmRg2 🔗 LeetCode Profile: https://lnkd.in/gUp8nBdn This is Week 3, and I’m focused on building strong foundations before moving fast. Grateful for structured guidance, quality problems, and the discipline this journey is building. 📈 Onward to the next week — one concept, one problem, one improvement at a time. #DSAJourney #Java #Strings #StringBuilder #ProblemSolving #PWSkills #DecodeJava #LearningInPublic #Consistency #GeeksforGeeks #LeetCode #FutureSoftwareEngineer

🚀 Day 8 – LeetCode Practice Today, I solved the Search in Rotated Sorted Array problem on LeetCode: 🎯 Difficulty: Medium 💻 Language Used: Java 💡 Approach: • Given a rotated sorted array and a target value, the task was to find the index of the target if it exists — otherwise return -1. • I used a modified binary search to find the target in O(log n) time. • At each step, I determined which half of the array was sorted and used that information to decide where the target could lie. • This careful range narrowing allowed efficient searching even after rotation. ⏱ Complexity: • Time Complexity: O(log n) • Space Complexity: O(1) 📚 Key Takeaway: This problem reinforced how binary search can be adapted beyond simple sorted arrays to handle rotated scenarios by identifying sorted subranges at each step. Consistent problem-solving practice continues to sharpen my algorithmic intuition and implementation skills. 💪 #LeetCode #Java #DSA #BinarySearch #Algorithms #ProblemSolving #CodingPractice #100DaysOfCode #SoftwareDeveloper

🚀 Day 56 Out of #365DaysOfCode Github Link: https://lnkd.in/gGUy_MKZ Today I solved an interesting problem sort an integer array based on the number of 1’s in its binary representation. If two numbers have the same number of set bits, sort them in ascending numerical order. 🔎 Key Concept: Use Integer.bitCount() to count the number of 1’s. Apply a custom comparator with Arrays.sort(). Handle tie-breaking by normal ascending comparison. 💡 This problem is a great reminder of how powerful Java’s built-in methods and custom comparators can be for writing clean and efficient solutions. Time Complexity: O(n log n) It’s always exciting to explore bit manipulation problems—they strengthen logical thinking and deepen understanding of how numbers work internally. #Java #Coding #DataStructures #Algorithms #BitManipulation #ProblemSolving #Learning

🚀 Day 85 of My 100 Days LeetCode Challenge | Java Today’s problem was a beautiful recursion + pattern observation challenge. We had to find the k-th bit in a recursively defined binary string sequence — and the string grows exponentially with each step. Clearly, constructing the entire string was not an option. The breakthrough came from understanding the structure: Each sequence is built as: S(n) = S(n-1) + "1" + reverse(invert(S(n-1))) Once I noticed the symmetry around the middle element and how the second half mirrors the first (with inversion), the solution became a clean recursive reduction instead of brute force. ✅ Problem Solved: Find K-th Bit in N-th Binary String ✔️ All test cases passed (63/63) ⏱️ Runtime: 0 ms (Beats 100%) 🧠 Approach: Recursion + Divide & Conquer + Symmetry Observation 🧩 Key Learnings: ● Never build exponential structures directly — reduce the problem. ● Recursive definitions often hide symmetry. ● The middle element becomes a powerful pivot. ● Mirroring + inversion patterns simplify complex generation problems. ● Think structurally, not sequentially. This problem reminded me that many recursive constructions are just cleverly disguised divide-and-conquer problems. 🔥 Day 85 complete — stronger recursion intuition and pattern recognition sharpening further. #LeetCode #100DaysOfCode #Java #Recursion #DivideAndConquer #ProblemSolving #DSA #CodingJourney #Consistency