What is the time complexity of Maximum Good Subarray Sum?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Maximum Good Subarray Sum?

This problem uses Array, Hash Table, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Maximum Good Subarray Sum?

Insight 1: Using a prefix sum to calculate subarray sums efficiently can significantly reduce the time complexity. Insight 2: Employing a hash map (or dictionary) to store and quickly retrieve previously encountered prefix sums allows for an O(1) lookup time when checking for potential 'good' subarrays.

Which companies ask LeetCode 3026. Maximum Good Subarray Sum in interviews?

This problem is frequently asked at Atlassian, Groww, Zepto.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Maximum Good Subarray Sum - LeetCode 3026 Solution

Maximum Good Subarray Sum - Complete Solution Guide

Maximum Good Subarray Sum is LeetCode problem 3026, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an array nums of length n and a positive integer k . A subarray of nums is called good if the absolute difference between its first and last element is exactly k , in other words, the subarray nums[i..j] is good if |nums[i] - nums[j]| == k . Return the maximum sum of a good subarray of nums . If there are no good subarrays , return 0 . Example 1: Input: nums = [1,2,3,4,5,6], k = 1 Output: 11 Explanation: The absolute difference between the first and last element must be 1 for a goo

Detailed Explanation

The problem asks us to find the maximum sum of a 'good' subarray within a given array `nums`. A subarray is considered 'good' if the absolute difference between its first and last elements is exactly equal to a given integer `k`. The goal is to iterate through all possible subarrays, check if they are 'good', calculate their sum, and return the maximum sum among all 'good' subarrays. If no such subarray exists, the function should return 0.

Solution Approach

The solution uses a prefix sum approach along with a hash map to efficiently find 'good' subarrays. It calculates the prefix sum as it iterates through the array. For each number, it checks if there's a previous number (using the hash map) such that their absolute difference is equal to `k`. If such a number exists, the sum of the corresponding subarray is calculated using the prefix sums and compared to the current maximum sum. The hash map stores each number encountered along with its minimum prefix sum so far. This way, when a good subarray is detected, the difference in prefix sums is maximized, leading to a potentially greater subarray sum.

Step-by-Step Algorithm

Step 1: Initialize `max_s` (maximum sum) to negative infinity and `found` (boolean to indicate if a good subarray was found) to `false`.
Step 2: Initialize `prefix_sum` to 0 and `min_prefix_map` (hash map) to store each number's minimum prefix sum.
Step 3: Iterate through the `nums` array.
Step 4: For each `num` in `nums`, calculate `target1 = num - k` and `target2 = num + k`.
Step 5: Check if `target1` exists in `min_prefix_map`. If it does, calculate the current subarray sum as `prefix_sum + num - min_prefix_map[target1]`. Update `max_s` with the maximum of `max_s` and the `current_sum`. Set `found` to `true`.
Step 6: Repeat Step 5 for `target2`.
Step 7: If `num` is not in `min_prefix_map` or if the current `prefix_sum` is less than the existing value in `min_prefix_map[num]`, update `min_prefix_map[num]` with the current `prefix_sum`. This ensures that we always store the minimum prefix sum for each number.
Step 8: Update `prefix_sum` by adding `num` to it.
Step 9: After iterating through all numbers, return `max_s` if `found` is true, otherwise return 0.

Key Insights

Insight 1: Using a prefix sum to calculate subarray sums efficiently can significantly reduce the time complexity.
Insight 2: Employing a hash map (or dictionary) to store and quickly retrieve previously encountered prefix sums allows for an O(1) lookup time when checking for potential 'good' subarrays.
Insight 3: Keeping track of the minimum prefix sum for each number encountered helps to maximize the overall sum when a 'good' subarray is found. This addresses the possibility of negative numbers within the subarrays.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Prefix Sum.

Companies

Asked at: Atlassian, Groww, Zepto.

Maximum Good Subarray Sum | LeetCode 3026

Medium

