Prim's Algorithm for Minimum Spanning Tree

🚀 #LeetCode Day Problem Solving 🚀 Day-30 📌 Problem: You are given a circular array nums and an array queries. For each query index i, find the minimum circular distance to another index j such that: ✔ nums[j] == nums[queries[i]] ✔ If no such index exists → return -1 🧠 Example: Input: nums = [1,3,1,4,1,3,2] queries = [0,3,5] ✅ Output: [2, -1, 3] 📖 Explanation: Query 0 → value = 1 → nearest same value at index 2 → distance = 2 Query 1 → value = 4 → no duplicate → -1 Query 2 → value = 3 → nearest at index 1 (circular path) → distance = 3 💡 Key Insight: ✔ Since array is circular, distance = 👉 min(|i - j|, n - |i - j|) ✔ Store indices of each value using a map (value → list of indices) ✔ For each query: 👉 Use binary search to find nearest index efficiently 📊 Complexity Analysis: ⏱ Time Complexity: O(n + q log n) 📦 Space Complexity: O(n) 🧠 What I Learned: ✔ Handling circular arrays smartly ✔ Using binary search on index lists ✔ Optimizing brute force to efficient lookup ✅ Day 30 Completed 🚀 Leveling up in Arrays + Binary Search + Optimization 💪 #Leetcode #DSA #ProblemSolving #BitManipulation #CodingJourney #InterviewPreparation #Consistency

🚀 LeetCode Day Problem Solving 🚀 Day-50 📌 Problem: You are given a circular array nums and an array queries. For each query index i, find the minimum circular distance to another index j such that: ✔ nums[j] == nums[queries[i]] ✔ If no such index exists → return -1 🧠 Example: Input: nums = [1,3,1,4,1,3,2] queries = [0,3,5] ✅ Output: [2, -1, 3] 📖 Explanation: Query 0 → value = 1 → nearest same value at index 2 → distance = 2 Query 1 → value = 4 → no duplicate → -1 Query 2 → value = 3 → nearest at index 1 (circular path) → distance = 3 💡 Key Insight: ✔ Since array is circular, distance = 👉 min(|i - j|, n - |i - j|) ✔ Store indices of each value using a map (value → list of indices) ✔ For each query: 👉 Use binary search to find nearest index efficiently 📊 Complexity Analysis: ⏱ Time Complexity: O(n + q log n) 📦 Space Complexity: O(n) 🧠 What I Learned: ✔ Handling circular arrays smartly ✔ Using binary search on index lists ✔ Optimizing brute force to efficient lookup ✅ Day 50 Completed 🚀 Leveling up in Arrays + Binary Search + Optimization 💪 #Leetcode #DSA #ProblemSolving #BitManipulation #CodingJourney #InterviewPreparation #Consistency #MilanSahoo 🚀

🚀 LeetCode Day Problem Solving 🚀 Day-57 📌 Problem: For each index i in array nums, compute: 👉 arr[i] = sum of |i - j| for all j such that nums[j] == nums[i] and j ≠ i ✔ If no such j exists → arr[i] = 0 🧠 Example: Input: nums = [1,3,1,1,2] ✅ Output: [5,0,3,4,0] 📖 Explanation: For value 1 → indices = [0,2,3] For index 0: → |0-2| + |0-3| = 5 For index 2: → |2-0| + |2-3| = 3 For index 3: → |3-0| + |3-2| = 4 💡 Key Insight: ✔ Group indices by same values (using HashMap) ✔ For each group, compute distances efficiently 👉 Instead of brute force O(n²) ❌ Use Prefix Sum on indices 🔥 ⚡ Optimized Approach: 1️⃣ Store indices for each value 2️⃣ For each group: Maintain prefix sum of indices Use formula to compute distance in O(1) per index 👉 Left contribution + Right contribution 📊 Complexity Analysis: ⏱ Time Complexity: O(n) 📦 Space Complexity: O(n) 🧠 What I Learned: ✔ Grouping using HashMap ✔ Using prefix sums on indices ✔ Turning brute force into efficient solution ✅ Day 57 Completed 🚀 Leveling up in Hashing + Prefix Sum Optimization 💪 #Leetcode #DSA #ProblemSolving #BitManipulation #CodingJourney #InterviewPreparation #Consistency #MilanSahoo 🚀

🚀 #LeetCode Day Problem Solving 🚀 Day-37 📌 Problem: For each index i in array nums, compute: 👉 arr[i] = sum of |i - j| for all j such that nums[j] == nums[i] and j ≠ i ✔ If no such j exists → arr[i] = 0 🧠 Example: Input: nums = [1,3,1,1,2] ✅ Output: [5,0,3,4,0] 📖 Explanation: For value 1 → indices = [0,2,3] For index 0: → |0-2| + |0-3| = 5 For index 2: → |2-0| + |2-3| = 3 For index 3: → |3-0| + |3-2| = 4 💡 Key Insight: ✔ Group indices by same values (using HashMap) ✔ For each group, compute distances efficiently 👉 Instead of brute force O(n²) ❌ Use Prefix Sum on indices 🔥 ⚡ Optimized Approach: 1️⃣ Store indices for each value 2️⃣ For each group: Maintain prefix sum of indices Use formula to compute distance in O(1) per index 👉 Left contribution + Right contribution 📊 Complexity Analysis: ⏱ Time Complexity: O(n) 📦 Space Complexity: O(n) 🧠 What I Learned: ✔ Grouping using HashMap ✔ Using prefix sums on indices ✔ Turning brute force into efficient solution ✅ Day 37 Completed 🚀 Leveling up in Hashing + Prefix Sum Optimization 💪 #Leetcode #DSA #ProblemSolving #BitManipulation #CodingJourney #InterviewPreparation #Consistency

