525.Contiguous Array.

#dsa #programming #cpp #beginners

🧠 Simple Idea:
We want a subarray where number of 0s = number of 1s.

But comparing counts in every subarray is slow, so we trick the problem:

`Treat every 0 as -1

Treat every 1 as +1`
Now:

If we can find any subarray that adds up to 0, it means equal number of 0s and 1s.

💡 Main Trick – Prefix Sum + HashMap
We calculate a running sum (prefix sum) while moving through the array.

We store the first index where each prefix sum occurs.

If the same prefix sum occurs again later, the subarray between those two positions must sum to 0 → equal 0s and 1s.

🔍 Step-by-Step Example
Let's take an example:

nums = [0, 1, 0, 0, 1, 1] 👉 After converting 0s to -1s:

[-1, +1, -1, -1, +1, +1] Now we calculate running sum (prefix sum):

✅ Final Answer: 6
That subarray is from index 0 to 5: [0, 1, 0, 0, 1, 1] → has 3 zeros and 3 ones.

🕒 Time Complexity
O(n) — only one loop

O(n) — extra space for hashmap

- Space complexity:
O(k)

 ` int findMaxLength(vector<int>& nums) {
        int maxi = 0, sum = 0;
        unordered_map<int, int>mpp;
        mpp[0] =-1;
        for(int i=0;i<nums.size();i++){
            sum += ((nums[i] == 0) ? -1 : 1);

            if(mpp.find(sum) != mpp.end()) maxi = max(maxi, i-mpp[sum]);
            else mpp[sum] = i;
        }

        return maxi;
    }

📁 Organized DSA Repository
I've started a DSA-in-C++ GitHub repository where all problems are sorted algorithm-wise into folders like: