DEV Community: Harry Alto

📘 Subarray Concepts

Harry Alto — Mon, 14 Jul 2025 04:56:31 +0000

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]

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

✅ Prefix Sum Technique (for fast sum queries)

Build:

arr = [3, 4, 6, 2, 8]
prefix = [3, 7, 13, 15, 23]

Query:

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

🔁 Carry-Forward Technique

arr = [7, 3, 2, 1, 6, 2]

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

🧮 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

✅ 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.

Solving Leetcode Problem of Finding Pivot Index

Harry Alto — Mon, 14 Jul 2025 04:29:42 +0000

🧠 Understanding the Pivot Index

When given an array of integers, can we find an index where the sum of all elements to its left equals the sum of all elements to its right?

That index is called the pivot index.

The link to the leetcode problem is here for reference: Leetcode 724

🧾 Problem Statement

You're given a list of integers nums. Find the pivot index where:

sum(nums[0:i]) == sum(nums[i+1:])

Return that index, or -1 if no such index exists.

There are three ways to solve the problem

🚧 Approach 1: Brute Force (O(n²))

In this simple approach, we loop through the array and compute the sum of elements on both sides of every index.

🔍 Logic

def pivot_index_brute_force(nums):
    for i in range(len(nums)):
        left_sum = sum(nums[:i])
        right_sum = sum(nums[i+1:])
        if left_sum == right_sum:
            return i
    return -1

⚠️ Downside

Repeated summing → O(n²) time
Works, but not scalable

🧮 Approach 2: Prefix and Suffix Arrays (O(n) Time, O(n) Space)

Let’s optimize it by precomputing prefix and suffix sums.

prefix[i]: sum of elements before i
suffix[i]: sum of elements after i

We then find the index where prefix[i] == suffix[i].

🔍 Logic

def pivot_index_prefix_suffix(nums):
    n = len(nums)
    prefix = [0] * n
    suffix = [0] * n

    for i in range(1, n):
        prefix[i] = prefix[i - 1] + nums[i - 1]

    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] + nums[i + 1]

    for i in range(n):
        if prefix[i] == suffix[i]:
            return i
    return -1

🧠 Intuition

We calculate the cumulative sum from the start to each index (prefix) and from the end to each index (suffix).

At each index i, if the sum of elements before it (prefix[i]) equals the sum of elements after it (suffix[i]), then that index is the pivot.

This avoids recalculating sums on every iteration and gives an efficient solution using two passes.

🧠 Approach 3: Optimized Mathematical Trick (O(n) Time, O(1) Space)

Here’s where the real magic happens! Let’s derive the core insight.

🧠 Intuition

We know:

left_sum + nums[i] + right_sum = total_sum

Since left_sum == right_sum, we substitute:

2 * left_sum + nums[i] = total_sum

So our pivot condition becomes:

if 2 * running_sum + nums[i] == total_sum

Where running_sum is the sum to the left of index i.

🔍 Logic

def pivot_index_optimized(nums):
    total_sum = sum(nums)
    running_sum = 0

    for i, val in enumerate(nums):
        if 2 * running_sum + val == total_sum:
            return i
        running_sum += val

    return -1

🧪 Example Walkthrough

Input: nums = [1, 7, 3, 6, 5, 6]

Index	Left Sum	Value	Right Sum	2×Left + Val	Equals total?
0	0	1	27	1	❌
1	1	7	20	9	❌
2	8	3	17	19	❌
3	11	6	11	✅ 28 = 28	✅ Pivot found

✅ Summary Table

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Simple but inefficient
Prefix & Suffix Arrays	O(n)	O(n)	Fast, uses extra memory
Optimized Math	O(n)	O(1)	Fastest and cleanest ✅

🔚 Final Thoughts

This is a classic case of turning a brute-force problem into an elegant, math-powered solution. It's not just about speed — it's about understanding the data flow.

➡ Know the definition

➡ Translate into equations

➡ Optimize with insight