Array Hash Table Prefix Sum

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long max_s = Long.MIN_VALUE;
        boolean found = false;
        
        long prefix_sum = 0;
        Map<Integer, Long> min_prefix_map = new HashMap<>();
        
        for (int num : nums) {
            int target1 = num - k;
            if (min_prefix_map.containsKey(target1)) {
                long current_sum = prefix_sum + num - min_prefix_map.get(target1);
                max_s = Math.max(max_s, current_sum);
                found = true;
            }
            
            int target2 = num + k;
            if (min_prefix_map.containsKey(target2)) {
                long current_sum = prefix_sum + num - min_prefix_map.get(target2);
                max_s = Math.max(max_s, current_sum);
                found = true;
            }
            
            if (!min_prefix_map.containsKey(num) || prefix_sum < min_prefix_map.get(num)) {
                min_prefix_map.put(num, prefix_sum);
            }
            
            prefix_sum += num;
            
        }
        
        return found ? max_s : 0;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3026: Maximum Good Subarray Sum - Detailed explanation and solution approaches.

Topics

Array Hash Table Prefix Sum

Companies

AtlassianGrowwZepto

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:3026

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize `max_s` (maximum sum) to negative infinity and `found` (boolean to indicate if a good subarray was found) to `false`.
2
Step 2: Initialize `prefix_sum` to 0 and `min_prefix_map` (hash map) to store each number's minimum prefix sum.
3
Step 3: Iterate through the `nums` array.
4
Step 4: For each `num` in `nums`, calculate `target1 = num - k` and `target2 = num + k`.
5
Step 5: Check if `target1` exists in `min_prefix_map`. If it does, calculate the current subarray sum as `prefix_sum + num - min_prefix_map[target1]`. Update `max_s` with the maximum of `max_s` and the `current_sum`. Set `found` to `true`.
6
Step 6: Repeat Step 5 for `target2`.
7
Step 7: If `num` is not in `min_prefix_map` or if the current `prefix_sum` is less than the existing value in `min_prefix_map[num]`, update `min_prefix_map[num]` with the current `prefix_sum`. This ensures that we always store the minimum prefix sum for each number.
8
Step 8: Update `prefix_sum` by adding `num` to it.
9
Step 9: After iterating through all numbers, return `max_s` if `found` is true, otherwise return 0.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm iterates through the input array `nums` only once, resulting in a linear time complexity. The hash map stores prefix sums associated with each unique number in `nums`. In the worst-case scenario where all numbers are distinct, the hash map will store `n` key-value pairs, leading to a linear space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays, check if they are 'good', and calculate their sum. Keep track of the maximum sum found so far.

Time: O(n^2), where n is the length of the `nums` array.Space: O(1).

Trade-offs: The brute-force approach is much simpler to implement but has a quadratic time complexity, making it unsuitable for larger input arrays. Use this if n is very small.

✨

Key Insights

1Insight 1: Using a prefix sum to calculate subarray sums efficiently can significantly reduce the time complexity.
2Insight 2: Employing a hash map (or dictionary) to store and quickly retrieve previously encountered prefix sums allows for an O(1) lookup time when checking for potential 'good' subarrays.
3Insight 3: Keeping track of the minimum prefix sum for each number encountered helps to maximize the overall sum when a 'good' subarray is found. This addresses the possibility of negative numbers within the subarrays.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: No 'good' subarray exists. The solution correctly returns 0 in this case because the `found` variable remains false, and the conditional statement at the end handles this scenario.
Edge case 2: All numbers are negative. The algorithm correctly calculates and returns the maximum (least negative) sum of a 'good' subarray when all numbers are negative. The initialization of `max_s` to negative infinity ensures that negative sums are properly compared.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering negative numbers in the subarray. The algorithm needs to correctly handle negative numbers to find the maximum sum of a 'good' subarray, hence the use of storing *minimum* prefix sums.

✗Common mistake 2: Incorrectly calculating the subarray sum using prefix sums. Ensuring that the correct difference of prefix sums is taken, especially when dealing with starting and ending indices of the good subarray, is crucial.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Financial data analysis: Identifying periods where the difference between the initial and final stock price equals a specific target value `k` and maximizing profit during that period.

🏦Real-world scenario 2: Signal processing: Detecting patterns in signals where the difference between the start and end points of a signal segment matches a given threshold, maximizing the signal strength within that segment.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Maximum Good Subarray Sum"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?