Kadane's Algorithm for Maximum Subarray

🚀 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

🚀 Day 84 — Kadane’s Algorithm (Maximum Circular Subarray Sum) Leveling up Kadane’s pattern — today I solved the circular version of the maximum subarray problem. The twist: subarrays can wrap around the end to the beginning. 📌 Problem Solved: LeetCode 918 – Maximum Sum Circular Subarray 🧠 Key Insight – Two Cases: Case 1: The maximum subarray is non-circular (lies within the array). → Solved by standard Kadane (gmax). Case 2: The maximum subarray wraps around (takes a prefix + suffix). → Equivalent to: total sum - minimum subarray sum. Because removing the minimum contiguous segment from the middle leaves the circular max. Final answer: If all numbers are negative → gmax (since sum - gmin would be 0 or less). Else max(gmax, sum - gmin). java int min = nums[0], max = nums[0], sum = nums[0]; int gmin = nums[0], gmax = nums[0]; for (int i = 1; i < nums.length; i++) { sum += nums[i]; min = Math.min(nums[i], min + nums[i]); gmin = Math.min(gmin, min); max = Math.max(nums[i], max + nums[i]); gmax = Math.max(gmax, max); } if (gmax < 0) return gmax; return Math.max(gmax, sum - gmin); 💡 Takeaway: Kadane’s pattern is not just linear — it adapts to circular arrays by combining max subarray and min subarray with total sum. Track both extremes, and the circular case becomes elegant. No guilt about past breaks — just mastering variations, one problem at a time. #DSA #KadaneAlgorithm #CircularSubarray #LeetCode918 #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

🚀 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 82 — Kadane’s Algorithm (Maximum Subarray Sum with One Deletion) Pushing forward with a more advanced Kadane variation — today I solved a problem where you’re allowed to delete at most one element from the subarray to maximize the sum. 📌 Problem Solved: LeetCode 1186 – Maximum Subarray Sum with One Deletion 🧠 The Twist on Standard Kadane: We now need to track two states at each index: nd = maximum subarray sum ending at i with no deletion used so far. od = maximum subarray sum ending at i with exactly one deletion used so far. Transition logic: nd = Math.max(arr[i], nd + arr[i]) → classic Kadane (no deletion). od = Math.max(nd_prev, od_prev + arr[i]) → either skip deleting this element (so use previous no‑deletion state) or extend a previously deleted subarray. Why track both? Because at any point, the best subarray ending here may have never deleted, or may have deleted a previous element. The answer is the max of all nd and od across the array. 💡 Key Insight: Kadane’s pattern isn’t just one variable — it scales to multiple states. This “state‑based DP” approach is the bridge between Kadane and more complex subarray problems. No guilt about past breaks — just leveling up one variation at a time. #DSA #KadaneAlgorithm #MaximumSubarrayWithDeletion #LeetCode1186 #CodingJourney #Revision #Java #ProblemSolving #Consistency #GrowthMindset #TechCommunity #LearningInPublic

🚀 Solved: Maximum Subarray Problem (Kadane’s Algorithm) Today, I solved the classic Maximum Subarray problem from LeetCode using an efficient approach. 🔍 Problem Statement Given an integer array, find the contiguous subarray with the largest sum and return that sum. 💡 Approach Used: Kadane’s Algorithm Instead of checking all possible subarrays (which would take O(N²)), I used an optimized linear approach: -> Keep a running sum of elements -> If the sum becomes negative, reset it to 0 -> Track the maximum sum encountered so far ⚡ Time Complexity: O(N) 📦 Space Complexity: O(1) 💻 Java Implementation: class Solution { public int maxSubArray(int[] nums) { int sum = 0; int max = nums[0]; for (int i = 0; i < nums.length; i++) { sum = sum + nums[i]; if (sum > max) { max = sum; } if (sum < 0) { sum = 0; } } return max; } } 🎯 Key Insight: Even if a running sum becomes negative, continuing it will only decrease future subarray sums—so it's better to restart. This problem is a great example of how understanding patterns can reduce complexity from brute force to optimal. #Java #DataStructures #Algorithms #LeetCode #CodingInterview #SoftwareEngineering #ProblemSolving

