DSU and Graphs for Minimizing Hamming Distance

🧠 Day 215 — Mean of Range in Array 📊⚡ Today solved a clean problem using Prefix Sum, a must-know technique for range queries. 📌 Problem Goal Given an array and multiple queries: ✔️ Each query asks for the mean (average) of a subarray ✔️ Return the floor value of that mean 🔹 Core Idea Instead of calculating sum for every query (which is slow): 👉 Precompute prefix sum array ✔️ prefix[i] = sum of elements from 0 → i 🔹 Query Optimization For any range [l, r]: ✔️ Sum = prefix[r] − prefix[l−1] ✔️ Mean = sum / length This makes each query O(1) 🔹 Key Observation ✔️ Preprocessing once → fast multiple queries ✔️ Handles large constraints efficiently ✔️ Avoids repeated summation 🧠 Key Learning ✔️ Prefix Sum is essential for range query problems ✔️ Time complexity improves from O(n * q) → O(n + q) ✔️ Always think preprocessing when queries are multiple 💡 Big Realization Whenever you see: 👉 “Range sum / average queries” 👉 “Multiple queries on same array” Think: ➡️ Prefix Sum 🚀 Momentum Status: Strong grip on array optimization techniques. On to Day 216. #DSA #PrefixSum #Arrays #Optimization #LeetCode #Java #CodingJourney #ConsistencyWins

