prefix sum

Minimum Size Subarray Sum

Find the minimal length of a subarray whose sum is greater than or equal to the target using efficient algorithms.

Product of Array Except Self

Solve the 'Product of Array Except Self' problem by calculating the product of all elements except self for each index e…

Range Sum Query - Immutable

The Range Sum Query - Immutable problem involves implementing a data structure to handle range sum queries efficiently.

Range Sum Query 2D - Immutable

Design a 2D matrix class that efficiently handles sum queries with O(1) time complexity using a prefix sum approach.

Max Sum of Rectangle No Larger Than K

Solve the "Max Sum of Rectangle No Larger Than K" problem using binary search over the valid sum space to optimize space…

Split Array Largest Sum

Solve the 'Split Array Largest Sum' problem by minimizing the largest sum across k subarrays using dynamic programming a…

Random Point in Non-overlapping Rectangles

Design an algorithm to pick random points within non-overlapping rectangles using binary search and reservoir sampling.

Continuous Subarray Sum

Identify if any continuous subarray sums to a multiple of k using prefix sums and hash table tracking efficiently.

Contiguous Array

Find the maximum length contiguous subarray with equal numbers of 0s and 1s using array scanning and hash lookup efficie…

Random Pick with Weight

Random Pick with Weight requires implementing a probabilistic index picker using prefix sums and binary search efficient…

Subarray Sum Equals K

Count the total number of contiguous subarrays in an integer array that sum exactly to a target value k using optimized …

Maximum Sum of 3 Non-Overlapping Subarrays

Maximize the sum of three non-overlapping subarrays with length k in an integer array using dynamic programming.

Subarray Product Less Than K

Count subarrays with a product strictly less than a given value k using efficient algorithms like binary search and slid…

Find Pivot Index

Find the pivot index in an array where the sums of elements on both sides are equal using array and prefix sum technique…

My Calendar II

Implement a calendar that allows double bookings but prevents triple bookings, managing overlapping intervals efficientl…

My Calendar III

Implement My Calendar III to track maximum overlapping events efficiently using binary search and segment tree technique…

Smallest Rotation with Highest Score

Find the smallest rotation index with the highest score using array and prefix sum techniques.

Largest Sum of Averages

Maximize the sum of averages by partitioning an integer array into at most k contiguous subarrays using dynamic programm…

Shifting Letters

Given a string and a shift array, shift the first i+1 letters of the string as specified in the array.

Shortest Subarray with Sum at Least K

Find the shortest subarray with a sum of at least k using binary search and sliding window techniques.

Valid Permutations for DI Sequence

The problem asks to find the number of valid permutations for a given DI sequence string using dynamic programming and s…

Binary Subarrays With Sum

Count all contiguous subarrays in a binary array whose elements sum exactly to a given goal using prefix sums efficientl…

Subarray Sums Divisible by K

Count the number of subarrays whose sum is divisible by a given integer k using array scanning and hash lookup.

Minimum Number of K Consecutive Bit Flips

Determine the minimum number of k-length consecutive bit flips needed to convert all zeros to ones in a binary array eff…

Minimum Cost to Merge Stones

Minimize the cost to merge stones with k consecutive piles using dynamic programming to achieve the optimal solution.

Max Consecutive Ones III

Find the longest consecutive ones in a binary array by optimally flipping at most k zeros using sliding window technique…

Number of Submatrices That Sum to Target

Count all non-empty submatrices in a given matrix whose elements sum exactly to the target using efficient scanning tech…

Car Pooling

Determine if a car can handle multiple trips without exceeding its capacity using array sorting and event simulation tec…

Corporate Flight Bookings

Solve Corporate Flight Bookings by marking range changes once, then building final seat totals with a single prefix sum …

Longest Well-Performing Interval

The Longest Well-Performing Interval problem challenges you to find the longest subarray where tiring days exceed non-ti…

Stone Game II

Stone Game II is a dynamic programming problem where Alice and Bob alternate taking stones from piles to maximize their …

