LCP Matrix Meets DSU: Reconstructing Strings with Disjoint Set Union

🚀 How LinkedList Solves What Arrays Cannot. (https://lnkd.in/g_8fWXFq ) ➡️ An array demands contiguous memory — every element must sit next to the other. But what if memory is scattered? That's exactly where LinkedList steps in, connecting nodes across RAM using addresses. Here are the key takeaways from the LinkedList session at TAP Academy by Sharath R sir : 🔹 The Node: Every element lives in a node — an object with a data field and the address of the next (and previous) node. It's not magic, it's just object references. 🔹 Singly vs Doubly: Singly LL has one link — forward traversal only. Doubly LL has two links — bidirectional. Java's LinkedList class uses Doubly LL internally. 🔹 Initial Capacity = 0: Unlike ArrayList (initial capacity 10), LinkedList pre-allocates nothing. Every add() creates a fresh node dynamically — no contiguous block needed. 🔹 Polymorphism hiding in plain sight: new LinkedList(arrayList) works because ArrayList IS-A Collection. Parent reference + child object = loose coupling. The same concept from OOP, live inside Collections. 🔹 Iterator vs ListIterator: Iterator moves forward only. ListIterator moves both ways — but declaring it as Iterator type blocks access to hasPrevious(). That's Inheritance at work — parent references can't reach specialized child methods. Visit this Interactive webpage to understand the concept by visualization : https://lnkd.in/g_8fWXFq #Java #LinkedList #CoreJava #TapAcademy #DataStructures #OOP #Collections #LearningEveryDay #SoftwareDevelopment #Programming

🔥 𝗗𝗮𝘆 𝟵𝟰/𝟭𝟬𝟬 — 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 𝗖𝗵𝗮𝗹𝗹𝗲𝗻𝗴𝗲 𝟭𝟱𝟯𝟵. 𝗞𝘁𝗵 𝗠𝗶𝘀𝘀𝗶𝗻𝗴 𝗣𝗼𝘀𝗶𝘁𝗶𝘃𝗲 𝗡𝘂𝗺𝗯𝗲𝗿 | 🟢 Easy | Java Marked as Easy — but the optimal solution is pure binary search brilliance. 🎯 🔍 𝗧𝗵𝗲 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 Given a sorted array, find the kth missing positive integer. Linear scan works — but can we do O(log n)? 💡 𝗧𝗵𝗲 𝗞𝗲𝘆 𝗜𝗻𝘀𝗶𝗴𝗵𝘁 At index i, the value arr[i] should be i+1 in a complete sequence. So missing numbers before arr[i] = arr[i] - 1 - i This lets us binary search on the count of missing numbers! ⚡ 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 — 𝗕𝗶𝗻𝗮𝗿𝘆 𝗦𝗲𝗮𝗿𝗰𝗵 ✅ If arr[mid] - 1 - mid < k → not enough missing numbers yet, go right ✅ Else → too many missing, go left ✅ After the loop, left + k gives the exact answer 𝗪𝗵𝘆 𝗹𝗲𝗳𝘁 + 𝗸? After binary search, left is the index where the kth missing number falls beyond. left numbers exist in the array before that point, so the answer is left + k. No extra passes needed. ✨ 📊 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 ⏱ Time: O(log n) — vs O(n) linear scan 📦 Space: O(1) This is a perfect example of binary searching on a derived condition, not just a value. A real upgrade from the naive approach. 🧠 📂 𝗙𝘂𝗹𝗹 𝘀𝗼𝗹𝘂𝘁𝗶𝗼𝗻 𝗼𝗻 𝗚𝗶𝘁𝗛𝘂𝗯: https://lnkd.in/gVYcjNS6 𝟲 𝗺𝗼𝗿𝗲 𝗱𝗮𝘆𝘀. 𝗧𝗵𝗲 𝗳𝗶𝗻𝗶𝘀𝗵 𝗹𝗶𝗻𝗲 𝗶𝘀 𝗿𝗶𝗴𝗵𝘁 𝘁𝗵𝗲𝗿𝗲! 🏁 #LeetCode #Day94of100 #100DaysOfCode #Java #DSA #BinarySearch #Arrays #CodingChallenge #Programming

Day 111: DSU, Graphs, and Hamming Distances 🧠⚡ Problem 1722: Minimize Hamming Distance After Swap Operations Today was a massive step up. I moved beyond simple pointers and dove into Disjoint Set Union (DSU) to solve a complex graph-based problem. The Strategy: • The Swap Logic: Since allowedSwaps can be chained, any indices in the same connected component can be rearranged freely. • Disjoint Set Union: I used DSU to group these indices. If index A can swap with B, and B with C, then {A, B, C} form a component where any value can move to any position. • Frequency Tracking: For each connected component, I used a nested HashMap to track the available numbers from the source. • Calculating the Distance: For each position, I checked if the target value existed in its component's pool. If not, the Hamming distance increased. The Java vs. C++ Choice: I actually tried implementing this in C++ first, but the time complexity turned out to be higher than expected for this specific logic. To ensure the most efficient O(N⋅α(N)) performance and clear the tight test cases, I stuck with Java for today’s solve. Day 111 in the books. Sometimes choosing the right tool for the specific problem is the most important engineering decision you can make. 🚀 #LeetCode #Java #DSU #Graphs #Algorithms #ProblemSolving #DailyCode

🚀 Day 32 of #128DaysOfCode Today I explored an efficient way to find the square root of a number without using built-in functions. Instead of the usual brute force or binary search, I implemented Newton’s Method (Babylonian Method) — a powerful mathematical approach that converges very fast. 🔹 The idea is to continuously improve our guess using: r = (r + x / r) / 2 This method quickly narrows down to the correct integer square root, making it both optimized and elegant. 💡 Key Takeaways: - Learned how mathematical concepts can optimize coding problems - Understood the importance of avoiding overflow using "long" - Practiced writing clean and efficient Java code 🔥 Consistency is the real game changer. Step by step, improving logic and problem-solving skills! #Java #DSA #CodingJourney #ProblemSolving #Consistency #LearnInPublic

When I first started learning C++, I learned that data structures in the STL, like vector, stack, queue, etc., use heap memory internally. But when I wrote: vector<int> vec; …it clearly looked like it lived on the stack. No object creation or destruction was visible (coming from Java, I was used to seeing the new keyword everywhere an object is created). So where exactly was this “heap magic” happening? Turns out, the vector object itself does live on the stack when declared normally. But internally, it maintains a pointer to dynamically allocated memory on the heap where the elements are stored. When the object goes out of scope, its destructor is automatically called, and that destructor is responsible for freeing the heap memory. So the cleanup also happens kind of automatically, if we understand what’s going on under the hood. This pattern follows a design principle called RAII (Resource Acquisition Is Initialisation) (more on that in the next post). What advantage does this approach provide? • You get the performance of stack allocation • You get the flexibility of heap allocation • And you still maintain control… woww Also, in C++, we can explicitly create objects on the heap when needed. For example: • to enable runtime polymorphism • to extend the lifetime of an object beyond a specific scope I guess complete resource control wasn’t that bad after all XD. Happy Coding :) #Cpp #LearningInPublic #SoftwareDevelopment #Coding #Algorithms #Programming