🚀 Day 88 — Prefix Sum Pattern (Pivot Index) Continuing the prefix sum journey — today I solved a problem that finds the equilibrium point where the sum of elements to the left equals the sum to the right. This is a great example of optimizing space using simple math. 📌 Problem Solved: LeetCode 724 – Find Pivot Index 🧠 Optimized Approach – Single Pass with Total Sum: java int total = 0, leftSum = 0; for (int num : nums) total += num; for (int i = 0; i < nums.length; i++) { // rightSum = total - leftSum - nums[i] if (leftSum == total - leftSum - nums[i]) return i; leftSum += nums[i]; } return -1; Why this works: total = sum of all elements. At index i, rightSum = total - leftSum - nums[i]. No need to store prefix/suffix arrays — just update leftSum as we go. Space complexity drops from O(n) to O(1). Key Insight from Revision: Earlier we discussed the Pivot Index optimization using the relationship: Total Sum = Left Sum + arr[i] + Right Sum → Right Sum = Total Sum - Left Sum - arr[i] This eliminates extra arrays. Edge Cases: Pivot at index 0 → left sum = 0. Pivot at last index → right sum = 0. No pivot → return -1. 💡 Takeaway: Not every prefix sum problem needs extra arrays. Recognizing when you can derive one side from the total sum and the other side saves space and simplifies code. No guilt about past breaks — just mastering optimizations within patterns. #DSA #PrefixSum #PivotIndex #LeetCode724 #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

Day 118: Finding the Middle Ground 🎯 Problem 2033: Minimum Operations to Make a Uni-Value Grid Today was a lesson in mathematical optimization. After a brute force approach led to a TLE, I realized that to minimize total operations, all numbers must converge toward the median. The Strategy: • Median Magic: In any "minimum total distance" problem, the median is the optimal point to minimize the sum of absolute differences. • The "X" Constraint: For a solution to even exist, every value in the grid must be reachable by steps of x. I checked this by ensuring (val - min_val) % x == 0. • Execution: I flattened the grid into a 1D array, sorted it to find the median, and calculated the total operations needed to move every element there. Java vs. C++: I experimented with both today, but my Java implementation actually clocked in faster for this specific logic, so I'm sticking with Java for the win today. Sometimes you have to slow down, find the center, and optimize. Day 118—keeping the streak alive. 🚀 #LeetCode #Java #Algorithms #Math #ProblemSolving #DailyCode

Day 45 of Daily DSA 🚀 Solved LeetCode 867: Transpose Matrix ✅ Problem: Given a 2D matrix, return its transpose (rows become columns and columns become rows). Approach: Created a new matrix and swapped indices while traversing. Steps: Get number of rows and columns Create a new matrix of size cols x rows Traverse original matrix Assign: trans[j][i] = matrix[i][j] Return the new matrix ⏱ Complexity: • Time: O(n × m) • Space: O(n × m) 📊 LeetCode Stats: • Runtime: 0 ms (Beats 100%) ⚡ • Memory: 46.46 MB Simple transformations like transpose build strong fundamentals for matrix-based problems 💡 #DSA #LeetCode #Java #Arrays #Matrix #CodingJourney #ProblemSolving

📘 DSA Journey — Day 35 Today’s focus: Binary Search with index patterns. Problem solved: • Single Element in a Sorted Array (LeetCode 540) Concepts used: • Binary Search • Index parity (even/odd pattern) • Search space reduction Key takeaway: The array is sorted and every element appears twice except one. A key observation: Before the single element, pairs start at even indices After the single element, this pattern breaks. Using binary search: • If mid is even and nums[mid] == nums[mid + 1], the single element lies on the right side • Else, it lies on the left side (including mid) By leveraging this pattern, we can find the answer in O(log n) time and O(1) space. Continuing to strengthen binary search intuition and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

💡 Day 64 of LeetCode Problem Solved! 🔧 🌟 2033. Minimum Operations to Make a Uni-Value Grid 🌟 🔗 Solution Code: https://lnkd.in/gts2KBqr 🧠 Approach: • Flattened the 2D grid into a sorted 1D list. • Chose the median as the target value — it minimises total absolute deviation mathematically. • Early-exit with -1 if any element has a different remainder mod x than the median. • Summed |element - median| / x for all elements to get the answer. ⚡ Key Learning: • The median is the optimal target for minimising sum of absolute differences — a powerful mathematical insight that replaces brute-force enumeration entirely. • A simple remainder check handles all impossible cases upfront. ⏱️ Complexity: • Time: O(m·n·log(m·n)) • Space: O(m·n) #LeetCode #Java #DSA #ProblemSolving #Consistency #CodingJourney #Algorithms #Grid

**Day 115 of #365DaysOfLeetCode Challenge** Today’s problem: **Diagonal Traverse (LeetCode 498)** A smart **matrix traversal** problem where the goal is to print all elements in zigzag diagonal order. Example: ```text id="k44nq2" 1 2 3 4 5 6 7 8 9 ``` Output: `[1,2,4,7,5,3,6,8,9]` **Core Idea:** Each diagonal is identified by: `row + col` * If `(row + col)` is even → move **up-right** * If `(row + col)` is odd → move **down-left** This removes the need for an extra direction variable. 📌 **Approach:** 1️⃣ Start at `(0,0)` 2️⃣ Add current element to result 3️⃣ Check parity of `(row + col)` 4️⃣ Move diagonally 5️⃣ If boundary reached, adjust row/col accordingly Repeat until all cells are visited. ⚡ **Time Complexity:** O(m × n) ⚡ **Space Complexity:** O(1) extra (excluding output) **What I learned today:** Sometimes parity (`row + col`) can simplify movement logic beautifully. Instead of tracking direction separately: 👉 Even diagonal = upward 👉 Odd diagonal = downward 💭 **Key Takeaway:** Great solutions often replace state variables with mathematical patterns. #LeetCode #DSA #Matrix #Arrays #Traversal #Java #CodingChallenge #ProblemSolving #TechJourney #Consistency

🚀 LeetCode 207 – Course Schedule | From Multiple Approaches → Cleaner Thinking While working on graph problems, I revisited Course Schedule and explored multiple implementations in Java — not just to solve it, but to understand why each approach works. 🔍 Core Idea Courses + prerequisites → Directed Graph Goal → Check if graph has a cycle 👉 If cycle exists → ❌ cannot finish all courses 👉 If no cycle → ✅ valid ordering exists (DAG) 💡 Approach 1: BFS (Kahn’s Algorithm) Build graph + compute in-degree Process nodes with in-degree = 0 Count processed nodes ✔ Intuitive (layer-by-layer removal) ✔ Great for topological sorting ❗ Slight overhead (separate passes) 💡 Approach 2: DFS (Visited + Recursion Stack) Track visited[] and recStack[] Detect back-edge → cycle ✔ Strong conceptual clarity ✔ Useful for many graph problems ❗ Extra space for 2 arrays 💡 Approach 3: Optimized BFS (Single Pass) ⭐ Build graph + in-degree together Use ArrayDeque for performance No extra passes ✔ Cleaner ✔ More efficient in practice ✔ Interview-friendly 💡 Approach 4: DFS with State Array (Latest Submission) 🔥 // 0 = unvisited, 1 = visiting, 2 = visited Replace visited[] + recStack[] with single state[] Detect cycle when visiting a node already in state = 1 ✔ Same time complexity → O(V + E) ✔ Reduced space usage ✔ Cleaner logic (less bookkeeping) 🔥 What Changed My Understanding Same problem. Same complexity. But different implementations gave me: Better control over graph traversal patterns Clear understanding of cycle detection Ability to optimize space without changing logic 📌 Takeaway Don’t stop at “Accepted” ✅ Push further: Try another approach Optimize space or structure Compare trade-offs That’s where real growth happens. #Java #DSA #Graphs #LeetCode #TopologicalSort #BackendDevelopment #LearningInPublic

Day 55/75 — Shortest Subarray with Sum at Least K Today’s problem was a challenging one involving prefix sums and a monotonic deque. Approach: • Use prefix sum to convert subarray sum into difference of indices • Maintain a deque to keep indices in increasing order of prefix sums • Remove useless indices to keep it optimal Key logic: while (!dq.isEmpty() && ps[j] - ps[dq.peekFirst()] >= k) { minLen = Math.min(minLen, j - dq.pollFirst()); } while (!dq.isEmpty() && ps[j] <= ps[dq.peekLast()]) { dq.pollLast(); } dq.offerLast(j); Time Complexity: O(n) Space Complexity: O(n) A tough problem that builds strong intuition for prefix sums + deque optimization. 55/75 🚀 #Day55 #DSA #PrefixSum #Deque #Java #Algorithms #LeetCode

Yesterday's matrix problem was solved using traversal. Today's matrix problem was solved using Binary Search. Same topic. Different thinking. 🚀 Day 95/365 — DSA Challenge Solved: Search a 2D Matrix Key observation: The matrix is not just row-wise sorted. The first element of each row is greater than the last element of previous row. This means the matrix behaves like a sorted 1D array. So we can apply Binary Search. We convert index → row, col: row = mid / cols col = mid % cols And perform normal binary search. ⏱ Time: O(log(m * n)) 📦 Space: O(1) Day 95/365 complete. 💻 270 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #BinarySearch #Matrix #LearningInPublic