Can Make Palindrome from Substring

Given a string and queries, determine if a substring can be rearranged and modified to form a palindrome.

Get Equal Substrings Within Budget

Optimize substring transformations using a binary search approach to maximize the change within a budget.

Count Number of Nice Subarrays

The problem requires counting subarrays with exactly k odd numbers using an efficient array scanning approach.

Maximum Side Length of a Square with Sum Less than or Equal to Threshold

This problem challenges you to find the largest square in a matrix with a sum below a given threshold using binary searc…

XOR Queries of a Subarray

Compute XOR results for multiple subarray queries using efficient prefix XOR to reduce repeated computation overhead in …

Matrix Block Sum

Compute a matrix where each cell contains the sum of all elements within k-distance blocks using prefix sums efficiently…

Product of the Last K Numbers

Design a data structure to efficiently return the product of the last k numbers in a dynamic integer stream using prefix…

Find the Longest Substring Containing Vowels in Even Counts

Find the longest substring with even counts of vowels using bitmasking and hash tables.

Minimum Value to Get Positive Step by Step Sum

Find the minimum starting value to ensure the step-by-step sum of an array is always at least 1.

Build Array Where You Can Find The Maximum Exactly K Comparisons

This problem asks to build an array where the maximum element is found using exactly K comparisons, with dynamic program…

Maximum Score After Splitting a String

Find the optimal split point in a binary string to maximize zeros on the left and ones on the right efficiently.

Maximum Points You Can Obtain from Cards

Maximize your score by selecting k cards from the beginning or end of the array using a sliding window approach.

Count Triplets That Can Form Two Arrays of Equal XOR

Efficiently count all triplets in an array where two subarrays formed by splitting have equal XOR using array scanning a…

Number of Ways of Cutting a Pizza

This problem challenges you to determine the number of valid ways to cut a pizza into pieces with apples using dynamic p…

Running Sum of 1d Array

Calculate the running sum of a given 1D array by updating each element to the sum of itself and all previous elements.

Range Sum of Sorted Subarray Sums

Compute the sum of sorted subarray sums efficiently using binary search over valid sum ranges and prefix sum accumulatio…

Number of Sub-arrays With Odd Sum

Count the number of subarrays with an odd sum using dynamic programming and prefix sum techniques.

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Find the maximum number of non-overlapping subarrays that sum to a given target using efficient scanning and hash lookup…

Sum of All Odd Length Subarrays

Calculate the sum of all odd-length subarrays in a given integer array using efficient array and math strategies.

Maximum Sum Obtained of Any Permutation

Maximize the total sum of requests on nums by greedily assigning larger numbers to most frequently requested indices.

Make Sum Divisible by P

Determine the minimum-length subarray to remove so the remaining array sum is divisible by a given integer p efficiently…

Minimum Operations to Reduce X to Zero

Find the minimum number of operations to reduce a value x to zero by removing elements from an array.

Ways to Make a Fair Array

Solve Ways to Make a Fair Array by tracking parity sums before and after each removal with prefix-sum style accounting.

Minimum Moves to Make Array Complementary

Find the minimum moves to make an array complementary by analyzing paired sums and using hash lookups for efficiency.

Sum of Absolute Differences in a Sorted Array

Calculate the sum of absolute differences between each element and others in a sorted array efficiently.

Delivering Boxes from Storage to Ports

Optimize the minimum number of trips to deliver boxes to ports under strict ship constraints using dynamic programming t…

Minimum Adjacent Swaps for K Consecutive Ones

Find the minimum number of adjacent swaps to gather k consecutive ones in a binary array using sliding window logic.

Ways to Split Array Into Three Subarrays

The problem requires finding the number of ways to split an array into three subarrays where each split meets a certain …

Find the Highest Altitude

Find the highest altitude after a series of altitude changes during a road trip using prefix sum technique.

Change Minimum Characters to Satisfy One of Three Conditions

This problem asks for the minimum operations to change two strings so that one of three conditions is met.

