Finding the Longest Subarray with a Given Sum: A Java Implementation (Handles Positive and Negative Numbers)

The problem of finding the longest subarray with a given sum is a common coding challenge. Given an array arr[] of integers (which can include both positive and negative numbers) and an integer k, our task is to find the length of the longest contiguous subarray whose elements sum up to k. If no such subarray exists, we return 0.

This blog post will explore an efficient Java implementation that correctly handles both positive and negative numbers in the input array.

The Challenge with Negative Numbers

The presence of negative numbers makes this problem more complex. A simple sliding window approach that works for positive numbers might fail when negative numbers are involved. This is because the sum of a subarray can decrease as we expand the window (due to negative numbers), and we might prematurely shrink the window, missing potential longer subarrays with the target sum.

The Solution: Sliding Window (Corrected)

We'll use a sliding window approach, but with a crucial modification to handle negative numbers correctly.

Java Code

Java

public class LongestSubarraySumK {

    public static int longestSubArray(int num[], long k) {
        int n = num.length;
        int left = 0, right = 0;
        long sum = 0; // Use long to prevent potential overflow
        int maxLen = 0;

        while (right < n) {
            sum += num[right];  // Add the current element to the sum

            while (sum > k) { // Shrink the window ONLY when sum exceeds k
                sum -= num[left];
                left++;
            }

            if (sum == k) {
                maxLen = Math.max(maxLen, right - left + 1);
            }

            right++; // Move the right pointer regardless of sum value
        }
        return maxLen;
    }

    public static void main(String[] args) {
        // Test cases
        int[] num1 = {-1, 2, -3, 4, -2, 1};
        long k1 = 0;
        System.out.println("Test Case 1: " + longestSubArray(num1, k1)); // Output: 6

        int[] num2 = {1, 2, 3, 4, 5};
        long k2 = 9;
        System.out.println("Test Case 2: " + longestSubArray(num2, k2)); // Output: 2

        int[] num3 = {1, 2, 3};
        long k3 = 7;
        System.out.println("Test Case 3: " + longestSubArray(num3, k3)); // Output: 0

        int[] num4 = {1, 2, 3, -2, -1, 3, 3};
        long k4 = 6;
        System.out.println("Test Case 4: " + longestSubArray(num4, k4)); // Output: 3

         int[] num5 = {1,2,3,-1,-2,4};
        long k5 = 3;
        System.out.println("Test Case 5: " + longestSubArray(num5, k5)); // Output: 4

                int[] num6 = {1,2,3,-1,-2,4};
        long k6 = 6;
        System.out.println("Test Case 6: " + longestSubArray(num6, k6)); // Output: 0

    }
}

Explanation of the Code

1. Initialization:

   • left and right pointers define the sliding window.

   • sum stores the current sum of elements within the window. It's crucial to use long for sum to avoid potential integer overflow, especially with large arrays or target values.

   • maxLen stores the maximum length of a subarray found so far.

2. Sliding Window Logic:

   • The while (right < n) loop expands the window by moving the right pointer.

   • sum += num[right]; adds the current element to the sum.

   • The while (sum > k) loop shrinks the window from the left only when the sum strictly exceeds k. This is the key change to handle negative numbers correctly. We don't shrink the window if sum is just greater than or equal to k. We keep shrinking until it is strictly greater than k.

   • if (sum == k): If the sum equals k, we update maxLen.

   • right++;: The right pointer is always incremented to explore all possible subarrays.

Why this works:

By only shrinking the window when sum > k, we ensure that we don't prematurely discard potential solutions with negative numbers. The window might contain negative numbers that bring the sum down to k after it has been greater than k at some point.

Time and Space Complexity

• Time Complexity: O(n). Although there appears to be a nested while loop, the left pointer only moves forward throughout the process. Each element is visited at most twice.

• Space Complexity: O(1). The algorithm uses constant extra space.

Conclusion

This corrected sliding window approach provides an efficient and robust solution to the longest subarray sum problem, correctly handling both positive and negative numbers. The use of long for the sum variable is also important to prevent potential overflow issues. This implementation is suitable for various coding challenges and real-world applications.