✳️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

Ever tried to run a standard Gaussian blur and watched your processing time quadratically explode? 🐢📉 I just published a new tutorial on Baeldung detailing how to implement a highly optimized, Fast Gaussian Blur in Java. The traditional 2D convolution matrix gives us a time complexity of O(n * r²), which quickly becomes a bottleneck for high-res images or large blur radii. In this article, I break down how to drop that complexity down to a flat O(n) by leveraging two mathematical properties: 1️⃣ Separable Filters: Breaking a 2D matrix down into sequential horizontal and vertical 1D passes. 2️⃣ The Central Limit Theorem: Approximating a true Gaussian bell curve by applying a lightning-fast sliding-window Box Blur three times. The result? A blur effect where the processing time is completely independent of the blur radius. 🚀 You can read the full breakdown, analyze the math, and grab the JUnit 5 tested code here: [https://lnkd.in/d6NMwVjw] How do you usually handle expensive image processing tasks in your Java pipelines? Let me know below! 👇 #Java #Algorithms #SoftwareEngineering #ImageProcessing #Baeldung #PerformanceOptimization

𝗗𝗮𝘆 𝟲𝟴/𝟳𝟱 | 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 𝟳𝟱 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: 136. Single Number 𝗗𝗶𝗳𝗳𝗶𝗰𝘂𝗹𝘁𝘆: Easy 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗦𝘂𝗺𝗺𝗮𝗿𝘆: Given a non-empty array where every element appears twice except for one, find the element that appears only once. Constraints: • Linear time complexity required • Constant extra space 𝗠𝘆 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵: This problem is efficiently solved using Bit Manipulation (XOR operation). • Key Properties of XOR: – a ^ a = 0 – a ^ 0 = a – XOR is commutative and associative • Logic: – XOR all elements in the array – Duplicate numbers cancel each other out – The remaining value is the unique element • Implementation: – Initialize a variable (e.g., result = 0) – Traverse the array and XOR each element with result – Final result holds the single number This works because pairs eliminate themselves, leaving only the non-repeating number. 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 𝗔𝗻𝗮𝗹𝘆𝘀𝗶𝘀: • Time Complexity: O(n) • Space Complexity: O(1) 𝗞𝗲𝘆 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆: Bit manipulation can simplify problems that seem to require extra space. XOR is especially powerful when dealing with pairs or duplicates. 𝗤𝘂𝗲𝘀𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: https://lnkd.in/guP-fJnC #Day68of75 #LeetCode75 #DSA #Java #Python #BitManipulation #Algorithms #MachineLearning #DataScience #ML #DataAnalyst #LearningInPublic #TechJourney #LeetCode

**Day 106 of #365DaysOfLeetCode Challenge** Today’s problem: **Number of Boomerangs (LeetCode 447)** A very interesting problem that combines **geometry + hashing**. 💡 **Core Idea:** A boomerang is defined as: 👉 `(i, j, k)` such that distance(i, j) == distance(i, k) ⚠️ Order matters → (i, j, k) ≠ (i, k, j) 📌 **Approach:** * Fix one point `i` as the center * Compute distance from `i` to every other point * Store frequencies of distances in a HashMap 👉 If `count` points have the same distance from `i`, then number of boomerangs = `count * (count - 1)` Why? Because order matters → permutations! ⚡ **Time Complexity:** O(n²) ⚡ **Space Complexity:** O(n) **What I learned today:** When order matters in combinations → think **permutations (n × (n-1))** 💭 **Key Takeaway:** * Fix one point → reduce problem complexity * Use hashing to group equal distances * Apply math on frequencies This is a great example of: 👉 Turning a geometric problem into a hashmap problem #LeetCode #DSA #HashMap #Geometry #CodingChallenge #ProblemSolving #Java #TechJourney #Consistency

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