Find Kth Largest XOR Coordinate Value

Compute the kth largest XOR coordinate in a 2D matrix using prefix sums, bit manipulation, and optimized selection techn…

Can You Eat Your Favorite Candy on Your Favorite Day?

Determine if you can eat a candy of your favorite type on a specific day, given daily limits and candy availability.

Minimum Number of Operations to Move All Balls to Each Box

Solve the problem of finding the minimum operations to move balls to each box using an efficient approach with arrays an…

Maximum XOR for Each Query

Find the maximum XOR for each query based on a sorted array and bit manipulation.

Frequency of the Most Frequent Element

Maximize the frequency of an element in an array by incrementing at most `k` elements. Use binary search and greedy tech…

Maximum Population Year

Find the earliest year with the highest population using an array plus counting approach.

Maximum Subarray Min-Product

The problem asks to find the maximum min-product of any non-empty subarray of nums.

Sum of Floored Pairs

The problem asks to calculate the sum of floor divisions for all pairs in a given integer array, using an efficient meth…

Jump Game VII

The problem asks to determine if we can reach the last index of a binary string, with a set range of jumps between indic…

Stone Game VIII

Stone Game VIII requires calculating maximum score difference using state transition dynamic programming on prefix sums …

Get Biggest Three Rhombus Sums in a Grid

Find the three largest distinct rhombus sums from a given grid using array and math techniques.

Minimum Space Wasted From Packaging

Minimize the wasted space when packaging items into boxes, considering package and box size constraints.

Check if All the Integers in a Range Are Covered

Check if all integers in the range [left, right] are covered by intervals in a given set of ranges.

Find the Student that Will Replace the Chalk

Identify the first student who will run out of chalk using a simulation with prefix sums and binary search.

Largest Magic Square

Find the side length of the largest magic square in a matrix where row, column, and diagonal sums are equal.

Number of Wonderful Substrings

Count the number of wonderful non-empty substrings of a given string based on frequency conditions of characters.

Unique Length-3 Palindromic Subsequences

Count all unique length-3 palindromic subsequences in a string efficiently using hash tables and character positions.

Describe the Painting

Solve the problem of describing a painted segment with mixed colors using array scanning and hash table lookups.

Find the Middle Index in Array

Find the smallest middle index where the sum of elements on the left equals the sum on the right using prefix sums effic…

Grid Game

Solve the Grid Game problem by optimizing the movement of two robots on a 2D matrix grid.

Maximize the Confusion of an Exam

Maximize the Confusion of an Exam requires adjusting at most k answers to create the longest consecutive true or false s…

Maximum Number of Ways to Partition an Array

Determine the maximum number of ways to split an array into equal sums using at most one element change, leveraging pref…

Plates Between Candles

Determine the number of plates between candles in a given substring using binary search and prefix sum techniques.

Find Good Days to Rob the Bank

Find good days to rob the bank by identifying days with non-increasing and non-decreasing guard counts using dynamic pro…

Maximum Fruits Harvested After at Most K Steps

Compute the maximum fruits collectable on an infinite line by moving at most k steps from a start position efficiently.

Intervals Between Identical Elements

Solve the problem of calculating intervals between identical elements using array scanning and hash lookup.

Stamping the Grid

Determine if a binary grid can be fully covered using fixed-size stamps by applying a greedy placement and validation st…

Count the Hidden Sequences

Given a sequence of differences, count how many hidden sequences fit within a range using an array and prefix sum approa…

Removing Minimum Number of Magic Beans

Determine the minimum beans to remove so all remaining non-empty bags have equal beans using a greedy approach.

Maximize Number of Subsequences in a String

Maximize the number of subsequences by optimally adding a character to a given string to match a specified pattern.

Minimum White Tiles After Covering With Carpets

Find the minimum number of white tiles visible after optimally placing carpets using state transition dynamic programmin…

Maximum Value of K Coins From Piles

Optimize coin selection across multiple piles using state transition dynamic programming to achieve the maximum wallet v…

Number of Ways to Select Buildings

