Kadane Algorithm with One Deletion for Maximum Subarray Sum

🚀 Day 80 — Kadane’s Algorithm (Maximum Subarray) Continuing the Kadane pattern — today I implemented the classic Maximum Subarray Sum problem. This is where the “ending at index i” logic truly shines. 📌 Problem Solved: LeetCode 53 – Maximum Subarray 🧠 Kadane’s in Action: java int max = nums[0], gmax = nums[0]; for (int i = 1; i < nums.length; i++) { max = Math.max(nums[i], max + nums[i]); gmax = Math.max(gmax, max); } return gmax; Step‑by‑step logic: max = best sum of subarray ending at current index. At each i, we choose: extend previous subarray (max + nums[i]) or start fresh (nums[i]). gmax tracks the global maximum across all endings. Why this works even with negatives: Because we always have the option to discard the past and start fresh, Kadane’s never gets stuck with a losing streak. 💡 Takeaway: Three lines of code, but behind them lies a powerful pattern. Understanding the why (the decision at each index) makes it easy to adapt to variations like minimum subarray or maximum product. No guilt about past breaks — just building pattern recognition one day at a time. #DSA #KadaneAlgorithm #MaximumSubarray #LeetCode53 #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

✳️Day 35 of #100DaysOfCode✳️ 📌 Cracking the "Redundant Connection" Problem with DSU! 🛠️ My Approach: The DSU Strategy The Disjoint Set Union (or Union-Find) algorithm is perfect here because it allows us to track connected components efficiently as we iterate through the edges. ✨The Steps in my Code: 1️⃣Initialization: Created a parent array where every node is initially its own parent (representing n independent sets). 2️⃣Iterative Union: For every edge (u, v) in the input: Find the root (representative) of u. Find the root (representative) of v. Cycle Detection: * If find(u) == find(v), it means u and v are already part of the same connected component. Adding this edge would create a cycle. 🚩 Since the problem asks for the last edge that causes the cycle, I return this edge immediately. 3️⃣Union: If they are in different sets, I perform a union by setting the parent of one root to the other. 4️⃣Optimization: I used Path Compression in the find function to keep the tree flat, ensuring almost constant time complexity. 💡 When should you use DSU? 🔅DSU is a powerhouse for specific graph scenarios. Reach for it when: Cycle Detection: You need to check if adding an edge creates a cycle in an undirected graph. 🔅Connected Components: You need to count or manage groups of connected nodes dynamically. 🔅Minimum Spanning Trees: It’s the backbone of Kruskal’s Algorithm. Grid Problems: Identifying "islands" or connected regions in a 2D matrix. #DataStructures #Algorithms #LeetCode #Java #GraphTheory #CodingLife #SoftwareEngineering

Day 79/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Flatten Binary Tree to Linked List A powerful tree transformation problem using pointer manipulation. Problem idea: Convert a binary tree into a linked list in-place following preorder traversal. Key idea: Iterative traversal + rewiring (similar to Morris traversal idea). Why? • We need preorder sequence (Root → Left → Right) • Instead of extra space, we modify pointers in-place • Efficient and avoids recursion stack How it works: • Traverse using a pointer curr • If left child exists: → Find rightmost node of left subtree → Connect it to current’s right subtree → Move left subtree to right → Set left = null • Move to next node (curr.right) Time Complexity: O(n) Space Complexity: O(1) Big takeaway: Tree problems can often be optimized using in-place pointer rewiring, avoiding extra space. 🔥 This pattern is very useful for tree flattening and traversal optimizations. Day 79 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #BinaryTree #MorrisTraversal #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

🚀 LeetCode Challenge 28/50 💡 Approach: Bidirectional HashMap + HashSet This is the word-level version of Isomorphic Strings! We need a true bijection — each pattern letter maps to exactly one word AND each word maps to exactly one letter. One map alone isn't enough! 🔍 Key Insight: → Split string s into words array → If lengths differ → instantly return false → Map char → word using HashMap → Track already-used words with a HashSet → If a new char tries to claim an already-used word → false! 📈 Complexity: ✅ Time: O(n) — single pass through pattern ✅ Space: O(n) — map + set storing at most n entries Pattern recognition in problem solving is just like pattern recognition in code — once you see the structure, the solution follows naturally! 🔍 #LeetCode #DSA #HashMap #Java #ADA #PBL2 #LeetCodeChallenge #Day28of50 #CodingJourney #ComputerEngineering #AlgorithmDesign #WordPattern

