Prefix Sum
Prefix Sum is a technique used with arrays to quickly compute the sum of elements in any subarray. It is especially useful when you need to perform multiple range sum queries efficiently.
🔹 Basic Idea
Given an array arr, the prefix sum array prefix is defined as:
prefix[0] = arr[0]
for i in range(1, len(arr)):
prefix[i] = prefix[i - 1] + arr[i]
🔹 Use Case: Subarray Sum
Solve this in leetcode
🔗 https://leetcode.com/problems/range-sum-query-immutable/
If you want to calculate the sum of elements from index l to r (arr[l] + arr[l+1] + ... + arr[r]), you can do:
(If l == 0, then the sum is just prefix[r].)
🔹 Example
arr = [2, 4, 1, 3, 5]
# Prefix sum computation
prefix = [2, 6, 7, 10, 15]
To find sum from index 1 to 3 (i.e., 4 + 1 + 3 = 8):
prefix[3]−prefix[0]=10−2=8
🔹 Time Complexity
- Building prefix sum: \(O(n)\)
- Query sum from index
ltor: \(O(1)\)
Same problem when solved in a naive way i.e find sub array sum of an array between
landris \(O(n)\) complexity which gets worsened if this method is queried multiple times. With Prefix sum, once prefix array is build, each query is an \(O(1)\) complexit.
📓 Usage
The Prefix Sum Problem is a classic in dynamic programming and has many real-world applications and algorithmic patterns. It’s particularly useful in problems involving combinations, constraints, and choices. Here are common patterns and scenarios where the Prefix sum problem (or its variants) is applicable:
🔹 1. Decision-Based Problems (Can we reach a sum?)
- Pattern: “Can we find a subset of numbers that adds up to target?”
🔹 2. Counting Subsets
- Pattern: “How many subsets sum to a target?”
🔹 3. Minimum/Maximum Subset Difference
- Pattern: “Split an array into two subsets with minimum difference between their sums.”
- Used in resource allocation and load balancing
🔹 4. Knapsack Variants
Pattern: “Choose items with weights and values to maximize value without exceeding capacity.”
Example: 0/1 Knapsack: Uses subset sum logic with added value dimension Bounded/Unbounded Knapsack LeetCode 474: Ones and Zeroes
🔹 5. Partitioning Problems
Pattern: “Can we partition the array into k subsets with equal sum?”
Example: LeetCode 698: Partition to K Equal Sum Subsets
🔹 6. Array Splitting for Target Conditions
Pattern: “Can we split or reorder the array to meet some sum criteria?”
Example: Equal sum partition Split array into subarrays with specific properties (e.g., sum = K)
🔹 7. Subset Sum with Constraints
Pattern: Add more rules, like subset size, number parity, or specific element requirements
Example: Find subset of exactly k elements summing to target Used in scheduling or budgeting problems
📝 Suggested Practice Problems
Easy
➡ Total Subarray with sum equals K
Medium
➡ Count the number of subarrays with exactly k odd numbers.
➡ Count the number of subarrays whose sum is divisible by k
Hard