Solve Number of Ways to Select Buildings by counting alternating 3-building patterns with state transitions over the bin…

Maximum Total Beauty of the Gardens

Determine the maximum total beauty of gardens by strategically planting flowers using binary search over achievable flow…

Maximum Trailing Zeros in a Cornered Path

Find the maximum trailing zeros in the product of a cornered path within a 2D grid.

Number of Flowers in Full Bloom

Find the number of flowers in full bloom at the given times for a list of people.

Minimum Average Difference

Find the index with the minimum average difference in an array using prefix sums.

Number of Ways to Split Array

Count all valid ways to split a 0-indexed integer array into two non-empty parts using array plus prefix sum logic effic…

Maximum White Tiles Covered by a Carpet

Solve Maximum White Tiles Covered by a Carpet by sorting intervals, checking optimal carpet starts, and counting full pl…

Sum of Total Strength of Wizards

The Sum of Total Strength of Wizards problem asks for the sum of the total strengths of all contiguous subarrays of wiza…

Count Subarrays With Score Less Than K

Count all non-empty subarrays whose score, defined as sum times length, is strictly less than a given integer k efficien…

Shifting Letters II

Shift letters in a string using a sequence of range-based forward or backward operations efficiently with prefix sums.

Maximum Segment Sum After Removals

Calculate the maximum segment sum after sequential removals using array plus union find for efficient merging of segment…

Longest Subsequence With Limited Sum

Find the maximum size of a subsequence from nums with a sum less than or equal to each query value.

Minimum Amount of Time to Collect Garbage

This problem asks you to find the minimum amount of time needed to collect all garbage in a city, focusing on array and …

Maximum Number of Robots Within Budget

Determine the maximum number of consecutive robots you can operate without exceeding a given budget using efficient bina…

Divide Intervals Into Minimum Number of Groups

Determine the minimum number of non-overlapping groups for a set of intervals using precise two-pointer scanning logic.

Find All Good Indices

Identify all indices in an array where the k-length prefix is non-increasing and the k-length suffix is non-decreasing.

Maximum Sum of an Hourglass

Calculate the maximum sum of an hourglass in a 2D matrix using array traversal and submatrix evaluation techniques effic…

Range Product Queries of Powers

The Range Product Queries of Powers problem requires calculating the product of powers of 2 for a range of queries on a …

Minimize Maximum of Array

Minimize Maximum of Array involves finding the smallest possible maximum value after applying a series of operations on …

Minimum Cost to Make Array Equal

Find the minimum cost to make all elements of an array equal by using binary search over valid answers.

Minimum Penalty for a Shop

Determine the earliest closing hour of a shop to minimize penalty using a string of customer visits and prefix sums.

Find the Pivot Integer

Find the Pivot Integer problem challenges you to identify an integer x that balances prefix sums on both sides.

Count Subarrays With Median K

Count the number of subarrays in a given array with median equal to a specified value k.

Maximize the Minimum Powered City

Determine the maximum minimum power a city can achieve by strategically adding power stations using binary search and pr…

Increment Submatrices by One

Increment Submatrices by One focuses on efficiently updating submatrices using row-wise prefix sums in an n by n matrix.

Count Increasing Quadruplets

Given a permutation of numbers, count the number of increasing quadruplets using dynamic programming.

Count Vowel Strings in Ranges

Count the number of strings that start and end with a vowel in given ranges within an array of words.

Left and Right Sum Differences

Compute absolute differences between left and right cumulative sums for each element in an integer array efficiently.

Rearrange Array to Maximize Prefix Score

Maximize the number of positive prefix sums by rearranging an integer array using a greedy, order-focused strategy.

Count the Number of Beautiful Subarrays

Count the Number of Beautiful Subarrays is a Medium-level problem involving array scanning and hash table lookup to find…

Minimum Operations to Make All Array Elements Equal

Find the minimum number of operations to make all elements in an array equal for each query.

Sum of Distances

In this problem, you calculate an array where each element is the sum of absolute differences of indices for equal value…

