Sum of All Odd Length Subarrays - Practice Coding Problems

Sum of All Odd Length Subarrays - Problem

Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

For example, if arr = [1,4,2,5,3], the odd-length subarrays are:

Length 1: [1], [4], [2], [5], [3]
Length 3: [1,4,2], [4,2,5], [2,5,3]
Length 5: [1,4,2,5,3]

We need to sum all elements in all these subarrays.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,4,2,5,3]

› Output: 58

💡 Note: Odd-length subarrays: [1]=1, [4]=4, [2]=2, [5]=5, [3]=3, [1,4,2]=7, [4,2,5]=11, [2,5,3]=10, [1,4,2,5,3]=15. Sum = 1+4+2+5+3+7+11+10+15 = 58

Example 2 — Smaller Array

$ Input: arr = [1,2]

› Output: 3

💡 Note: Only odd-length subarrays are [1] and [2]. Sum = 1 + 2 = 3

Example 3 — Single Element

$ Input: arr = [10]

› Output: 10

💡 Note: Only one subarray [10] with odd length 1. Sum = 10

Constraints

1 ≤ arr.length ≤ 100
1 ≤ arr[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with positive integers

Find Odd Subarrays

Identify all subarrays with odd lengths (1, 3, 5, ...)

Sum All Elements

Add up all elements from all odd-length subarrays

Key Takeaway

🎯 Key Insight: Each element contributes to multiple odd-length subarrays - count mathematically instead of generating all subarrays

Asked in

A Amazon 25 G Google 18 🍎 Apple 12

The key insight is that instead of generating all odd-length subarrays, we can mathematically calculate how many times each element appears in odd-length subarrays. The optimal approach uses combinatorics to determine each element's contribution in O(1) time. Best approach: Mathematical Formula with Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n²)	O(n)	Use prefix sums to calculate subarray sums in O(1) time
Mathematical Formula	O(n)	O(1)	Calculate how many times each element appears in odd subarrays using combinatorics
Brute Force - Generate All Odd Subarrays	O(n³)	O(1)	Generate every possible odd-length subarray and sum all elements

Prefix Sum Optimization — Algorithm Steps

Build prefix sum array where prefix[i] = sum of elements 0 to i-1
For each starting position, try all odd lengths
Use prefix sums to calculate subarray sum in O(1): prefix[end+1] - prefix[start]

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Array

prefix[i] = sum of elements 0 to i-1

Calculate Range Sum

sum[i..j] = prefix[j+1] - prefix[i]

Apply to All Odd Subarrays

Use formula for each odd-length subarray

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int n) {
    // Build prefix sum array
    int* prefix = (int*)calloc(n + 1, sizeof(int));
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    int totalSum = 0;
    
    // Try all starting positions
    for (int i = 0; i < n; i++) {
        // Try all odd lengths starting from position i
        for (int length = 1; length <= n - i; length += 2) {
            // Calculate subarray sum using prefix sums in O(1)
            int subarraySum = prefix[i + length] - prefix[i];
            totalSum += subarraySum;
        }
    }
    
    free(prefix);
    return totalSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int arr[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            arr[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops for start position and length, but subarray sum calculation is O(1) with prefix sums

⚠ Quadratic Growth

Space Complexity

O(n)

Extra prefix sum array of size n+1 to store cumulative sums

⚡ Linearithmic Space

98.4K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler