Kadane's Algorithm for Minimum 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 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 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

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

🚀 Day 5/100 — #100DaysOfLeetCode Consistency + Concepts = Growth 📈 ✅ Problem Solved: 🔹 LeetCode 53 — Maximum Subarray 💡 Algorithm Used: Kadane’s Algorithm 🧠 What I Learned: Kadane’s Algorithm efficiently finds the maximum subarray sum in O(n) time by following a simple intuition: Keep adding elements to a running sum. If the running sum becomes negative, reset it to 0 because a negative sum can never help future subarrays. Continuously track the maximum sum seen so far. Instead of checking all possible subarrays (which is costly), Kadane’s Algorithm teaches how local decisions lead to a global optimal solution. This problem helped me understand how optimization patterns work in real DSA problems. Day by day, patterns are becoming clearer 🚀 #100DaysOfLeetCode #LeetCode #DSA #KadaneAlgorithm #Java #ProblemSolving #Algorithms #CodingJourney #LearningInPublic

✅ Solved: Anagram Palindrome Another step forward in sharpening problem-solving skills 🚀 🔍 Problem Insight: A string can be rearranged into a palindrome if at most one character has an odd frequency. Simple idea, but powerful when applied efficiently. 💡 Implemented using an optimized approach in Java: - Time Complexity: O(n) - Space Complexity: O(1) 📊 Result: ✔️ Test Cases Passed: 1113 / 1113 ✔️ Accuracy: 100% ✔️ Time Taken: 0.52s Small problem, but a good reminder that the right observation beats brute force every time ⚡ #DataStructures #Algorithms #Java #ProblemSolving #CodingJourney #DSA #TechGrowth

Day 33 #SDE string algorithms and two-pointer techniques. Solved: • Longest Palindromic Substring • Reverse String Key Learning: • “Longest Palindromic Substring” can be solved using the expand around center approach, checking both odd and even length palindromes efficiently. • “Reverse String” reinforces the two-pointer technique, a simple yet powerful pattern for in-place operations. #LeetCode #DSA #Strings #TwoPointers #Algorithms #Java #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

We are excited to share that we've successfully tackled the Anagram Palindrome problem from GeeksforGeeks! This classic string manipulation challenge tests whether any permutation of a given string can form a palindrome—a fundamental concept in algorithm design and competitive programming. Our solution leverages the key insight from combinatorics: a string can be rearranged into a palindrome if and only if at most one character has an odd frequency. We implemented this logic efficiently across multiple languages—Python, Java, and C++—using each language’s idiomatic constructs for optimal performance and readability. In Python, we utilized collections.Counter for concise frequency counting; in Java, we employed HashMap<Character, Integer> with proper null handling; and in C++, we used unordered_map<char, int> for direct hash-based frequency tracking. All implementations run in O(n) time complexity with O(k) space complexity, where k is the number of unique characters, making them highly scalable even for large inputs. This problem beautifully illustrates how mathematical reasoning translates into clean, efficient code—and how different programming paradigms express the same algorithmic truth. Whether you're preparing for technical interviews, sharpening your coding skills, or exploring string algorithms , mastering such foundational patterns is essential. A big thank you to GeeksforGeeks for providing high-quality practice problems that bridge theory and real-world implementation. Keep coding, keep learning! #geekstreak60 #NPCI #Strings #POTD #GFG #Coding #Python #Cpp #Java #Algorithms #DataStructures #Palindrome #Anagram #CompetitiveProgramming #CodeOptimization #SoftwareEngineering #DSA Problem Link : https://lnkd.in/gxTBx6ex Solution Link : https://lnkd.in/gmMViqWv