Find the Score of All Prefixes of an Array

Compute the score of each prefix in an array using conversion rules while tracking the maximum efficiently for prefix su…

Maximum OR

Maximize the bitwise OR of an array by applying at most k multiplication operations on selected elements.

Power of Heroes

Calculate the total power of all non-empty hero groups using state transition dynamic programming efficiently with sorti…

Movement of Robots

Calculate total distances between robots moving on a number line while accounting for collisions using array plus braint…

Apply Operations to Make All Array Elements Equal to Zero

Determine if all elements in a given array can be reduced to zero using repeated k-length prefix operations efficiently.

Count of Interesting Subarrays

Count all subarrays where the number of elements satisfying a modulo condition equals a target k using efficient prefix …

Points That Intersect With Cars

Count covered integer points by merging overlapping car intervals or marking visited positions on the number line.

Minimum Size Subarray in Infinite Array

Find the shortest subarray in an infinite array that sums to a given target using array scanning and hash lookup.

Construct Product Matrix

Solve the "Construct Product Matrix" problem by calculating the product of elements in 2D matrices without division.

Count Beautiful Substrings I

Given a string and a value k, count the number of beautiful substrings where vowels * consonants % k == 0.

Count Beautiful Substrings II

Count Beautiful Substrings II focuses on finding beautiful substrings with hash tables and number theory techniques.

Apply Operations to Maximize Frequency Score

Maximize the frequency score by applying up to k operations on a sorted array using binary search over valid answer spac…

Find Polygon With the Largest Perimeter

Determine the largest perimeter polygon from a set of side lengths using a greedy approach with invariant validation che…

Palindrome Rearrangement Queries

Given a string and queries, check if rearranging specified substrings can make the string a palindrome.

Count the Number of Houses at a Certain Distance I

Determine the number of house pairs at each street distance using graph traversal and breadth-first search efficiently.

Count the Number of Houses at a Certain Distance II

Count the Number of Houses at a Certain Distance II is a graph problem that requires efficient pair counting with an add…

Maximum Good Subarray Sum

Find the maximum sum of any subarray where the first and last elements differ by exactly k using efficient array scannin…

Ant on the Boundary

Solve the problem of counting how often an ant returns to a boundary based on the steps described in the input array.

Count Submatrices with Top-Left Element and Sum Less Than k

Count all submatrices including the top-left element with sum less than k using array and matrix prefix sum strategies.

Maximum Strength of K Disjoint Subarrays

Solve Maximum Strength of K Disjoint Subarrays with dynamic programming that tracks segment state, sign changes, and wei…

Minimum Moves to Pick K Ones

Find the minimum number of moves to pick exactly k ones from a binary array, considering a constraint on changes.

Minimum Levels to Gain More Points

Determine the minimum number of levels Alice must play in a binary game array to secure more points than Bob using prefi…

Find All Possible Stable Binary Arrays I

Find all stable binary arrays of a given number of 0's, 1's, and limit using dynamic programming and state transitions.

Find All Possible Stable Binary Arrays II

Compute the number of stable binary arrays using state transition dynamic programming with exact zero, one, and limit co…

Taking Maximum Energy From the Mystic Dungeon

Maximize your energy by strategically jumping through magicians using array and prefix sum techniques for optimal path c…

Special Array II

Determine whether each subarray meets the special condition of alternating parity for all adjacent elements efficiently …

Find the N-th Value After K Seconds

Solve for the N-th value after K seconds by simulating array updates and using prefix sum techniques.

Minimum Operations to Make Binary Array Elements Equal to One I

Find the minimum number of operations to make all elements of a binary array equal to one using sliding window and state…

Count Submatrices With Equal Frequency of X and Y

Count the number of submatrices with equal frequency of 'X' and 'Y' in a 2D character grid.

Minimum Array Changes to Make Differences Equal

Minimize changes to make array differences equal by replacing elements within a given range.

Maximum Score From Grid Operations

