Prefix Sum LeetCode Problems: All 157,
With Python Solutions

Every problem in this library that LeetCode tags Prefix Sum. 139 of them carry a complete Python solution, a worked example and the time and space complexity of the approach.

Get Stealth Interview

Easy: 14
Medium: 102
Hard: 41

1 pattern

How Prefix Sum problems are solved

A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Prefix Sum problems — each one explains the approach, gives a Python template and states its complexity.

Prefix SumPrecompute running totals once so any range query becomes a single subtraction.

Eyes only

When the Prefix Sum problem arrives live.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

Prefix Sum problems by difficulty

Problems with a complete Python solution are listed first, then by ascending problem number.

Easy (14)

Easy problems
No.	Problem	Topics
0303	Range Sum Query - Immutable	Design, Array, Prefix Sum
0724	Find Pivot Index	Array, Prefix Sum
1413	Minimum Value to Get Positive Step by Step Sum	Array, Prefix Sum
1422	Maximum Score After Splitting a String	String, Prefix Sum
1480	Running Sum of 1d Array	Array, Prefix Sum
1588	Sum of All Odd Length Subarrays	Array, Math, Prefix Sum
1732	Find the Highest Altitude	Array, Prefix Sum
1854	Maximum Population Year	Array, Counting, Prefix Sum
1893	Check if All the Integers in a Range Are Covered	Array, Hash Table, Prefix Sum
1991	Find the Middle Index in Array	Array, Prefix Sum
2389	Longest Subsequence With Limited Sum	Greedy, Array, Binary Search +2
2485	Find the Pivot Integer	Math, Prefix Sum
2574	Left and Right Sum Differences	Array, Prefix Sum
2848	Points That Intersect With Cars	Array, Hash Table, Prefix Sum

Medium (102)