𝐋𝐞𝐞𝐭𝐂𝐨𝐝𝐞 𝐇𝐚𝐫𝐝 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝: 𝐅𝐢𝐧𝐝 𝐭𝐡𝐞 𝐒𝐭𝐫𝐢𝐧𝐠 𝐰𝐢𝐭𝐡 𝐋𝐂𝐏 𝐐𝐮𝐞𝐬𝐭𝐢𝐨𝐧 𝐋𝐢𝐧𝐤 :https://lnkd.in/gPQ5WExk 𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 𝐋𝐢𝐧𝐤 : https://lnkd.in/gYpvYnaW Today I worked on an interesting 𝐡𝐚𝐫𝐝 𝐩𝐫𝐨𝐛𝐥𝐞𝐦: 𝐅𝐢𝐧𝐝 𝐭𝐡𝐞 𝐒𝐭𝐫𝐢𝐧𝐠 𝐰𝐢𝐭𝐡 𝐋𝐂𝐏. The problem provides an 𝐋𝐂𝐏 (𝐋𝐨𝐧𝐠𝐞𝐬𝐭 𝐂𝐨𝐦𝐦𝐨𝐧 𝐏𝐫𝐞𝐟𝐢𝐱) 𝐦𝐚𝐭𝐫𝐢𝐱 and asks us to construct the lexicographically smallest string that satisfies this matrix.  𝐊𝐞𝐲 𝐈𝐝𝐞𝐚 Instead of constructing substrings directly, the approach is: 1️⃣ Start assigning characters from 'a' onward. 2️⃣ If lcp[i][j] > 0, it means the substrings starting at i and j share the same first character. 3️⃣ Propagate the same character across positions where the LCP value indicates a match. 4️⃣ Finally, validate the entire LCP matrix using the rule: lcp[i][j] = (word[i] == word[j]) ? 1 + lcp[i+1][j+1] : 0 If any condition fails, no valid string exists.  𝐖𝐡𝐚𝐭 𝐈 𝐥𝐞𝐚𝐫𝐧𝐞𝐝 • How LCP matrices represent relationships between substrings • Constructing strings using greedy character assignment • Validating constraints using dynamic programming relations • Importance of verifying generated structures against given matrices Problems like this really sharpen string manipulation + matrix reasoning skills. Always fun pushing through Hard-level challenges! #LeetCode #DataStructures #Algorithms #CodingPractice #Java #ProblemSolving