🧠 Day 202 — Minimum Spanning Tree (Prim’s Algorithm) 🌳⚡ Today I solved Minimum Spanning Tree (MST) using Prim’s Algorithm, a core concept in graph optimization. 📌 Problem Goal Given a weighted undirected graph: ✔️ Connect all vertices ✔️ Minimize total edge weight ✔️ No cycles allowed 🔹 Core Idea Grow the tree step by step: 👉 Always pick the minimum weight edge connecting a new node 🔹 Approach 1️⃣ Build adjacency list 2️⃣ Use a min-heap (priority queue) 3️⃣ Start from any node (e.g., 0) 4️⃣ Pick the smallest edge → add to MST 5️⃣ Mark node as visited and push its neighbors 🔹 Key Insight ✔️ Greedy choice → always take smallest edge ✔️ Avoid revisiting nodes to prevent cycles ✔️ Heap ensures optimal edge selection 🧠 Key Learning ✔️ Prim’s = BFS + Priority Queue mindset ✔️ Works well with adjacency list representation ✔️ MST problems are about optimization, not paths 💡 Today’s Realization Graph algorithms now feel like a complete system: • BFS / DFS → Traversal • Dijkstra → Shortest Path • Bellman-Ford → Negative weights • Floyd-Warshall → All pairs • Prim’s → Minimum Spanning Tree Different goals, same graph foundation. 🚀 Momentum Status: Graph concepts are now deeply connected. On to Day 203. #DSA #Graphs #MinimumSpanningTree #PrimsAlgorithm #LeetCode #Java #CodingJourney #ConsistencyWins

Day 3: LeetCode – 74. Search a 2D Matrix Today I solved a problem that looks like a 2D matrix question but is actually a binary search problem in disguise. Key Insight: Although the input is a matrix, the constraints ensure it behaves like a single sorted array. That allows us to apply binary search across the entire matrix in O(log(m × n)) time. My Approach: • Treated the matrix as a single sorted list • Applied binary search on the range [0 … m×n − 1] • Converted the mid index back to matrix coordinates using: – row = mid / n – col = mid % n • Compared the value at that position with the target and adjusted the search range Takeaway: A shift in perspective can simplify seemingly complex problems. Recognizing hidden patterns is as important as knowing algorithms. Day 3 completed. #DSA #LeetCode #BinarySearch #ProblemSolving

Day 33 Today I solved: Two Sum II – Input Array Is Sorted (LeetCode 167) 💡 Problem: Given a sorted array, find two numbers such that they add up to a target. Return their 1-based indices. --- 💡 My Approach: Since the array is already sorted, I used the Two Pointer Technique instead of a HashMap: 1️⃣ Start with two pointers: left = 0 right = n - 1 2️⃣ Calculate sum: If sum == target → ✅ found the answer If sum < target → move left++ (increase sum) If sum > target → move right-- (decrease sum) 3️⃣ Continue until the pair is found 💡 Key Insight: Use the sorted property to your advantage 🚀 No need for extra space like HashMap ❌ Two pointers give an optimal solution ✅ ⚡ Complexity: Time: O(n) Space: O(1) #LeetCode #DSA #LearnInPublic

🚀 Day 69 of #100DaysOfDSA Another step deeper into optimization techniques ⚡ 🧩 Problem Solved: LeetCode 2121 – Intervals Between Identical Elements 💡 Key Idea: Brute force would be too slow ❌ → Optimize using prefix sums + grouping 🔍 Approach: Store indices of each value using a hash map For each group of indices: Use prefix sum to compute left & right distances efficiently Build the final answer in linear time ⚡ Result: ⏱️ 0 ms runtime 💯 📈 Optimized from O(n²) → O(n) 📚 Concepts Practiced: ✅ Prefix Sum ✅ Hash Map ✅ Efficient Distance Calculation 💭 Lesson Learned: When same values repeat: ➡️ Think grouping + precomputation ➡️ Avoid recalculating distances again & again Consistency is the real win 🚀 #100DaysOfDSA #LeetCode #Day69 #DSA #PrefixSum #Hashing #CodingJourney #ProblemSolving

Day 30 Today I solved “Top K Frequent Elements” on LeetCode. The problem is to find the k most frequent elements in an array. At first, I thought about sorting or using a heap — but then I learned a more optimal approach: 💡 Bucket Sort + HashMap Approach: Use a HashMap to count frequency of each element Create a bucket array where index = frequency Store elements based on their frequency Traverse from highest frequency to get top k elements 💡 Why this is powerful: Time Complexity: O(n) ✅ Space Complexity: O(n) 👉 Faster than heap-based solution (O(n log k)) 💡 Key takeaway: Sometimes, instead of sorting, we can use frequency-based grouping (bucket sort) to achieve optimal performance. 💡 What I learned: HashMap for frequency counting Bucket sort for grouping Avoiding unnecessary sorting #LeetCode #DSA #LearnInPublic

🚀 Day 42/100 – #100DaysOfDSA Back again with trees 🌳 (starting to feel like home now 😄) 🔹 Problem Solved: • Balanced Binary Tree ✅ 💡 Key Learning: This problem clicked when I stopped thinking separately and used a combined approach: → Return (isBalanced, height) together → Check balance while calculating height → Avoids recalculating height again & again (optimized 💯) ⚡ Core Insight: Instead of: ❌ Checking height again and again (O(n²)) Do this: ✅ Compute everything in one recursion (O(n)) 🧠 This is where recursion gets powerful — you don’t just return values, you return information. 📈 Feeling more confident with: • Tree recursion patterns • Optimized thinking • Writing clean recursive code Consistency still ON 🔥 Day 43 loading… 🚀 #DSA #BinaryTree #Recursion #CodingJourney #100DaysOfCode #CPP