Medium problems
No.	Problem	Topics
0209	Minimum Size Subarray Sum	Array, Binary Search, Prefix Sum +1
0238	Product of Array Except Self	Array, Prefix Sum
0304	Range Sum Query 2D - Immutable	Design, Array, Matrix +1
0497	Random Point in Non-overlapping Rectangles	Reservoir Sampling, Array, Math +4
0523	Continuous Subarray Sum	Array, Hash Table, Math +1
0525	Contiguous Array	Array, Hash Table, Prefix Sum
0528	Random Pick with Weight	Array, Math, Binary Search +2
0560	Subarray Sum Equals K	Array, Hash Table, Prefix Sum
0713	Subarray Product Less Than K	Array, Binary Search, Prefix Sum +1
0731	My Calendar II	Design, Segment Tree, Array +3
0813	Largest Sum of Averages	Array, Dynamic Programming, Prefix Sum
0848	Shifting Letters	Array, String, Prefix Sum
0930	Binary Subarrays With Sum	Array, Hash Table, Prefix Sum +1
0974	Subarray Sums Divisible by K	Array, Hash Table, Prefix Sum
1004	Max Consecutive Ones III	Array, Binary Search, Prefix Sum +1
1094	Car Pooling	Array, Prefix Sum, Sorting +2
1109	Corporate Flight Bookings	Array, Prefix Sum
1124	Longest Well-Performing Interval	Stack, Array, Hash Table +2
1140	Stone Game II	Array, Math, Dynamic Programming +2
1177	Can Make Palindrome from Substring	Bit Manipulation, Array, Hash Table +2
1208	Get Equal Substrings Within Budget	String, Binary Search, Prefix Sum +1
1248	Count Number of Nice Subarrays	Array, Hash Table, Math +2
1292	Maximum Side Length of a Square with Sum Less than or Equal to Threshold	Array, Binary Search, Matrix +1
1310	XOR Queries of a Subarray	Bit Manipulation, Array, Prefix Sum
1314	Matrix Block Sum	Array, Matrix, Prefix Sum
1352	Product of the Last K Numbers	Design, Array, Math +2
1371	Find the Longest Substring Containing Vowels in Even Counts	Bit Manipulation, Hash Table, String +1
1423	Maximum Points You Can Obtain from Cards	Array, Prefix Sum, Sliding Window
1442	Count Triplets That Can Form Two Arrays of Equal XOR	Bit Manipulation, Array, Hash Table +2
1508	Range Sum of Sorted Subarray Sums	Array, Two Pointers, Binary Search +2
1524	Number of Sub-arrays With Odd Sum	Array, Math, Dynamic Programming +1
1546	Maximum Number of Non-Overlapping Subarrays With Sum Equals Target	Greedy, Array, Hash Table +1
1589	Maximum Sum Obtained of Any Permutation	Greedy, Array, Prefix Sum +1
1590	Make Sum Divisible by P	Array, Hash Table, Prefix Sum
1658	Minimum Operations to Reduce X to Zero	Array, Hash Table, Binary Search +2
1664	Ways to Make a Fair Array	Array, Prefix Sum
1674	Minimum Moves to Make Array Complementary	Array, Hash Table, Prefix Sum
1685	Sum of Absolute Differences in a Sorted Array	Array, Math, Prefix Sum
1712	Ways to Split Array Into Three Subarrays	Array, Two Pointers, Binary Search +1
1737	Change Minimum Characters to Satisfy One of Three Conditions	Hash Table, String, Counting +1
1738	Find Kth Largest XOR Coordinate Value	Bit Manipulation, Array, Divide and Conquer +5
1744	Can You Eat Your Favorite Candy on Your Favorite Day?	Array, Prefix Sum
1769	Minimum Number of Operations to Move All Balls to Each Box	Array, String, Prefix Sum
1829	Maximum XOR for Each Query	Bit Manipulation, Array, Prefix Sum
1838	Frequency of the Most Frequent Element	Greedy, Array, Binary Search +3
1856	Maximum Subarray Min-Product	Stack, Array, Prefix Sum +1
1871	Jump Game VII	String, Dynamic Programming, Prefix Sum +1
1878	Get Biggest Three Rhombus Sums in a Grid	Array, Math, Matrix +3
1894	Find the Student that Will Replace the Chalk	Array, Binary Search, Prefix Sum +1
1895	Largest Magic Square	Array, Matrix, Prefix Sum
1915	Number of Wonderful Substrings	Bit Manipulation, Hash Table, String +1
1930	Unique Length-3 Palindromic Subsequences	Bit Manipulation, Hash Table, String +1
1943	Describe the Painting	Array, Hash Table, Prefix Sum +1
2017	Grid Game	Array, Matrix, Prefix Sum
2024	Maximize the Confusion of an Exam	String, Binary Search, Prefix Sum +1
2055	Plates Between Candles	Array, String, Binary Search +1
2100	Find Good Days to Rob the Bank	Array, Dynamic Programming, Prefix Sum
2121	Intervals Between Identical Elements	Array, Hash Table, Prefix Sum
2145	Count the Hidden Sequences	Array, Prefix Sum
2171	Removing Minimum Number of Magic Beans	Greedy, Array, Enumeration +2
2207	Maximize Number of Subsequences in a String	Greedy, String, Prefix Sum
2222	Number of Ways to Select Buildings	String, Dynamic Programming, Prefix Sum
2245	Maximum Trailing Zeros in a Cornered Path	Array, Matrix, Prefix Sum
2256	Minimum Average Difference	Array, Prefix Sum
2270	Number of Ways to Split Array	Array, Prefix Sum
2271	Maximum White Tiles Covered by a Carpet	Greedy, Array, Binary Search +3
2381	Shifting Letters II	Array, String, Prefix Sum
2391	Minimum Amount of Time to Collect Garbage	Array, String, Prefix Sum
2406	Divide Intervals Into Minimum Number of Groups	Greedy, Array, Two Pointers +3
2420	Find All Good Indices	Array, Dynamic Programming, Prefix Sum
2428	Maximum Sum of an Hourglass	Array, Matrix, Prefix Sum
2438	Range Product Queries of Powers	Bit Manipulation, Array, Prefix Sum
2439	Minimize Maximum of Array	Greedy, Array, Binary Search +2
2483	Minimum Penalty for a Shop	String, Prefix Sum
2536	Increment Submatrices by One	Array, Matrix, Prefix Sum
2559	Count Vowel Strings in Ranges	Array, String, Prefix Sum
2587	Rearrange Array to Maximize Prefix Score	Greedy, Array, Prefix Sum +1
2588	Count the Number of Beautiful Subarrays	Bit Manipulation, Array, Hash Table +1
2602	Minimum Operations to Make All Array Elements Equal	Array, Binary Search, Prefix Sum +1
2615	Sum of Distances	Array, Hash Table, Prefix Sum
2640	Find the Score of All Prefixes of an Array	Array, Prefix Sum
2680	Maximum OR	Greedy, Bit Manipulation, Array +1
2731	Movement of Robots	Brainteaser, Array, Prefix Sum +1
2772	Apply Operations to Make All Array Elements Equal to Zero	Array, Prefix Sum
2845	Count of Interesting Subarrays	Array, Hash Table, Prefix Sum
2875	Minimum Size Subarray in Infinite Array	Array, Hash Table, Prefix Sum +1
2906	Construct Product Matrix	Array, Matrix, Prefix Sum
2947	Count Beautiful Substrings I	Hash Table, Math, String +3
2971	Find Polygon With the Largest Perimeter	Greedy, Array, Prefix Sum +1
0253	Meeting Rooms IIPremium	Greedy, Array, Two Pointers +3
0325	Maximum Size Subarray Sum Equals kPremium	Array, Hash Table, Prefix Sum
0370	Range AdditionPremium	Array, Prefix Sum
1983	Widest Pair of Indices With Equal Range SumPremium	Array, Hash Table, Prefix Sum
2021	Brightest Position on StreetPremium	Array, Ordered Set, Prefix Sum +1
2083	Substrings That Begin and End With the Same LetterPremium	Hash Table, Math, String +2
2219	Maximum Sum Score of ArrayPremium	Array, Prefix Sum
2237	Count Positions on Street With Required BrightnessPremium	Array, Prefix Sum
2489	Number of Substrings With Fixed RatioPremium	Hash Table, Math, String +1
2505	Bitwise OR of All Subsequence SumsPremium	Bit Manipulation, Brainteaser, Array +2
2838	Maximum Coins Heroes Can CollectPremium	Array, Two Pointers, Binary Search +2
2950	Number of Divisible SubstringsPremium	Hash Table, String, Counting +1
2955	Number of Same-End SubstringsPremium	Array, Hash Table, String +2