Maximize your score by choosing the optimal sequence of column operations on a grid using dynamic programming transition…

Find the Count of Monotonic Pairs I

Compute the number of monotonic pairs in an integer array using state transition dynamic programming efficiently.

Find the Count of Monotonic Pairs II

This problem involves finding the count of monotonic pairs in an array using dynamic programming and combinatorics techn…

Count Substrings That Satisfy K-Constraint II

Count Substrings That Satisfy K-Constraint II requires finding valid substrings in a binary string based on a k-constrai…

Sorted GCD Pair Queries

Solve the Sorted GCD Pair Queries problem by efficiently counting and locating GCDs of all array pairs using hash mappin…

Find the Original Typed String II

Calculate how many potential original strings Alice might have intended to type, considering her clumsy typing behavior.

Maximum Frequency of an Element After Performing Operations I

Maximize the frequency of an element in an array after performing a series of operations to find the best possible resul…

Maximum Frequency of an Element After Performing Operations II

Determine the maximum frequency of any element after performing limited operations using binary search and sliding windo…

Make Array Elements Equal to Zero

Learn how to transform an integer array to zeros using simulation and directional selection efficiently and reliably.

Zero Array Transformation I

Transform the given integer array into a zero array using range operations, focusing on prefix sum optimization and care…

Zero Array Transformation II

Zero Array Transformation II requires determining the minimum query sequence to convert all array elements to zero using…

Shift Distance Between Two Strings

Find the minimum cost of transforming one string into another, considering operations between characters.

Zero Array Transformation III

Zero Array Transformation III requires removing the minimum number of queries to make all elements zero using greedy val…

Minimum Positive Sum Subarray

Find the minimum sum of any subarray of size between l and r with a positive total using efficient sliding window logic.

Maximum Subarray Sum With Length Divisible by K

Find the maximum sum of a subarray where the length of the subarray is divisible by k.

Maximum Coins From K Consecutive Bags

Solve the problem of maximizing coins from selecting k consecutive bags, using binary search and sliding window techniqu…

Longest Special Path

Compute the longest downward path in a tree with unique node values using DFS, hash lookup, and careful array scanning.

Sum of Variable Length Subarrays

Calculate the total sum of all elements in subarrays defined for each index in an array, using the array plus prefix sum…

Count Partitions with Even Sum Difference

Count the number of partitions with an even sum difference from an array of integers.

Maximum Frequency After Subarray Operation

Determine the maximum frequency of a target value k after applying one subarray addition operation efficiently using arr…

Maximum Difference Between Even and Odd Frequency II

Find the maximum difference between even and odd character frequencies in substrings using sliding window updates effici…

Sum of K Subarrays With Length at Least M

Maximize the sum of k non-overlapping subarrays of at least length m using dynamic programming and prefix sums efficient…

Maximize Subarrays After Removing One Conflicting Pair

Maximize the count of subarrays after removing one conflicting pair using array traversal and segment tree logic efficie…

Longest Special Path II

Find the longest downward path in a tree where node values are mostly distinct, allowing one repeat, using array scannin…

Find the Minimum Amount of Time to Brew Potions

This problem involves calculating the minimum time required for wizards to brew potions based on their skills and mana u…

Minimum Cost to Divide Array Into Subarrays

Optimize array splits with dynamic programming to minimize costs for the Minimum Cost to Divide Array Into Subarrays pro…

Merge Operations for Minimum Travel Time

Minimize the total travel time by merging road signs, using dynamic programming to manage state transitions efficiently.

Equal Sum Grid Partition I

Determine if an m x n matrix grid can be split into two non-empty sections with equal sums by making a single horizontal…

Equal Sum Grid Partition II

Determine if a matrix can be partitioned into two sections with an equal sum using a single cut.

Count Partitions With Max-Min Difference at Most K

Count the number of valid ways to partition an array into contiguous segments where max-min difference is at most k.

Partition Array to Minimize XOR

Partition an integer array into k subarrays to minimize the maximum XOR using state transition dynamic programming effic…