2. Sliding Window Vs Prefix Sum

---

The Core Difference

Property	Sliding Window	Prefix Sum
All elements non-negative?	✅ Works	✅ Works
Negative elements?	❌ Breaks	✅ Works
State monotonic when expanding?	✅ Required	Not needed
Space	O(1) to O(n)	O(n)
Time	O(n)	O(n)

The One Rule

Sliding window works when moving the left pointer always makes the window “more valid.” The moment a single element can both increase AND decrease the state — use Prefix Sum.

---

Same Problem — Different Solution

930. Binary Subarrays With Sum

Binary array (only 0s and 1s) → adding element only increases sum → Sliding Window works.

// Sliding Window approach
int atMost(vector<int>& A, int S) {
    if (S < 0) return 0;
    int res = 0, sum = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        sum += A[i];
        while (sum > S) sum -= A[j++];
        res += i - j + 1;
    }
    return res;
}
int numSubarraysWithSum(vector<int>& A, int S) {
    return atMost(A, S) - atMost(A, S - 1);
}

560. Subarray Sum Equals K

Can have negative numbers → Sliding Window breaks → use Prefix Sum.

// Prefix Sum + HashMap approach
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int psum = 0, count = 0;
    for (int i = 0; i < nums.size(); i++) {
        psum += nums[i];
        count += mp[psum - k];
        mp[psum]++;
    }
    return count;
}

---

Decision Flowchart

Subarray problem?
├── Fixed window size k → Fixed Sliding Window
└── Variable window
    ├── All elements positive / binary?
    │   ├── Count subarrays → atMost(K) - atMost(K-1)
    │   ├── Max length → shrink while invalid
    │   └── Min length → shrink while valid
    └── Negative elements possible?
        ├── Count / Length → Prefix Sum + HashMap
        └── Divisibility → Prefix Sum + Remainder map

---

Common Traps

"Looks like sliding window" but isn't

Problem	Why SW fails	Real solution
Subarray Sum = K (with negatives)	Adding element can increase OR decrease sum	Prefix Sum + HashMap
Contiguous Array (equal 0s and 1s)	Replace 0→-1, now has negatives	Prefix Sum + HashMap
Longest Palindromic Substring	No monotonic window property	Expand from center
Longest Continuous Subarray, abs diff ≤ limit	Need both max AND min of window	Monotonic Deque

---