Lesson 4 � Intermediate

Prefix Sum & Subarray Problems

Prefix sum ek precomputation technique hai jo range sum queries ko O(1) mein solve karti hai. Agar tumhe baar baar subarray sums nikalne hain, toh prefix sum tumhare liye best hai. Ye technique interview mein bahut kaam aati hai.

? 22 min✓ Intermediate✓ Arrays basics

Prefix Sum hota kya hai?

WHAT

Prefix sum ek array hai jismein har index pe uss index tak ke saare elements ka sum hota hai. MATLAB prefix[i] mein arr[0] + arr[1] + ... + arr[i-1] ka sum hota hai. Ek baar prefix sum bana lo toh kisi bhi range ka sum O(1) mein nikal sakte ho.

WHEN

Jab baar baar range sum queries aayein (kisi subarray ka sum nikalo), jab difference array banana ho, jab subarray problems solve karni ho (equal sum partitions, subarray sum equals k), ya jab 2D matrix mein region sum chahiye � tab prefix sum use karo.

WHERE

Range Sum Query, Subarray Sum Equals K, Contiguous Array, Find Pivot Index, Car Pooling � ye sab prefix sum se solve hote hain.

Mental Model: Imagine karo tum school mein ho aur teacher ne kaha hai ki har student apne roll number tak ka total marks bataaye. Agar tum pehle se cumulative total nikal lo (roll 1 ka total, roll 2 ka total, etc.), toh kisi bhi beech ke students ka total ek second mein bata sakte ho � bas dono totals subtract karo. Ye hai prefix sum ka magic.

Prefix Sum kaise banayein

Prefix sum banana bahut simple hai. Ek array lo aur cumulative sum nikalte jao. Python mein 2 tarike hain:

# Method 1: Direct cumulative sum
arr = [3, 1, 4, 1, 5, 9]
prefix = [0] * (len(arr) + 1)

for i in range(len(arr)):
 prefix[i+1] = prefix[i] + arr[i]

# prefix = [0, 3, 4, 8, 9, 14, 23]
# prefix[0] = 0 (empty prefix)
# prefix[1] = 3 (arr[0])
# prefix[2] = 3+1 = 4 (arr[0]+arr[1])
# prefix[3] = 3+1+4 = 8 (arr[0]+arr[1]+arr[2])

# Range sum: arr[i] to arr[j] ka sum
def range_sum(i, j):
 return prefix[j+1] - prefix[i]

# arr[1] to arr[3] ka sum = 1+4+1 = 6
print(range_sum(1, 3)) # prefix[4] - prefix[1] = 9 - 3 = 6

# Method 2: Pythonic way using itertools
from itertools import accumulate

arr = [3, 1, 4, 1, 5, 9]
prefix = list(accumulate(arr))
# prefix = [3, 4, 8, 9, 14, 23]

# Range sum: arr[i] to arr[j]
def range_sum(i, j):
 if i == 0:
 return prefix[j]
 return prefix[j] - prefix[i-1]

print(range_sum(1, 3)) # prefix[3] - prefix[0] = 8 - 3 = 5
# Note: ye method mein prefix 0-indexed hai

Important: 0-indexed prefix sum mein range_sum(i, j) = prefix[j] - prefix[i-1]. But agar prefix array extra 0 se start ho (prefix[0]=0), toh formula prefix[j+1] - prefix[i] hai. Dono methods same kaam karte hain, sirf indexing alag hai.

Prefix Sum ke Use Cases

Prefix sum sirf range sum ke liye nahi � bahut saare problems mein use hota hai. Ye kuch common use cases hain:

# Use Case 1: Subarray Sum Equals K
def subarray_sum_equals_k(arr, k):
 prefix_sum = 0
 count = 0
 prefix_map = {0: 1} # 0 sum ek baar aaya hai
 
 for num in arr:
 prefix_sum += num
 
 # Agar (prefix_sum - k) pehle aaya hai
 # toh uss point se current tak ka sum = k
 if (prefix_sum - k) in prefix_map:
 count += prefix_map[prefix_sum - k]
 
 prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
 
 return count

print(subarray_sum_equals_k([1, 2, 3, -3, 2], 3)) # 4

# Use Case 2: Find Pivot Index
def pivot_index(arr):
 total_sum = sum(arr)
 left_sum = 0
 
 for i in range(len(arr)):
 right_sum = total_sum - left_sum - arr[i]
 
 if left_sum == right_sum:
 return i
 
 left_sum += arr[i]
 
 return -1

print(pivot_index([1, 7, 3, 6, 5, 6])) # 3
# Index 3: left = 1+7+3 = 11, right = 5+6 = 11

Pattern Recognition: Agar question mein "subarray sum" ya "range sum" ya "equal partitions" hai � prefix sum try karo. Agar multiple range sum queries hain � toh prefix sum definitely best approach hai O(1) per query.

2D Prefix Sum

Matrix mein bhi prefix sum use hota hai. 2D prefix sum mein har cell mein uss cell tak ke saare elements ka sum hota hai (top-left corner se). Ye rectangular region sum ko O(1) mein solve karta hai.

# 2D Prefix Sum Construction
def build_2d_prefix(matrix):
 m, n = len(matrix), len(matrix[0])
 prefix = [[0] * (n + 1) for _ in range(m + 1)]
 
 for i in range(m):
 for j in range(n):
 prefix[i+1][j+1] = (matrix[i][j] 
 + prefix[i][j+1] 
 + prefix[i+1][j] 
 - prefix[i][j])
 
 return prefix

# Region sum: (r1,c1) se (r2,c2) tak
def region_sum(prefix, r1, c1, r2, c2):
 return (prefix[r2+1][c2+1] 
 - prefix[r1][c2+1] 
 - prefix[r2+1][c1] 
 + prefix[r1][c1])

matrix = [
 [1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]
prefix = build_2d_prefix(matrix)
print(region_sum(prefix, 1, 1, 2, 2)) # 5+6+8+9 = 28

Try it: code khud likho

Exercise

Question: Given array [1, 3, 5, 7, 9, 11], prefix sum array banao aur index 2 se 4 tak ka sum nikalo. Answer mein sirf sum daalo.

Question: Given array [1, 7, 3, 6, 5, 6], pivot index find karo jahan left sum = right sum. Answer mein sirf index daalo.

Common mistakes

Prefix array size galat rakhna: Prefix sum array ka size n+1 hona chahiye (n = arr length). Agar n rakha toh last element ka sum store nahi ho payega.
Off-by-one in indexing: Range sum formula galat rakhna � prefix[j+1] - prefix[i] vs prefix[j] - prefix[i-1]. Yaad rakho prefix array kaise banaya hai.
Negative numbers ka scene: Prefix sum negative numbers pe bhi kaam karta hai. But hash map approach mein duplicate sums handle karo � {0: 1} initialization zaroori hai.
2D prefix mein double counting: Inclusion-exclusion principle use karo � prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]. Bina subtract kiye galat aayega.

Lesson complete?

Prefix sum samajh aa gaya✓ Ab Module 01 ke top array problems dekhte hain � jo interviews mein sabse zyada puche jaate hain.