Subarray with Zero Sum 🎯

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we're diving deep into one of the most intriguing problems called the "Subarray with Zero Sum". 💡

Understanding the Problem

The problem statement is simple: Given an array, find a continuous subarray with zero sum.

Let's break it down:

Array: A list of numbers, where each number is an element.
Continuous subarray: A subset of elements where no elements from outside the subset are included.
Zero Sum: The sum of all elements in the subarray equals zero.

Why is this Problem Important?

Subarray with Zero Sum is a classic problem that tests your understanding of arrays and algorithms. It's a great starting point for learning various algorithmic concepts like prefix sum and sliding window techniques. These skills are essential for many real-world applications, including data analysis, machine learning, and competitive programming.

Solving the Problem: Step-by-Step 📝

Step 1: Prefix Sum

To solve the problem, we'll first create a prefix sum of the given array. The prefix sum array stores the sum of elements from the beginning of the array up to the current index.

Here's an example:

python

def prefix_sum(arr):
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]
    return prefix_sum

Step 2: Finding the Subarray

Now that we have the prefix sum, we can find a subarray with zero sum by looking for a pair of indices (i and j) such that the sum of prefix_sum[j] - prefix_sum[i] equals zero.

python

def subarray_with_zero_sum(arr):
    prefix_sum = prefix_sum(arr)
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if prefix_sum[j] - prefix_sum[i] == 0:
                return "Subarray from index {} to {} has zero sum".format(i, j)
    return "No subarray with zero sum found"

Putting it all Together 💡

Let's see the entire solution:

python

def prefix_sum(arr):
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]
    return prefix_sum

def subarray_with_zero_sum(arr):
    prefix_sum = prefix_sum(arr)
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if prefix_sum[j] - prefix_sum[i] == 0:
                return "Subarray from index {} to {} has zero sum".format(i, j)
    return "No subarray with zero sum found"

arr = [15, -2, 2, -8, 1, 7, 10, -2, 3, 10]
print(subarray_with_zero_sum(arr))

In this example, the subarray from index 1 to 4 (-2, 2, -8, 1) has a zero sum.

Quiz Time 🎯

Happy coding! 🎉 Let's continue learning and exploring the exciting world of Data Structures and Algorithms together! 💡💡💡