Hard (41)

Hard problems
No.	Problem	Topics
0363	Max Sum of Rectangle No Larger Than K	Array, Binary Search, Matrix +2
0410	Split Array Largest Sum	Greedy, Array, Binary Search +2
0689	Maximum Sum of 3 Non-Overlapping Subarrays	Array, Dynamic Programming, Prefix Sum +1
0732	My Calendar III	Design, Segment Tree, Binary Search +2
0798	Smallest Rotation with Highest Score	Array, Prefix Sum
0862	Shortest Subarray with Sum at Least K	Queue, Array, Binary Search +4
0903	Valid Permutations for DI Sequence	String, Dynamic Programming, Prefix Sum
0995	Minimum Number of K Consecutive Bit Flips	Bit Manipulation, Queue, Array +2
1000	Minimum Cost to Merge Stones	Array, Dynamic Programming, Prefix Sum
1074	Number of Submatrices That Sum to Target	Array, Hash Table, Matrix +1
1420	Build Array Where You Can Find The Maximum Exactly K Comparisons	Dynamic Programming, Prefix Sum
1444	Number of Ways of Cutting a Pizza	Memoization, Array, Dynamic Programming +2
1687	Delivering Boxes from Storage to Ports	Segment Tree, Queue, Array +4
1703	Minimum Adjacent Swaps for K Consecutive Ones	Greedy, Array, Prefix Sum +1
1862	Sum of Floored Pairs	Array, Math, Binary Search +1
1872	Stone Game VIII	Array, Math, Dynamic Programming +2
1889	Minimum Space Wasted From Packaging	Array, Binary Search, Prefix Sum +1
2025	Maximum Number of Ways to Partition an Array	Array, Hash Table, Counting +2
2106	Maximum Fruits Harvested After at Most K Steps	Array, Binary Search, Prefix Sum +1
2132	Stamping the Grid	Greedy, Array, Matrix +1
2209	Minimum White Tiles After Covering With Carpets	String, Dynamic Programming, Prefix Sum
2218	Maximum Value of K Coins From Piles	Array, Dynamic Programming, Prefix Sum
2234	Maximum Total Beauty of the Gardens	Greedy, Array, Two Pointers +4
2251	Number of Flowers in Full Bloom	Array, Hash Table, Binary Search +3
2281	Sum of Total Strength of Wizards	Stack, Array, Prefix Sum +1
2302	Count Subarrays With Score Less Than K	Array, Binary Search, Prefix Sum +1
2382	Maximum Segment Sum After Removals	Union Find, Array, Ordered Set +1
2398	Maximum Number of Robots Within Budget	Queue, Array, Binary Search +4
2448	Minimum Cost to Make Array Equal	Greedy, Array, Binary Search +2
2478	Number of Beautiful Partitions	String, Dynamic Programming, Prefix Sum
2488	Count Subarrays With Median K	Array, Hash Table, Prefix Sum
2528	Maximize the Minimum Powered City	Greedy, Queue, Array +3
2552	Count Increasing Quadruplets	Binary Indexed Tree, Array, Dynamic Programming +2
2681	Power of Heroes	Array, Math, Dynamic Programming +2
2968	Apply Operations to Maximize Frequency Score	Array, Binary Search, Prefix Sum +2
2983	Palindrome Rearrangement Queries	Hash Table, String, Prefix Sum
0548	Split Array with Equal SumPremium	Array, Hash Table, Prefix Sum
0644	Maximum Average Subarray IIPremium	Array, Binary Search, Prefix Sum
1788	Maximize the Beauty of the GardenPremium	Greedy, Array, Hash Table +1
2819	Minimum Relative Loss After Buying ChocolatesPremium	Array, Binary Search, Prefix Sum +1
2949	Count Beautiful Substrings II	Hash Table, Math, String +2

How Prefix Sum problems are solved

When the Prefix Sum problem arrives live.

Approach

Approach

Approach

Prefix Sum problems by difficulty

Easy (14)14

Medium (102)102

Hard (41)41

Keep exploring

Easy (14)

Medium (102)

Hard (41)