Prefix Sum Pattern

Precompute cumulative sums for O(1) range queries.

#	Title	Difficulty	Topics
1664	Ways to Make a Fair Array	Medium	dynamic programming
1703	Minimum Adjacent Swaps for K Consecutive Ones	Hard	sort
1712	Ways to Split Array Into Three Subarrays	Medium	two pointers
1737	Change Minimum Characters to Satisfy One of Three Conditions	Medium	greedy
1744	Can You Eat Your Favorite Candy on Your Favorite Day?	Medium	math
1749	Maximum Absolute Sum of Any Subarray	Medium	greedy
1856	Maximum Subarray Min-Product	Medium	stack
1906	Minimum Absolute Difference Queries	Medium	array
1937	Maximum Number of Points with Cost	Medium	dynamic programming
1966	Binary Searchable Numbers in an Unsorted Array	Medium	array
1983	Widest Pair of Indices With Equal Range Sum	Medium	array
1991	Find the Middle Index in Array	Easy	array
2012	Sum of Beauty in the Array	Medium	array
2017	Grid Game	Medium	array
2025	Maximum Number of Ways to Partition an Array	Hard	hash table
2031	Count Subarrays With More Ones Than Zeros	Medium	dynamic programming
2055	Plates Between Candles	Medium	array
2100	Find Good Days to Rob the Bank	Medium	array
2106	Maximum Fruits Harvested After at Most K Steps	Hard	array
2121	Intervals Between Identical Elements	Medium	array
2132	Stamping the Grid	Hard	array
2155	All Divisions With the Highest Score of a Binary Array	Medium	array
2163	Minimum Difference in Sums After Removal of Elements	Hard	binary heap
2219	Maximum Sum Score of Array	Medium	array
2234	Maximum Total Beauty of the Gardens	Hard	two pointers
2245	Maximum Trailing Zeros in a Cornered Path	Medium	array
2256	Minimum Average Difference	Medium	array
2270	Number of Ways to Split Array	Medium	array
2271	Maximum White Tiles Covered by a Carpet	Medium	array
2281	Sum of Total Strength of Wizards	Hard	stack
2382	Maximum Segment Sum After Removals	Hard	array
2391	Minimum Amount of Time to Collect Garbage	Medium	array
2409	Count Days Spent Together	Easy	math
2420	Find All Good Indices	Medium	dynamic programming
2438	Range Product Queries of Powers	Medium	array
2448	Minimum Cost to Make Array Equal	Hard	binary search
2463	Minimum Total Distance Traveled	Hard	dynamic programming
2484	Count Palindromic Subsequences	Hard	hash table
2488	Count Subarrays With Median K	Hard	hash table
2489	Number of Substrings With Fixed Ratio	Medium	hash table
2503	Maximum Number of Points From Grid Queries	Hard	breadth first search
2552	Count Increasing Quadruplets	Hard	dynamic programming
2554	Maximum Number of Integers to Choose From a Range I	Medium	binary search
2557	Maximum Number of Integers to Choose From a Range II	Medium	binary search
2559	Count Vowel Strings in Ranges	Medium	array
2574	Left and Right Sum Differences	Easy	array
2575	Find the Divisibility Array of a String	Medium	string
2599	Make the Prefix Sum Non-negative	Medium	greedy
2602	Minimum Operations to Make All Array Elements Equal	Medium	binary search
2615	Sum of Distances	Medium	hash table
2640	Find the Score of All Prefixes of an Array	Medium	array
2670	Find the Distinct Difference Array	Easy	hash table
2680	Maximum OR	Medium	greedy
2711	Difference of Number of Distinct Values on Diagonals	Medium	array
2735	Collecting Chocolates	Medium	stack
2790	Maximum Number of Groups With Increasing Length	Hard	greedy
2819	Minimum Relative Loss After Buying Chocolates	Hard	greedy
2836	Maximize Value of Function in a Ball Passing Game	Hard	graph
2845	Count of Interesting Subarrays	Medium	hash table
2875	Minimum Size Subarray in Infinite Array	Medium	two pointers
2903	Find Indices With Index and Value Difference I	Easy	array
2905	Find Indices With Index and Value Difference II	Medium	array
2906	Construct Product Matrix	Medium	array
2907	Maximum Profitable Triplets With Increasing Prices I	Medium	binary search tree
2908	Minimum Sum of Mountain Triplets I	Easy	array
2909	Minimum Sum of Mountain Triplets II	Medium	array
2921	Maximum Profitable Triplets With Increasing Prices II	Hard	binary search tree
2941	Maximum GCD-Sum of a Subarray	Hard	dynamic programming
2945	Find Maximum Non-decreasing Array Length	Hard	dynamic programming
2947	Count Beautiful Substrings I	Medium	hash table
2949	Count Beautiful Substrings II	Hard	hash table
2950	Number of Divisible Substrings	Medium	hash table
2955	Number of Same-End Substrings	Medium	hash table
2968	Apply Operations to Maximize Frequency Score	Hard	two pointers
2971	Find Polygon With the Largest Perimeter	Medium	greedy
2983	Palindrome Rearrangement Queries	Hard	hash table
3003	Maximize the Number of Partitions After Operations	Hard	greedy
3015	Count the Number of Houses at a Certain Distance I	Medium	array
3017	Count the Number of Houses at a Certain Distance II	Hard	array
3026	Maximum Good Subarray Sum	Medium	array
3028	Ant on the Boundary	Easy	array
3070	Count Submatrices with Top-Left Element and Sum Less Than k	Medium	array
3073	Maximum Increasing Triplet Value	Medium	binary search tree
3081	Replace Question Marks in String to Minimize Its Value	Medium	sort
3086	Minimum Moves to Pick K Ones	Hard	greedy
3096	Minimum Levels to Gain More Points	Medium	array
3098	Find the Sum of Subsequence Powers	Hard	dynamic programming
3152	Special Array II	Medium	array
3153	Sum of Digit Differences of All Pairs	Medium	array
3179	Find the N-th Value After K Seconds	Medium	math
3189	Minimum Moves to Get a Peaceful Board	Medium	greedy
3197	Find the Minimum Area to Cover All Ones II	Hard	dynamic programming
3205	Maximum Array Hopping Score I	Medium	greedy
3221	Maximum Array Hopping Score II	Medium	greedy
3224	Minimum Array Changes to Make Differences Equal	Medium	array
3225	Maximum Score From Grid Operations	Hard	dynamic programming
3250	Find the Count of Monotonic Pairs I	Hard	math
3251	Find the Count of Monotonic Pairs II	Hard	math
3261	Count Substrings That Satisfy K-Constraint II	Hard	two pointers
3287	Find the Maximum Sequence Value of Array	Hard	dynamic programming
3299	Sum of Consecutive Subsequences	Hard	math
3312	Sorted GCD Pair Queries	Hard	math
3323	Minimize Connected Groups by Inserting Interval	Medium	two pointers
3334	Find the Maximum Factor Score of Array	Medium	array
3348	Smallest Divisible Digit Product II	Hard	math
3354	Make Array Elements Equal to Zero	Easy	array
3361	Shift Distance Between Two Strings	Medium	array
3364	Minimum Positive Sum Subarray	Easy	two pointers
3372	Maximize the Number of Target Nodes After Connecting Trees I	Medium	dynamic programming
3381	Maximum Subarray Sum With Length Divisible by K	Medium	dynamic programming
3395	Subsequences with a Unique Middle Mode I	Hard	math
3410	Maximize Subarray Sum After Removing All Occurrences of One Element	Hard	greedy
3416	Subsequences with a Unique Middle Mode II	Hard	math
3425	Longest Special Path	Hard	two pointers
3432	Count Partitions with Even Sum Difference	Easy	array
3445	Maximum Difference Between Even and Odd Frequency II	Hard	two pointers
3473	Sum of K Subarrays With Length at Least M	Medium	dynamic programming
3485	Longest Common Prefix of K Strings After Removal	Hard	two pointers
3486	Longest Special Path II	Hard	two pointers
3494	Find the Minimum Amount of Time to Brew Potions	Medium	greedy
3500	Minimum Cost to Divide Array Into Subarrays	Hard	dynamic programming
3502	Minimum Cost to Reach Every Position	Easy	array
3511	Make a Positive Array	Medium	greedy
3532	Path Existence Queries in a Graph I	Medium	graph
3534	Path Existence Queries in a Graph II	Hard	graph
3538	Merge Operations for Minimum Travel Time	Hard	dynamic programming
3540	Minimum Time to Visit All Houses	Medium	array
3578	Count Partitions With Max-Min Difference at Most K	Medium	dynamic programming
3585	Find Weighted Median Node in Tree	Hard	tree
3598	Longest Common Prefix Between Adjacent Strings After Removals	Medium	string
3599	Partition Array to Minimize XOR	Medium	dynamic programming
3628	Maximum Number of Subsequences After One Inserting	Medium	dynamic programming
3632	Subarrays with XOR at Least K	Hard	bit manipulation
3651	Minimum Cost Path with Teleportations	Hard	dynamic programming
3654	Minimum Sum After Divisible Sum Deletions	Medium	dynamic programming
3656	Determine if a Simple Graph Exists	Medium	graph
3660	Jump Game IX	Medium	graph
3707	Equal Score Substrings	Easy	array
3709	Design Exam Scores Tracker	Medium	design
3714	Longest Balanced Substring II	Medium	hash table
3719	Longest Balanced Subarray I	Medium	array
3721	Longest Balanced Subarray II	Hard	array
3728	Stable Subarrays With Equal Boundary and Interior Sum	Medium	hash table
3729	Count Distinct Subarrays Divisible by K in Sorted Array	Hard	hash table
3737	Count Subarrays With Majority Element I	Medium	array
3738	Longest Non-Decreasing Subarray After Replacing at Most One Element	Medium	array
3739	Count Subarrays With Majority Element II	Hard	array
3748	Count Stable Subarrays	Hard	string
3755	Find Maximum Balanced XOR Subarray Length	Medium	hash table
3756	Concatenate Non-Zero Digits and Multiply by Sum II	Medium	array
3762	Minimum Operations to Equalize Subarrays	Hard	array
3765	Complete Prime Number	Medium	math
3771	Total Score of Dungeon Runs	Medium	binary search
3788	Maximum Score of a Split	Medium	array
3802	Number of Ways to Paint Sheets	Hard	two pointers
3814	Maximum Capacity Within Budget	Medium	array
3826	Minimum Partition Score	Hard	binary search
3830	Longest Alternating Subarray After Removing At Most One Element	Hard	dynamic programming
3845	Maximum Subarray XOR with Bounded Range	Hard	two pointers
3862	Find the Smallest Balanced Index	Medium	array
3864	Minimum Cost to Partition a Binary String	Hard	dynamic programming
3867	Sum of GCD of Formed Pairs	Medium	simulation
3883	Count Non Decreasing Arrays With Given Digit Sums	Medium	dynamic programming
3886	Sum of Sortable Integers	Hard	array
3903	Smallest Stable Index I	Easy	array
3904	Smallest Stable Index II	Medium	array
3911	K-th Smallest Remaining Even Integer in Subarray Queries	Hard	binary search
3912	Valid Elements in an Array	Medium	array
3916	Number of ZigZag Arrays III	Hard	dynamic programming
3918	Sum of Primes Between Number and Its Reverse	Medium	array
3919	Minimum Cost to Move Between Indices	Medium	greedy
3929	Minimum Partition Score II	Hard	binary search
3948	Lexicographically Maximum MEX Array	Hard	greedy
3956	Maximum Sum of M Non-Overlapping Subarrays I	Hard	binary search
3957	Maximum Sum of M Non-Overlapping Subarrays II	Hard	binary search
3962	Maximum Subarray Sum After at Most K Swaps	Hard	binary heap
3966	Count Good Integers in a Range	Hard	dynamic programming
3969	Valid Subarrays With Matching Sum Digits I	Medium	two pointers
3972	Valid Subarrays With Matching Sum Digits II	Hard	two pointers
3979	Maximum Valid Pair Sum	Medium	array
3981	Count Distinct Ways to Form Target from Two Strings	Hard	dynamic programming
3984	Divisible Game	Medium	math
3985	Palindromic Subarray Sum	Hard	array
3989	Maximum Consistent Columns in a Grid	Hard	dynamic programming