Day 3 of 60 Days of DSA: Prefix odd and even sum algorithms

Learn how prefix sums make “tricky-looking” problems easy to crack in O(N).

Problem Description — 1

You are given an integer array A of size N.

You have to perform B operations. In one operation, you can remove either the leftmost or the rightmost element of the array A.

Find and return the maximum possible sum of the B elements that were removed after the B operations.

NOTE: Suppose B = 3, and array A contains 10 elements, then you can:

Remove 3 elements from front and 0 elements from the back, OR

Remove 2 elements from front and 1 element from the back, OR

Remove 1 element from front and 2 elements from the back, OR

Remove 0 elements from front and 3 elements from the back.

Problem Constraints

1 <= N <= 105

1 <= B <= N

-103 <= A[i] <= 103

Input Format

First argument is an integer array A.

Second argument is an integer B.

Output Format

Return an integer denoting the maximum possible sum of elements you removed.

Example Input

Input 1:

A = [5, -2, 3 , 1, 2]
B = 3

Input 2:

A = [ 2, 3, -1, 4, 2, 1 ]
B = 4

Example Output

Output 1: 8

Output 2: 9

Example Explanation

Explanation 1:

Remove element 5 from front and element (1, 2) from back so we get 5 + 1 + 2 = 8

Explanation 2:

Remove the first element and the last 3 elements. So we get 2 + 4 + 2 + 1 = 9

Solution Approach

Intuition

If we try all possible combinations of taking B elements from front and back, it’ll take O(B²) time — too slow for large B.

Instead, we can precompute prefix sums and efficiently find any combination’s total using those

Optimal Approach — Using Prefix Sum

Idea:
Let’s calculate prefix sums once. Then, for each split of front and back picks, compute the total in O(1).

Example:
If B = 3 → combinations:

Code Implementation

function pickFromBothSides(A, B){
 let n = A.length;
 let ps = [];
 // calculate prefix sum
 for(let i=0; i <A.length; i++){
 if(i ==0 ) ps[i] = A[i];
 else ps[i] = ps[i-1] + A[i];
 }
 // now find the combinations for ex - if B=2
 /*
 Front Back
 2 0
 1 1
 0 2
 */
 let front = B;
 let maxSum = Number.MIN_SAFE_INTEGER;
 while(front >= 0){
 let back = B-front;
 let sum = (front == 0 ? 0 : ps[front-1]) + (back == n ? ps[n-1]: ps[n-1]- ps[n-1-back]);
 maxSum = Math.max(sum, maxSum)
 front--;
 }
 return maxSum;
}

Time and Space Complexity

Time: O(N) — one pass for prefix sum + one loop for B splits.
Space: O(N) — for prefix sum array (can be optimized to O(1)).

Problem Description — 2

Given an array, arr[] of size N, the task is to find the count of array indices such that removing an element from these indices makes the sum of even-indexed and odd-indexed array elements equal.

Problem Constraints

1 <= N <= 105
-105 <= A[i] <= 105
Sum of all elements of A <= 109

Input Format

First argument contains an array A of integers of size N

Output Format

Return the count of array indices such that removing an element from these indices makes the sum of even-indexed and odd-indexed array elements equal.

Example Input

Input 1:

A = [2, 1, 6, 4]

Input 2:

A = [1, 1, 1]

Example Output

Output 1: 1

Output 2: 3

Example Explanation

Explanation 1:

Removing arr[1] from the array modifies arr[] to { 2, 6, 4 } such that, arr[0] + arr[2] = arr[1]. 
Therefore, the required output is 1.

Explanation 2:

Removing arr[0] from the given array modifies arr[] to { 1, 1 } such that arr[0] = arr[1] 
Removing arr[1] from the given array modifies arr[] to { 1, 1 } such that arr[0] = arr[1] 
Removing arr[2] from the given array modifies arr[] to { 1, 1 } such that arr[0] = arr[1] 
Therefore, the required output is 3.

Solution Approach

Intuition

We need to efficiently calculate even and odd sums after removing each element.
If we do this naively, it becomes O(N²) — too slow.

We can use two prefix arrays:

evenPs[i] → sum of even-indexed elements up to i
oddPs[i] → sum of odd-indexed elements up to i

Observation

When we remove an element, all elements after it shift left → even ↔ odd switch.

So for each index i:

evenSum = evenPs[i-1] + (oddPs[n-1] - oddPs[i])
oddSum = oddPs[i-1] + (evenPs[n-1] - evenPs[i])

If evenSum === oddSum → it’s a special index ✅

Code Implementation

function specialIndex(A){
 let oddPs = new Array(A.length).fill(0), evenPs =new Array(A.length).fill(0);
 for(let i =0; i<A.length ; i++){
 if(i==0){
 evenPs[0] = A[0];
 }else{ // even index
 evenPs[i] = i%2==0 ? evenPs[i-1] + A[i]: evenPs[i-1];
 oddPs[i] = i%2!=0 ? oddPs[i-1] + A[i]: oddPs[i-1];
 }
 }
 let count= 0;
 let n= A.length;
 for(let i=0; i<A.length; i++){
 let os = (i!=0 ? oddPs[i-1] : 0)+ evenPs[n-1] - evenPs[i] ;
 let es = (i!=0 ? evenPs[i-1] : 0) + oddPs[n-1] - oddPs[i];
 if(os == es){
 count++;
 }
 }

 return count;
}

Time and Space Complexity

Time: O(N) — single pass to build prefix arrays + one more pass to check each index.
Space: O(N) — for even and odd prefix arrays.

Key Takeaways

✅ Prefix sums turn repeated summations into O(1) lookups.
✅ Sliding window and prefix sum are must-master tools for arrays.
✅ Think in patterns — not just problems.

Day 3 of 60 Days of DSA: Prefix odd and even sum algorithms