DEV Community

Harry Alto
Harry Alto

Posted on

📘 Subarray Concepts

Notes & Intuition (with Examples)

These notes summarize key concepts from a class on subarrays, including brute-force techniques, prefix sum, and carry-forward approaches.

🧠 What is a Subarray?

A subarray is a contiguous part of an array.

Examples:

Given A = [5, 6, 2, 8]

  • Single-element subarrays: [5], [6], [2], [8]
  • Multi-element subarrays: [5, 6], [6, 2], [2, 8], [5, 6, 2], [6, 2, 8], [5, 6, 2, 8]

✅ The entire array and individual elements are subarrays.

✅ An empty array is also a valid subarray.

🧮 Basic Subarray Metadata

To define a subarray:

  • Start index s
  • End index e

Example:
Given A = [3, 4, 6, 2, 8, 10]

Indexes: [0, 1, 2, 3, 4, 5]

A subarray from index 2 to 4 is: A[2:5] = [6, 2, 8]

🔢 Total Number of Subarrays

For an array of length N = 4:

A = [1, 2, 3, 4]

Subarrays:

  • Starting at index 0: [1], [1,2], [1,2,3], [1,2,3,4]
  • Starting at index 1: [2], [2,3], [2,3,4]
  • Starting at index 2: [3], [3,4]
  • Starting at index 3: [4]

Total = 10 = N * (N + 1) / 2

🚀 Printing All Subarrays 

A = [3, 1, 6]
Enter fullscreen mode Exit fullscreen mode

Print all:

  • [3]
  • [3, 1]
  • [3, 1, 6]
  • [1]
  • [1, 6]
  • [6]

📌 Printing Sum of a Given Subarray [s, e]

Example:

arr = [3, 4, 6, 2, 8]
s, e = 1, 3
# arr[1:4] = [4, 6, 2] → sum = 12
Enter fullscreen mode Exit fullscreen mode

✅ Prefix Sum Technique (for fast sum queries)

Build:

arr = [3, 4, 6, 2, 8]
prefix = [3, 7, 13, 15, 23]
Enter fullscreen mode Exit fullscreen mode

Query:

  • Sum of subarray [1,3]: prefix[3] - prefix[0] = 15 - 3 = 12

🔁 Carry-Forward Technique 

arr = [7, 3, 2, 1, 6, 2]
Enter fullscreen mode Exit fullscreen mode

Running subarray sums starting from index 2 (value = 2):

  • [2] → 2
  • [2,1] → 3
  • [2,1,6] → 9
  • [2,1,6,2] → 11

🔄 Global Sum of All Subarray Sums (with Carry Forward)

Example:

arr = [1, 2, 3]

Subarrays and their sums:
[1]       → 1
[1,2]     → 3
[1,2,3]   → 6
[2]       → 2
[2,3]     → 5
[3]       → 3

Total = 1+3+6+2+5+3 = 20
Enter fullscreen mode Exit fullscreen mode

🧮 Subarrays Containing a Given Element

Given A = [7, 3, 2, 1, 6, 2]

For A[2] = 2 (index 2):

  • It can start at any index from 0 to 2 (3 options)
  • It can end at any index from 2 to 5 (4 options)
  • So 2 is part of 3 × 4 = 12 subarrays

🔄 Total Contribution of Each Element to All Subarray Sums

Given:

arr = [1, 2, 3]

Subarray counts:
1 → appears in 3 subarrays
2 → appears in 4 subarrays
3 → appears in 3 subarrays

So:
1 * 3 + 2 * 4 + 3 * 3 = 3 + 8 + 9 = 20
Enter fullscreen mode Exit fullscreen mode

✅ Matches total from carry-forward method.

🧠 Final Summary

Goal Approach Time Complexity Example
Print all subarrays 2 loops O(N²) [1,2], [2,3]
Subarray sum from s to e Prefix sum O(1) prefix[e] - prefix[s-1]
Sum of all subarrays Carry forward O(N²) Nested sum accumulation
Sum of all subarrays (optimized) Element contribution O(N) (i+1)*(N-i)
Count of subarrays including A[i] Formula-based O(1) per index A[2] in 12 subarrays

Use prefix sums when querying random subarray sums.

Use carry-forward when computing totals in sequence.

Use contribution formula for fast aggregation over all subarrays.

Top comments (0)