📘 DSA Journey — Day 22 Today’s focus: Prefix Sum + Fixed Window optimization. Problem solved: • K Radius Subarray Averages (LeetCode 2090) Concepts used: • Prefix Sum • Fixed-size sliding window • Efficient range sum calculation Key takeaway: The goal is to calculate the average of subarrays centered at each index with radius k. A brute-force approach would recompute sums for every index, leading to O(n·k) time. Instead, using prefix sum, we can compute any subarray sum in O(1) time. For each index i, the valid window is: [i - k, i + k] If this window is within bounds, we calculate the sum using prefix sum and divide by (2k + 1). If not enough elements exist on either side, we return -1. This approach reduces the complexity to O(n) and avoids repeated calculations. This problem highlights how prefix sum helps in efficiently handling range-based queries. Continuing to strengthen fundamentals and consistency in DSA problem solving. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 31 Today’s focus: Binary Search for boundaries and square roots. Problems solved: • Sqrt(x) (LeetCode 69) • Search Insert Position (LeetCode 35) Concepts used: • Binary Search • Search space reduction • Boundary conditions Key takeaway: In Sqrt(x), the goal is to find the integer square root. Using binary search, we search in the range [1, x] and check mid * mid against x to narrow down the answer. This avoids linear iteration and achieves O(log n) time. In Search Insert Position, we use binary search to find either: • The exact position of the target, or • The correct index where it should be inserted The key idea is that when the target is not found, the final position of the left pointer gives the correct insertion index. These problems highlight how binary search is not just for finding elements, but also for determining positions and boundaries efficiently. Continuing to strengthen fundamentals and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

Day 7 of Java with DSA Journey 🚀 📌 Topic: Missing Number (LeetCode 268) Quote: "Sometimes the best way to solve a coding problem is to put down the keyboard and pick up a calculator." ✨ What I learned today: 🔹 Mathematical Optimization: Instead of brute force, I used a simple formula to compute the expected sum. {Sum} = \frac{n(n+1)}{2} 🔹 Core Idea: Expected Sum − Actual Sum = Missing Number 🔹 Alternative Approach: Used XOR technique where duplicates cancel out → leaving the missing value. 🔹 Efficiency: ✔️ Time Complexity: O(n) ✔️ Space Complexity: O(1) 🧠 Problem Solved: ✔️ Missing Number 💡 Key Insight: We often jump to HashSet or Sorting, but this problem taught me to pause and think mathematically first. A simple formula reduced space complexity from O(n) → O(1) 🚀 ⚡ Interview Tip (Important!): Be careful of integer overflow in Java: n * (n + 1) can exceed int limit Use long OR switch to XOR method for safety Consistency is the real key 🔑 #DSA #LeetCode #Java #Mathematics #CodingJourney #ProblemSolving #Day7 #Algorithms #Optimization #Array #MCA #lnct #100DaysOfCode #Algorithms #SoftwareEngineering #InPlaceAlgorithms #TechLearning #JavaDeveloper