🚀 Day 83 — Kadane’s Algorithm (Maximum Absolute Subarray Sum) Taking Kadane’s pattern one step further — today I solved a problem that asks for the maximum absolute sum of any subarray. The absolute value adds a twist: the largest magnitude could come from a very positive sum or a very negative sum. 📌 Problem Solved: LeetCode 1749 – Maximum Absolute Sum of Any Subarray 🧠 The Approach – Track Both Extremes: java int max = nums[0], min = nums[0], ans = nums[0]; for (int i = 1; i < nums.length; i++) { max = Math.max(nums[i], max + nums[i]); min = Math.min(nums[i], min + nums[i]); ans = Math.max(ans, Math.max(Math.abs(max), Math.abs(min))); } return Math.abs(ans); Why this works: max tracks the maximum subarray sum ending at i (standard Kadane). min tracks the minimum subarray sum ending at i (Kadane for minimum). The absolute sum could be either |max| or |min| (since a large negative sum has a large absolute value). ans keeps the largest of these absolute values across all endings. 💡 Key Insight: When the problem asks for “maximum absolute” or “closest to zero” etc., often you need to track both the maximum and minimum subarray sums simultaneously. Kadane’s pattern is flexible enough to handle this with just two variables. No guilt about past breaks — just adding another tool to the Kadane toolbox. #DSA #KadaneAlgorithm #MaximumAbsoluteSum #LeetCode1749 #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

🚀 Day 81 — Kadane’s Algorithm (Minimum Subarray Sum) Extending the Kadane pattern — today I solved the minimum sum version of the contiguous subarray problem. The logic is identical to maximum subarray, just flipping max to min. 📌 Problem Solved: GeeksforGeeks – Smallest Sum Contiguous Subarray 🧠 Kadane’s for Minimum Sum: java int min = a[0], ans = a[0]; for (int i = 1; i < a.length; i++) { min = Math.min(a[i], a[i] + min); ans = Math.min(ans, min); } return ans; Step‑by‑step logic: min = best sum of subarray ending at current index (minimum possible). At each i, choose: extend previous subarray (min + a[i]) or start fresh (a[i]). ans tracks the global minimum across all endings. Why this works: Same as maximum subarray, but we always pick the smaller option. Negatives become desirable here, and positives may cause us to start fresh. 💡 Takeaway: Kadane’s is a template — Math.max for maximum sum, Math.min for minimum sum. Understand the decision at each index, and you can solve both variations effortlessly. No guilt about past breaks — just mastering patterns one variation at a time. #DSA #KadaneAlgorithm #MinimumSubarray #GeeksforGeeks #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

#70DayStreak 🚀 27/04/26 — Optimized Sliding Window | Longest Substring Without Repeating Characters (LeetCode 3) Today I revisited a classic problem — Longest Substring Without Repeating Characters — and implemented a more optimized Sliding Window using HashMap. Previously, I used a HashSet approach where the window shrinks step-by-step. This time, I upgraded it with a "jumping window" technique, allowing direct pointer movement. 🔑 Key Optimization Insight Instead of removing characters one by one: • Store last seen index of each character • When duplicate appears → jump left pointer instantly • Avoid unnecessary iterations 👉 This reduces redundant work and improves efficiency significantly. ⚙️ Algorithm Highlights • Left pointer jumps using stored indices • Right pointer scans once • Continuous max window calculation 📊 Complexity • Time: O(n) • Space: O(min(m, n)) 📈 Performance • Runtime: 5ms (Beats 87.15%) • Memory: 45.67 MB (Beats 69.72%) 🔥 Consistency Metrics • 84 Active Days • 70-Day Streak 💡 Key Learning Switching from HashSet → HashMap transforms the approach from iterative shrinking to direct optimization. This is a small shift in thinking, but a big upgrade in performance. 📌 Even after 100+ problems, refinement and optimization still matter. #DSA #Java #LeetCode #SlidingWindow #HashMap #Algorithms #CodingJourney #ProblemSolving #Optimization #100DaysOfCode

💡 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 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

Day 102 of 365 Days of code I'm falling in love with graphs 🕷️ Ever wondered how multi source bfs works "_". i thought we must be using some kind of concurrency or threading concepts to do perform bfs parallely at the same time. Then i saw some discussion from CF, and a guy said consider bfs search has multiple sources, each starting from a part of graph. A simple solution is to think about an imaginary node connecting all these multiple sources, and push the imaginary node into queue. Thereby you will be able simultaneously traverse the graph, where it looks like each of the node will be performed a bfs search, simultaneously. Instead of using an imaginary node, just push all the source nodes into the queue. and start performing bfs. both of the approaches are the same, we reach the second state after performing the first one, so instead of wasting time on constructing an imaginary node we directly enqueue the source nodes into the queue. SOrry for the bad english, i'm feeling sleepy :( Qn 1) Rotten oranges Approach: Multi Source Bfs Explanation: i wanna sleep bruv #365daysOfCode #NeetCode  #leetcode  #DSA  #python #LeetCode #ProblemSolving  #Algorithms #365dayschallenge