1. Lemonade Change
Easy · LC 860
Customers line up paying for five-dollar lemonade with five, ten, or twenty dollar bills, and the task is to report whether correct change can always be given starting with no cash. Track counts of fives and tens, paying out the largest usable bills first for each purchase. The greedy point is that a twenty should be changed with a ten plus a five when possible, since fives are the scarce universal resource.
def lemonade_change(bills: list[int]) -> bool:
"""LC 860. Lemonade Change.
Track counts of fives and tens and break every payment with the
BIGGEST bills first: a twenty takes a ten plus a five when both
exist, falling back to three fives. The invariant: a five is the
only bill that can change everything, so spending a ten before
fives never hurts and hoarding fives never helps less. O(n) time,
O(1) space.
"""
fives = tens = 0
for bill in bills:
if bill == 5:
fives += 1
elif bill == 10:
if fives == 0:
return False
fives -= 1
tens += 1
else: # bill == 20 -- twenties are never useful as change, drop them
if tens and fives: # biggest first: 10 + 5 saves a scarce five
tens -= 1
fives -= 1
elif fives >= 3:
fives -= 3
else:
return False
return True
// LC 860. Track only counts of fives and tens (twenties are never given back)
// and make change with the largest bills first: a ten plus a five for a
// twenty whenever possible, three fives only as a fallback. The greedy
// invariant is that fives are the scarce universal resource -- they are the
// only bill that changes a ten -- so spending a ten first is never worse.
bool lemonadeChange(vector<int> bills) {
int fives = 0, tens = 0;
for (int bill : bills) {
if (bill == 5) {
++fives;
} else if (bill == 10) {
if (fives == 0) return false;
--fives;
++tens;
} else { // 20: prefer 10 + 5, fall back to 5 + 5 + 5
if (tens > 0 && fives > 0) {
--tens;
--fives;
} else if (fives >= 3) {
fives -= 3;
} else {
return false;
}
}
}
return true;
}
/// LC 860. Count fives and tens; change a twenty with ten + five before three
/// fives. The invariant: fives are the only bill every payment can use, so
/// spending the scarcest-but-universal resource last is always safe.
pub fn lemonade_change(bills: Vec<i32>) -> bool {
let (mut fives, mut tens) = (0, 0);
for bill in bills {
match bill {
5 => fives += 1,
10 => {
if fives == 0 {
return false;
}
fives -= 1;
tens += 1;
}
_ => {
// 20: prefer ten + five, fall back to three fives.
if tens > 0 && fives > 0 {
tens -= 1;
fives -= 1;
} else if fives >= 3 {
fives -= 3;
} else {
return false;
}
}
}
}
true
}
/** LC 860. Count fives and tens; change a twenty with ten + five before three fives, since fives are the scarce universal resource. */
export function lemonadeChange(bills: number[]): boolean {
let fives = 0;
let tens = 0;
for (const bill of bills) {
if (bill === 5) {
fives++;
} else if (bill === 10) {
if (fives === 0) return false;
fives--;
tens++;
} else if (tens > 0 && fives > 0) {
tens--; // spend the ten first: tens only ever fit into twenties
fives--;
} else if (fives >= 3) {
fives -= 3;
} else {
return false;
}
}
return true;
}
// LC 860. Break every payment with the biggest bills first; fives are the
// scarce universal change, so spending a ten before fives never hurts.
func lemonadeChange(bills []int) bool {
fives, tens := 0, 0
for _, bill := range bills {
switch bill {
case 5:
fives++
case 10:
if fives == 0 {
return false
}
fives--
tens++
default: // 20: prefer 10 + 5, fall back to three fives
if tens > 0 && fives > 0 {
tens--
fives--
} else if fives >= 3 {
fives -= 3
} else {
return false
}
}
}
return true
}
// LC 860. Track only fives and tens and break a twenty with ten-plus-five
// before three fives: fives are the scarce bill that changes everything.
func lemonadeChange(_ bills: [Int]) -> Bool {
var fives = 0, tens = 0
for bill in bills {
if bill == 5 {
fives += 1
} else if bill == 10 {
if fives == 0 { return false }
fives -= 1
tens += 1
} else { // 20: prefer 10 + 5, fall back to 5 + 5 + 5
if tens > 0 && fives > 0 {
tens -= 1
fives -= 1
} else if fives >= 3 {
fives -= 3
} else {
return false
}
}
}
return true
}
2. Maximum Subarray
Medium · LC 53
Given an integer array, return the largest sum of any contiguous subarray. Kadane's algorithm walks the array once keeping a running sum that restarts at the current element whenever the running sum has gone negative, while tracking the best sum seen. The invariant is that a negative prefix can never help a later subarray, so dropping it is always safe, giving O(n) time.
def max_sub_array(nums: list[int]) -> int:
"""LC 53. Maximum Subarray.
Kadane's algorithm: sweep once with best_ending_here, the largest
sum of a subarray ending exactly at the current index, and track
the best value it ever takes. The invariant: a negative running
prefix can never help any later subarray, so resetting to the bare
element whenever the carry has gone negative is always safe.
O(n) time, O(1) space.
"""
best = best_ending_here = nums[0]
for num in nums[1:]:
# reset invariant: a negative carry only drags num down, drop it
best_ending_here = max(num, best_ending_here + num)
best = max(best, best_ending_here)
return best
// LC 53. Kadane: cur is the best sum of a subarray ENDING here. The invariant
// is that a negative prefix can never help anything that follows, so restart
// at the bare element whenever extending would carry a negative sum, and
// track the global best along the way. O(n) time, O(1) space.
int maxSubArray(vector<int> nums) {
int best = nums[0], cur = nums[0];
for (int i = 1; i < static_cast<int>(nums.size()); ++i) {
cur = max(nums[i], cur + nums[i]);
best = max(best, cur);
}
return best;
}
/// LC 53. Kadane: a running sum that restarts at the current element whenever
/// the carried prefix is negative. The invariant -- a negative prefix can
/// never help any later subarray -- makes dropping it always safe. O(n).
pub fn max_sub_array(nums: Vec<i32>) -> i32 {
let mut cur = nums[0];
let mut best = nums[0];
for &x in &nums[1..] {
cur = x.max(cur + x);
best = best.max(cur);
}
best
}
/** LC 53. Kadane: the running sum restarts at the current element once the prefix goes negative; a negative prefix never helps a later subarray. */
export function maxSubArray(nums: number[]): number {
let best = nums[0];
let running = nums[0]; // best sum of a subarray ending at i
for (let i = 1; i < nums.length; i++) {
running = Math.max(nums[i], running + nums[i]);
best = Math.max(best, running);
}
return best;
}
// LC 53. Kadane: a negative running prefix can never help what follows, so
// restart at the bare element and track the best sum ending here.
func maxSubArray(nums []int) int {
best, cur := nums[0], nums[0]
for _, num := range nums[1:] {
if cur+num < num {
cur = num // drop the negative carry
} else {
cur += num
}
if cur > best {
best = cur
}
}
return best
}
// LC 53. Kadane: a negative running prefix never helps what follows, so
// restart at the bare element where the carry hurts and track the best.
func maxSubArray(_ nums: [Int]) -> Int {
var best = nums[0], cur = nums[0]
for i in 1..<nums.count {
cur = max(nums[i], cur + nums[i])
best = max(best, cur)
}
return best
}
3. Maximum Sum Circular Subarray
Medium · LC 918
Given a circular integer array, return the maximum possible sum of a nonempty subarray that may wrap around the end. Run Kadane's for both the maximum and the minimum subarray, then take the larger of the plain maximum and total sum minus the minimum, since a wrapping subarray complements a middle minimum. The pitfall is the all-negative array, where total minus minimum describes an empty subarray, so return the plain Kadane answer there.
def max_subarray_sum_circular(nums: list[int]) -> int:
"""LC 918. Maximum Sum Circular Subarray.
A wrapping subarray is the complement of a plain middle subarray,
so its sum is total minus a MINIMUM subarray sum; answer with
max(plain Kadane, total - min Kadane). The invariant: every
nonempty subarray of the circle is either plain or the complement
of a plain one, so the two candidates cover all cases. O(n) time,
O(1) space.
"""
def kadane(values: list[int]) -> int:
best = best_ending_here = values[0]
for value in values[1:]:
best_ending_here = max(value, best_ending_here + value)
best = max(best, best_ending_here)
return best
best_plain = kadane(nums)
if best_plain < 0:
# all-negative guard: total - min strips EVERY element, which
# is the forbidden empty subarray, so the plain answer stands
return best_plain
best_wrap = sum(nums) + kadane([-value for value in nums]) # total - min
return max(best_plain, best_wrap)
// LC 918. A wrapping subarray is exactly the complement of a non-wrapping
// MINIMUM subarray, so run Kadane for both extremes in one pass and answer
// max(plain max, total - min). The all-negative guard: there the minimum
// swallows the whole array and total - min describes the forbidden empty
// subarray, so when the plain max is negative return it alone.
int maxSubarraySumCircular(vector<int> nums) {
int total = 0;
int maxCur = 0, maxBest = nums[0];
int minCur = 0, minBest = nums[0];
for (int x : nums) {
total += x;
maxCur = max(x, maxCur + x);
maxBest = max(maxBest, maxCur);
minCur = min(x, minCur + x);
minBest = min(minBest, minCur);
}
return maxBest < 0 ? maxBest : max(maxBest, total - minBest);
}
/// LC 918. A wrapping subarray is the total minus a middle minimum subarray,
/// so run Kadane for both max and min in one pass and take the larger of the
/// plain max and total - min. All-negative guard: there total - min describes
/// the forbidden empty subarray, so return the plain Kadane answer instead.
pub fn max_subarray_sum_circular(nums: Vec<i32>) -> i32 {
let mut total = 0;
let (mut cur_max, mut best_max) = (0, i32::MIN);
let (mut cur_min, mut best_min) = (0, i32::MAX);
for &x in &nums {
total += x;
cur_max = x.max(cur_max + x);
best_max = best_max.max(cur_max);
cur_min = x.min(cur_min + x);
best_min = best_min.min(cur_min);
}
if best_max < 0 {
best_max // every element negative: best single element, no wrap
} else {
best_max.max(total - best_min)
}
}
/** LC 918. Kadane for max AND min in one pass; a wrapping subarray complements a middle minimum, so answer max(best, total - worst). All-negative guard: total - worst is the empty subarray, fall back to the plain Kadane best. */
export function maxSubarraySumCircular(nums: number[]): number {
let total = 0;
let maxEnding = 0; // best sum of a subarray ending here
let minEnding = 0; // worst sum of a subarray ending here
let best = -Infinity;
let worst = Infinity;
for (const num of nums) {
total += num;
maxEnding = Math.max(num, maxEnding + num);
best = Math.max(best, maxEnding);
minEnding = Math.min(num, minEnding + num);
worst = Math.min(worst, minEnding);
}
return best < 0 ? best : Math.max(best, total - worst); // best < 0 means all negative
}
// LC 918. A wrapping subarray is the complement of a minimum one, so answer
// max(plain Kadane, total - min Kadane); all-negative keeps the plain answer.
func maxSubarraySumCircular(nums []int) int {
total := 0
maxCur, maxBest := 0, nums[0]
minCur, minBest := 0, nums[0]
for _, x := range nums {
total += x
if maxCur+x > x {
maxCur += x
} else {
maxCur = x
}
if maxCur > maxBest {
maxBest = maxCur
}
if minCur+x < x {
minCur += x
} else {
minCur = x
}
if minCur < minBest {
minBest = minCur
}
}
if maxBest < 0 {
return maxBest // total - min would strip everything: the empty subarray
}
if total-minBest > maxBest {
return total - minBest
}
return maxBest
}
// LC 918. A wrapping subarray is total minus a MINIMUM subarray; answer
// max(plain Kadane, total - min Kadane), all-negative guarded by plain alone.
func maxSubarraySumCircular(_ nums: [Int]) -> Int {
var total = 0
var maxCur = 0, maxBest = nums[0]
var minCur = 0, minBest = nums[0]
for x in nums {
total += x
maxCur = max(x, maxCur + x)
maxBest = max(maxBest, maxCur)
minCur = min(x, minCur + x)
minBest = min(minBest, minCur)
}
return maxBest < 0 ? maxBest : max(maxBest, total - minBest)
}
4. Longest Turbulent Subarray
Medium · LC 978
Given an integer array, return the length of the longest subarray where comparisons between consecutive elements strictly alternate between greater and less. Sweep once, extending the current run when the sign of the new comparison flips from the previous one, and resetting otherwise. The detail to remember is the reset: equal neighbors reset the run to length one, while a non-alternating strict comparison resets to length two, since that pair starts a fresh run.
def max_turbulence_size(arr: list[int]) -> int:
"""LC 978. Longest Turbulent Subarray.
Sweep once keeping the length of the turbulent run ending here:
extend it while the comparison sign between neighbors keeps
flipping, otherwise reset -- to 2 on a repeated strict sign (that
pair still starts a fresh run) or to 1 on equal neighbors. The
invariant: the run ending at i depends only on the run at i - 1
and the newest comparison sign. O(n) time, O(1) space.
"""
best = run = 1
prev_sign = 0 # sign of the previous comparison; 0 = none usable yet
for i in range(1, len(arr)):
sign = (arr[i - 1] < arr[i]) - (arr[i - 1] > arr[i]) # -1, 0, or +1
if sign == 0:
run = 1 # equal neighbors: no turbulent pair survives them
elif sign == -prev_sign and prev_sign != 0:
run += 1 # signs alternate: the run extends
else:
run = 2 # strict pair with the wrong sign BEGINS a fresh run
best = max(best, run)
prev_sign = sign
return best
// LC 978. One sweep over adjacent comparisons keeping the current turbulent
// run length; the invariant is that run counts the longest alternating run
// ENDING at i. A sign flip from the previous comparison extends the run,
// equal neighbors reset it to 1, and a repeated strict sign resets it to 2
// because the offending pair itself starts a fresh run.
int maxTurbulenceSize(vector<int> arr) {
auto sgn = [](int a, int b) -> int { return a < b ? -1 : (a > b ? 1 : 0); };
int best = 1, run = 1, prevSign = 0; // 0: no usable previous comparison
for (int i = 1; i < static_cast<int>(arr.size()); ++i) {
int sign = sgn(arr[i - 1], arr[i]);
if (sign == 0)
run = 1; // equal neighbors break every run
else if (sign == -prevSign)
++run; // alternation continues
else
run = 2; // this pair starts a fresh run
prevSign = sign;
best = max(best, run);
}
return best;
}
/// LC 978. One sweep tracking the sign of each neighbor comparison: a flipped
/// sign extends the run, equal neighbors reset to length 1, and a repeated
/// strict sign resets to length 2 because that pair already starts a fresh
/// turbulent run -- the reset value people get wrong.
pub fn max_turbulence_size(arr: Vec<i32>) -> i32 {
let mut best = 1;
let mut run = 1;
let mut prev_sign = 0;
for i in 1..arr.len() {
let sign = (arr[i] - arr[i - 1]).signum();
if sign == 0 {
run = 1;
} else if prev_sign != 0 && sign == -prev_sign {
run += 1;
} else {
run = 2;
}
prev_sign = sign;
best = best.max(run);
}
best
}
/** LC 978. One sweep on the sign of consecutive deltas: a flip extends the run, equal neighbors reset to 1, a repeated sign resets to 2 since that pair starts a fresh run. */
export function maxTurbulenceSize(arr: number[]): number {
let best = 1;
let run = 1; // turbulent run ending at i
let prevSign = 0; // sign of arr[i-1] - arr[i-2]; 0 means no usable comparison yet
for (let i = 1; i < arr.length; i++) {
const sign = Math.sign(arr[i] - arr[i - 1]);
if (sign === 0) run = 1; // equal neighbors break every run
else if (prevSign !== 0 && sign === -prevSign) run++; // strict alternation continues
else run = 2; // the new pair alone is turbulent
prevSign = sign;
best = Math.max(best, run);
}
return best;
}
// LC 978. Extend the run while comparison signs alternate; equal neighbors
// reset it to 1, a repeated strict sign starts a fresh run of 2.
func maxTurbulenceSize(arr []int) int {
sgn := func(a, b int) int {
switch {
case a < b:
return -1
case a > b:
return 1
}
return 0
}
best, run, prevSign := 1, 1, 0 // 0: no usable previous comparison
for i := 1; i < len(arr); i++ {
sign := sgn(arr[i-1], arr[i])
switch {
case sign == 0:
run = 1 // equal neighbors break every run
case sign == -prevSign:
run++ // alternation continues
default:
run = 2 // this pair starts a fresh run
}
prevSign = sign
if run > best {
best = run
}
}
return best
}
// LC 978. Extend the run while comparison signs alternate; equal neighbors
// reset to 1, a repeated strict sign starts a fresh run of 2.
func maxTurbulenceSize(_ arr: [Int]) -> Int {
func sgn(_ a: Int, _ b: Int) -> Int { a < b ? -1 : (a > b ? 1 : 0) }
var best = 1, run = 1, prevSign = 0 // 0: no usable previous comparison
for i in 1..<arr.count {
let sign = sgn(arr[i - 1], arr[i])
if sign == 0 {
run = 1 // equal neighbors break every run
} else if sign == -prevSign && prevSign != 0 {
run += 1 // alternation continues
} else {
run = 2 // this pair starts a fresh run
}
prevSign = sign
best = max(best, run)
}
return best
}
5. Jump Game
Medium · LC 55
Given an array where each value is the maximum jump length from that index, decide whether the last index is reachable from the first. Sweep left to right maintaining the farthest index reachable so far, updating it with i plus nums[i] at every position still within reach. The invariant is that if the sweep ever reaches an index beyond the current farthest reach, the answer is false; otherwise reaching the end proves true.
def can_jump(nums: list[int]) -> bool:
"""LC 55. Jump Game.
Sweep left to right maintaining farthest_reach, the largest index
any visited position can launch to. The invariant: every index up
to farthest_reach is reachable, so the first index strictly beyond
it proves the end can never be reached. O(n) time, O(1) space.
"""
farthest_reach = 0
for i, step in enumerate(nums):
if i > farthest_reach:
return False # a gap: nothing before i could jump past it
farthest_reach = max(farthest_reach, i + step)
return True
// LC 55. Sweep left to right maintaining farthest, the highest index
// reachable so far -- the invariant is that every index <= farthest is
// reachable. If i ever exceeds farthest the gap is unbridgeable and the
// answer is false; otherwise extend with i + nums[i], and surviving the scan
// proves the last index reachable.
bool canJump(vector<int> nums) {
int farthest = 0;
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
if (i > farthest) return false; // stranded before an unreachable gap
farthest = max(farthest, i + nums[i]);
}
return true;
}
/// LC 55. Sweep maintaining the farthest index reachable so far. The
/// invariant: every index at or before the farthest reach is reachable, so
/// standing on an index beyond it proves failure, and finishing the sweep
/// proves the last index is reachable.
pub fn can_jump(nums: Vec<i32>) -> bool {
let mut farthest = 0;
for (i, &x) in nums.iter().enumerate() {
if i > farthest {
return false;
}
farthest = farthest.max(i + x as usize);
}
true
}
/** LC 55. Sweep tracking the farthest reachable index; standing past it means stranded, finishing the sweep proves the end is reachable. */
export function canJump(nums: number[]): boolean {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false; // this index is beyond every previous jump
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// LC 55. Farthest-reach sweep: every index up to farthest is reachable, so
// the first index strictly beyond it proves an unbridgeable gap.
func canJump(nums []int) bool {
farthest := 0
for i, step := range nums {
if i > farthest {
return false // stranded before an unreachable gap
}
if i+step > farthest {
farthest = i + step
}
}
return true
}
// LC 55. Farthest-reach sweep: every index up to farthest is reachable, so
// the first index strictly beyond it proves an unbridgeable gap.
func canJump(_ nums: [Int]) -> Bool {
var farthest = 0
for i in 0..<nums.count {
if i > farthest { return false } // stranded before an unreachable gap
farthest = max(farthest, i + nums[i])
}
return true
}
6. Jump Game II
Medium · LC 45
Given an array of maximum jump lengths with the end guaranteed reachable, return the fewest jumps to the last index. Sweep with two markers, the end of the current jump's range and the farthest reach seen, and when i crosses the range end, count one jump and extend the range to the farthest reach. This is implicit BFS where each range is one level, so jumps are counted per boundary, not per step.
def jump(nums: list[int]) -> int:
"""LC 45. Jump Game II.
Sweep with two markers: current_range_end bounds the indices
reachable in the jumps counted so far, and farthest_reach is the
best launch seen inside that range; when i crosses the range end,
count one jump and adopt farthest_reach as the new end. This is
implicit BFS -- each (old end, new end] window is one BFS layer,
so jumps are counted per layer boundary, never per element. The
invariant: current_range_end is exactly the farthest index
reachable in `jumps` jumps. O(n) time, O(1) space.
"""
jumps = 0
current_range_end = 0 # last index inside the current BFS layer
farthest_reach = 0
for i in range(len(nums) - 1): # the last index never jumps out
farthest_reach = max(farthest_reach, i + nums[i])
if i == current_range_end:
jumps += 1 # crossing into the next BFS layer costs one jump
current_range_end = farthest_reach
return jumps
// LC 45. Implicit BFS with range-end jump counting: [.., rangeEnd] holds
// every index reachable in `jumps` jumps, and farthest accumulates the best
// reach from inside the level. When i crosses rangeEnd, count ONE jump and
// extend the range to farthest -- jumps are counted per level boundary, never
// per step. Stopping the scan before the last index avoids a spurious jump.
int jump(vector<int> nums) {
int jumps = 0, rangeEnd = 0, farthest = 0;
for (int i = 0; i + 1 < static_cast<int>(nums.size()); ++i) {
farthest = max(farthest, i + nums[i]);
if (i == rangeEnd) { // current level exhausted: take one more jump
++jumps;
rangeEnd = farthest;
}
}
return jumps;
}
/// LC 45. Implicit BFS with range-end counting: track the end of the current
/// jump's range and the farthest reach seen; crossing the range end counts
/// one jump and extends the range to that farthest reach. Each range is one
/// BFS level, so jumps are counted per boundary, never per step.
pub fn jump(nums: Vec<i32>) -> i32 {
let mut jumps = 0;
let (mut range_end, mut farthest) = (0, 0);
for i in 0..nums.len() - 1 {
farthest = farthest.max(i + nums[i] as usize);
if i == range_end {
jumps += 1;
range_end = farthest;
}
}
jumps
}
/** LC 45. Implicit BFS by range-end counting: when i crosses the current jump's range end, count one jump and extend the range to the farthest reach seen. */
export function jump(nums: number[]): number {
let jumps = 0;
let rangeEnd = 0; // last index covered by `jumps` jumps
let farthest = 0; // farthest index reachable with one more jump
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === rangeEnd) {
jumps++; // this BFS level is exhausted, start the next one
rangeEnd = farthest;
}
}
return jumps;
}
// LC 45. Implicit BFS: count one jump each time i crosses the current range
// end, then adopt the farthest reach seen inside that level as the new end.
func jump(nums []int) int {
jumps, rangeEnd, farthest := 0, 0, 0
for i := 0; i+1 < len(nums); i++ { // the last index never jumps out
if i+nums[i] > farthest {
farthest = i + nums[i]
}
if i == rangeEnd { // current level exhausted: take one more jump
jumps++
rangeEnd = farthest
}
}
return jumps
}
// LC 45. Implicit BFS: count ONE jump each time i crosses the current range
// end, then adopt the farthest reach seen inside the level as the new end.
func jump(_ nums: [Int]) -> Int {
var jumps = 0, rangeEnd = 0, farthest = 0
for i in 0..<(nums.count - 1) { // the last index never jumps out
farthest = max(farthest, i + nums[i])
if i == rangeEnd { // current level exhausted: take one more jump
jumps += 1
rangeEnd = farthest
}
}
return jumps
}
7. Jump Game VII
Medium · LC 1871
Given a binary string plus minJump and maxJump, decide whether index 0 can reach the last index when each move lands between minJump and maxJump positions ahead and only on '0' characters. Compute dp[i], whether i is reachable, while maintaining a sliding count of reachable indices inside the window [i-maxJump, i-minJump]. The trick is that the window count makes each dp check O(1), turning a quadratic scan into O(n).
def can_reach(s: str, min_jump: int, max_jump: int) -> bool:
"""LC 1871. Jump Game VII.
dp over indices: reachable[i] is true when s[i] is '0' and some
reachable index sits in the launch window [i - max_jump,
i - min_jump]; keep a sliding COUNT of reachable cells inside that
window so each check is O(1) instead of a rescan. The invariant:
in_window always equals the number of reachable indices currently
inside the launch window for i. O(n) time, O(n) space.
"""
n = len(s)
reachable = [False] * n
reachable[0] = True
in_window = 0 # reachable cells inside [i - max_jump, i - min_jump]
for i in range(min_jump, n):
in_window += reachable[i - min_jump] # this index enters the window
if i - max_jump - 1 >= 0:
in_window -= reachable[i - max_jump - 1] # this one slides out
reachable[i] = s[i] == "0" and in_window > 0
return reachable[n - 1]
// LC 1871. dp[i] = index i is reachable, true iff s[i] is '0' and some
// reachable index sits in the jump window [i - maxJump, i - minJump].
// Maintain `window`, a sliding count of reachable indices in that range:
// dp[i - minJump] enters as the right edge arrives and dp[i - maxJump - 1]
// leaves past the left edge, making each membership test O(1) and the whole
// scan O(n) instead of quadratic.
bool canReach(string s, int minJump, int maxJump) {
int n = static_cast<int>(s.size());
if (s[n - 1] != '0') return false;
vector<char> dp(n, 0);
dp[0] = 1;
int window = 0; // reachable indices currently in [i - maxJump, i - minJump]
for (int i = minJump; i < n; ++i) {
window += dp[i - minJump]; // right edge enters
if (i - maxJump - 1 >= 0) window -= dp[i - maxJump - 1]; // left edge leaves
if (s[i] == '0' && window > 0) dp[i] = 1;
}
return dp[n - 1] == 1;
}
/// LC 1871. dp[i] = i lands on '0' and some reachable index sits in the jump
/// window [i - max_jump, i - min_jump]. A sliding count of reachable indices
/// inside that window -- gain i - min_jump entering, drop i - max_jump - 1
/// leaving -- makes each check O(1), turning the quadratic scan into O(n).
pub fn can_reach(s: String, min_jump: i32, max_jump: i32) -> bool {
let b = s.as_bytes();
let n = b.len();
if b[n - 1] != b'0' {
return false;
}
let (min_jump, max_jump) = (min_jump as usize, max_jump as usize);
let mut dp = vec![false; n];
dp[0] = true;
let mut in_window = 0; // reachable indices inside [i - max_jump, i - min_jump]
for i in min_jump..n {
if dp[i - min_jump] {
in_window += 1;
}
if i > max_jump && dp[i - max_jump - 1] {
in_window -= 1;
}
dp[i] = b[i] == b'0' && in_window > 0;
}
dp[n - 1]
}
/** LC 1871. dp[i] = s[i] is '0' and some reachable j lies in [i-maxJump, i-minJump]; a sliding count of reachable indices in that window makes each check O(1). */
export function canReach(s: string, minJump: number, maxJump: number): boolean {
const n = s.length;
if (s[n - 1] !== "0") return false;
const reachable: boolean[] = new Array(n).fill(false);
reachable[0] = true;
let inWindow = 0; // reachable indices currently inside [i - maxJump, i - minJump]
for (let i = minJump; i < n; i++) {
if (reachable[i - minJump]) inWindow++; // right edge slides in
if (i - maxJump - 1 >= 0 && reachable[i - maxJump - 1]) inWindow--; // left edge slides out
reachable[i] = s[i] === "0" && inWindow > 0;
}
return reachable[n - 1];
}
// LC 1871. dp over indices with a sliding COUNT of reachable cells inside the
// launch window [i-maxJump, i-minJump], so each membership test is O(1).
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
if s[n-1] != '0' {
return false
}
dp := make([]bool, n)
dp[0] = true
window := 0 // reachable indices currently in [i - maxJump, i - minJump]
for i := minJump; i < n; i++ {
if dp[i-minJump] {
window++ // right edge enters
}
if i-maxJump-1 >= 0 && dp[i-maxJump-1] {
window-- // left edge leaves
}
dp[i] = s[i] == '0' && window > 0
}
return dp[n-1]
}
// LC 1871. dp over indices with a sliding COUNT of reachable cells inside
// the launch window [i - maxJump, i - minJump], so each check is O(1).
func canReach(_ s: String, _ minJump: Int, _ maxJump: Int) -> Bool {
let chars = Array(s.utf8)
let n = chars.count
var dp = [Bool](repeating: false, count: n)
dp[0] = true
var window = 0 // reachable indices currently in [i - maxJump, i - minJump]
for i in stride(from: minJump, to: n, by: 1) {
if dp[i - minJump] { window += 1 } // right edge enters
if i - maxJump - 1 >= 0 && dp[i - maxJump - 1] { window -= 1 } // left edge leaves
if chars[i] == UInt8(ascii: "0") && window > 0 { dp[i] = true }
}
return dp[n - 1]
}
8. Gas Station
Medium · LC 134
Given gas available at each station and the cost to drive to the next, return the unique starting index that completes the circuit, or -1 if none exists. Check that total gas covers total cost, then sweep with a running tank, restarting the candidate at j+1 whenever the tank goes negative at j. Failing at j eliminates every start between the candidate and j, and a feasible total guarantees the last candidate works.
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
"""LC 134. Gas Station.
If total gas falls short of total cost no start works; otherwise
sweep with a running tank and restart the candidate at j + 1
whenever the tank goes negative at j. WHY failure at j rules out
every start in between: each station k in (candidate, j] was
entered with a NONNEGATIVE tank, so starting at k with an empty
tank carries strictly less gas into every later station and still
dies by j. The invariant: the current candidate has a nonnegative
running tank over the whole stretch behind it, and a feasible
total guarantees the last candidate closes the circle. O(n) time,
O(1) space.
"""
if sum(gas) < sum(cost):
return -1 # the whole circle lacks fuel for any start
tank = 0
candidate = 0
for j in range(len(gas)):
tank += gas[j] - cost[j]
if tank < 0:
candidate = j + 1 # everything from the old candidate to j is dead
tank = 0
return candidate
// LC 134. If total gas is below total cost no start works; otherwise the
// answer is unique. Sweep with a running tank from the current candidate
// start: going negative at i eliminates every start in [start, i], because
// each would arrive at i with even less gas, so restart the candidate at
// i + 1 with an empty tank. A feasible total guarantees the last candidate
// completes the circuit.
int canCompleteCircuit(vector<int> gas, vector<int> cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < static_cast<int>(gas.size()); ++i) {
int delta = gas[i] - cost[i];
total += delta;
tank += delta;
if (tank < 0) { // every start in [start, i] dies here
start = i + 1;
tank = 0;
}
}
return total < 0 ? -1 : start;
}
/// LC 134. If total gas covers total cost a unique answer exists; sweep with
/// a running tank and restart the candidate at i + 1 whenever the tank goes
/// negative at i. Failing at i eliminates every start between the candidate
/// and i (each would arrive with no more gas), so the surviving candidate is
/// the answer.
pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
if gas.iter().sum::<i32>() < cost.iter().sum::<i32>() {
return -1;
}
let (mut tank, mut start) = (0, 0);
for i in 0..gas.len() {
tank += gas[i] - cost[i];
if tank < 0 {
tank = 0;
start = i as i32 + 1;
}
}
start
}
/** LC 134. Feasible iff total gas covers total cost; sweep a running tank and restart the candidate at j+1 whenever it dips negative, since every start in [candidate, j] also dies at j. */
export function canCompleteCircuit(gas: number[], cost: number[]): number {
let total = 0;
let tank = 0;
let start = 0;
for (let i = 0; i < gas.length; i++) {
const delta = gas[i] - cost[i];
total += delta;
tank += delta;
if (tank < 0) {
start = i + 1; // no station in [start, i] can be the answer
tank = 0;
}
}
return total < 0 ? -1 : start; // a feasible total guarantees the last candidate works
}
// LC 134. Restart past every failure: a negative tank at i kills every start
// in [start, i], and a feasible total guarantees the last candidate closes.
func canCompleteCircuit(gas []int, cost []int) int {
total, tank, start := 0, 0, 0
for i := range gas {
delta := gas[i] - cost[i]
total += delta
tank += delta
if tank < 0 { // every start in [start, i] dies here
start = i + 1
tank = 0
}
}
if total < 0 {
return -1 // the whole circle lacks fuel for any start
}
return start
}
// LC 134. Total gas short of total cost means no start; otherwise restart
// the candidate past every failure -- each start in between dies sooner.
func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
var total = 0, tank = 0, start = 0
for i in 0..<gas.count {
let delta = gas[i] - cost[i]
total += delta
tank += delta
if tank < 0 { // every start in [start, i] dies here
start = i + 1
tank = 0
}
}
return total < 0 ? -1 : start
}
9. Hand of Straights
Medium · LC 846
Given an array of card values and a group size, decide whether the cards can be split entirely into groups of consecutive values of exactly that size. Build a count map, then repeatedly take the smallest remaining card and consume one copy of each of the next groupSize consecutive values, failing if any is missing. The greedy is safe because the smallest card can only ever begin a run, never extend one.
def is_n_straight_hand(hand: list[int], group_size: int) -> bool:
"""LC 846. Hand of Straights.
Build a count map, then take cards in ascending order: every copy
of the smallest remaining card must BEGIN a straight (nothing
smaller is left to precede it), so consume that many full runs of
group_size consecutive values at once, failing on any shortage.
The invariant: the smallest remaining card can only ever start a
group, never extend one, so the greedy choice is forced. O(n log n)
time, O(n) space.
"""
if len(hand) % group_size:
return False # the cards cannot even split into equal groups
counts = Counter(hand)
for card in sorted(counts):
runs_starting_here = counts[card]
if runs_starting_here == 0:
continue # already consumed by runs that started lower
for value in range(card, card + group_size):
if counts[value] < runs_starting_here:
return False # some run through `value` is missing a card
counts[value] -= runs_starting_here # consume the whole batch
return True
// LC 846. Ordered count map of card values. The invariant making the greedy
// safe: the smallest remaining card can only ever BEGIN a run, never extend
// one, since nothing smaller is left to precede it. So repeatedly take the
// map's first key and consume one copy of each of the groupSize consecutive
// values, failing the moment a needed value is missing.
bool isNStraightHand(vector<int> hand, int groupSize) {
if (static_cast<int>(hand.size()) % groupSize != 0) return false;
map<int, int> count;
for (int card : hand) ++count[card];
while (!count.empty()) {
int start = count.begin()->first; // smallest remaining must start a run
for (int v = start; v < start + groupSize; ++v) {
auto it = count.find(v);
if (it == count.end()) return false; // run has a hole
if (--it->second == 0) count.erase(it);
}
}
return true;
}
/// LC 846. BTreeMap count of cards; repeatedly take the smallest remaining
/// value and consume one copy of each of the next group_size consecutive
/// values. The greedy is safe because the smallest card can only ever BEGIN a
/// run, never extend one, so it has exactly one possible role.
pub fn is_n_straight_hand(hand: Vec<i32>, group_size: i32) -> bool {
if hand.len() % group_size as usize != 0 {
return false;
}
let mut counts: BTreeMap<i32, i32> = BTreeMap::new();
for card in hand {
*counts.entry(card).or_insert(0) += 1;
}
while let Some((&smallest, _)) = counts.iter().next() {
for v in smallest..smallest + group_size {
match counts.get_mut(&v) {
Some(cnt) => {
*cnt -= 1;
if *cnt == 0 {
counts.remove(&v);
}
}
None => return false, // run starting at smallest has a gap
}
}
}
true
}
/** LC 846. Count map + sorted distinct values: the smallest remaining card can only BEGIN a run, never extend one, so consume one copy of each of the next groupSize consecutive values. */
export function isNStraightHand(hand: number[], groupSize: number): boolean {
if (hand.length % groupSize !== 0) return false;
const counts = new Map<number, number>();
for (const card of hand) counts.set(card, (counts.get(card) ?? 0) + 1);
const values = [...counts.keys()].sort((a, b) => a - b);
for (const value of values) {
const need = counts.get(value)!; // every remaining copy must start its own group
if (need === 0) continue;
for (let card = value; card < value + groupSize; card++) {
const have = counts.get(card) ?? 0;
if (have < need) return false; // a gap strands the smallest card
counts.set(card, have - need);
}
}
return true;
}
// LC 846. Always extend from the smallest remaining card: it can only BEGIN a
// straight, so consume whole batches of groupSize consecutive values at once.
func isNStraightHand(hand []int, groupSize int) bool {
if len(hand)%groupSize != 0 {
return false
}
counts := make(map[int]int)
for _, card := range hand {
counts[card]++
}
cards := make([]int, 0, len(counts))
for card := range counts {
cards = append(cards, card)
}
sort.Ints(cards)
for _, card := range cards {
runs := counts[card] // every copy of the smallest must start a run
if runs == 0 {
continue // already consumed by runs that started lower
}
for v := card; v < card+groupSize; v++ {
if counts[v] < runs {
return false // some run through v is missing a card
}
counts[v] -= runs
}
}
return true
}
// LC 846. The smallest remaining card can only BEGIN a straight, never extend
// one, so consume whole batches of groupSize consecutive values upward.
func isNStraightHand(_ hand: [Int], _ groupSize: Int) -> Bool {
if hand.count % groupSize != 0 { return false }
var counts: [Int: Int] = [:]
for card in hand { counts[card, default: 0] += 1 }
for card in counts.keys.sorted() {
let runsStartingHere = counts[card] ?? 0
if runsStartingHere == 0 { continue } // consumed by runs starting lower
for value in card..<(card + groupSize) {
let have = counts[value] ?? 0
if have < runsStartingHere { return false } // a run has a hole
counts[value] = have - runsStartingHere // consume the whole batch
}
}
return true
}
10. Dota2 Senate
Medium · LC 649
Given a string of 'R' and 'D' senators voting in rounds, where each active senator can permanently ban one opponent, return which party eventually announces victory. Keep two queues of senator indices, repeatedly pop the front of each, let the smaller index ban the other, and re-enqueue the winner at index plus n to fight in the next round. The trick is that earlier position wins each duel, and adding n preserves correct round ordering.
def predict_party_victory(senate: str) -> str:
"""LC 649. Dota2 Senate.
Keep one queue of senator indices per party; each duel pops both
fronts, the smaller index acts first and bans the other, and the
winner re-enqueues at index + n. WHY the + n trick works: the
survivor has already acted this round, so shifting by n files it
AFTER every senator still waiting in the current round while
preserving order inside each round -- one widened index space
replaces explicit round bookkeeping. The invariant: the two queue
fronts are always the next two senators eligible to act. O(n) per
round, O(n) space.
"""
n = len(senate)
radiant = deque(i for i, party in enumerate(senate) if party == "R")
dire = deque(i for i, party in enumerate(senate) if party == "D")
while radiant and dire:
r, d = radiant.popleft(), dire.popleft()
if r < d:
radiant.append(r + n) # r acts first: ban d, fight next round
else:
dire.append(d + n)
return "Radiant" if radiant else "Dire"
// LC 649. Two queues of senator indices, one per party. Each round the two
// fronts duel and the SMALLER index acts first, banning the other; the winner
// re-enters its queue at index + n, which preserves round ordering by placing
// every survivor behind all senators still waiting in the current round. A
// party announces victory when the opposing queue empties.
string predictPartyVictory(string senate) {
int n = static_cast<int>(senate.size());
queue<int> radiant, dire;
for (int i = 0; i < n; ++i)
(senate[i] == 'R' ? radiant : dire).push(i);
while (!radiant.empty() && !dire.empty()) {
int r = radiant.front();
radiant.pop();
int d = dire.front();
dire.pop();
if (r < d)
radiant.push(r + n); // R acts first and bans D's front
else
dire.push(d + n);
}
return radiant.empty() ? "Dire" : "Radiant";
}
/// LC 649. Two VecDeques of senator indices; pop one from each, the smaller
/// index bans the other, and the winner re-enqueues at index + n. Earlier
/// position always wins the duel (it acts first), and adding n keeps the
/// winner ordered correctly within the NEXT round.
pub fn predict_party_victory(senate: String) -> String {
let n = senate.len();
let mut radiant: VecDeque<usize> = VecDeque::new();
let mut dire: VecDeque<usize> = VecDeque::new();
for (i, c) in senate.bytes().enumerate() {
if c == b'R' {
radiant.push_back(i);
} else {
dire.push_back(i);
}
}
while !radiant.is_empty() && !dire.is_empty() {
let r = radiant.pop_front().unwrap();
let d = dire.pop_front().unwrap();
if r < d {
radiant.push_back(r + n);
} else {
dire.push_back(d + n);
}
}
if radiant.is_empty() { "Dire" } else { "Radiant" }.to_string()
}
/** LC 649. Two index queues; each duel the smaller index bans the other, and the winner re-enqueues at index + n, which preserves correct ordering for the next round. */
export function predictPartyVictory(senate: string): string {
const n = senate.length;
const radiant: number[] = [];
const dire: number[] = [];
for (let i = 0; i < n; i++) {
(senate[i] === "R" ? radiant : dire).push(i);
}
let r = 0; // queue heads, so dequeue is O(1) instead of Array#shift's O(n)
let d = 0;
while (r < radiant.length && d < dire.length) {
const ri = radiant[r++];
const di = dire[d++];
if (ri < di) radiant.push(ri + n); // the earlier senator acts first and bans the other
else dire.push(di + n);
}
return r < radiant.length ? "Radiant" : "Dire";
}
// LC 649. Duel queues: the smaller front index acts first and bans the other;
// the winner re-enters at index + n, filing it behind the current round.
func predictPartyVictory(senate string) string {
n := len(senate)
var radiant, dire []int
for i := 0; i < n; i++ {
if senate[i] == 'R' {
radiant = append(radiant, i)
} else {
dire = append(dire, i)
}
}
for len(radiant) > 0 && len(dire) > 0 {
r, d := radiant[0], dire[0]
radiant, dire = radiant[1:], dire[1:]
if r < d {
radiant = append(radiant, r+n) // R acts first and bans D's front
} else {
dire = append(dire, d+n)
}
}
if len(radiant) > 0 {
return "Radiant"
}
return "Dire"
}
// LC 649. Duel queues of senator indices: the smaller index acts first and
// bans the other; the winner re-enters at index + n, preserving round order.
func predictPartyVictory(_ senate: String) -> String {
let n = senate.count
var radiant: [Int] = [], dire: [Int] = []
for (i, party) in senate.enumerated() {
if party == "R" { radiant.append(i) } else { dire.append(i) }
}
var rHead = 0, dHead = 0 // array-backed queues: pop by advancing a head
while rHead < radiant.count && dHead < dire.count {
let r = radiant[rHead]
rHead += 1
let d = dire[dHead]
dHead += 1
if r < d {
radiant.append(r + n) // R acts first and bans D's front
} else {
dire.append(d + n)
}
}
return rHead < radiant.count ? "Radiant" : "Dire"
}
11. Merge Triplets to Form Target Triplet
Medium · LC 1899
Given a list of triplets and a target triplet, decide whether repeatedly taking elementwise maxima of chosen triplets can produce the target exactly. Filter out any triplet with a coordinate exceeding the target, then check whether the surviving triplets together hit each target coordinate, effectively taking their elementwise maximum. The insight is that a triplet that nowhere exceeds the target is always safe to merge, so only per-coordinate coverage matters.
def merge_triplets(triplets: list[list[int]], target: list[int]) -> bool:
"""LC 1899. Merge Triplets to Form Target Triplet.
Merging takes elementwise maxima, so any triplet with a coordinate
above the target poisons every merge it joins -- discard those and
OR together which target coordinates the survivors hit exactly.
The invariant: a triplet that nowhere exceeds the target is always
safe to merge in, so only per-coordinate coverage matters. O(n)
time, O(1) space.
"""
matched = [False, False, False]
for triplet in triplets:
if all(value <= bound for value, bound in zip(triplet, target)):
for k in range(3):
matched[k] = matched[k] or triplet[k] == target[k]
return all(matched)
// LC 1899. Elementwise max only ever raises coordinates, so any triplet with
// a coordinate above the target can never be used, while every triplet that
// is <= the target everywhere is always safe to merge in. The target is
// formable iff the safe triplets jointly hit all three target coordinates
// exactly -- their collective elementwise max is then the target.
bool mergeTriplets(vector<vector<int>> triplets, vector<int> target) {
bool hit[3] = {false, false, false};
for (const vector<int>& t : triplets) {
if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;
for (int k = 0; k < 3; ++k)
if (t[k] == target[k]) hit[k] = true; // safe triplet covers coordinate k
}
return hit[0] && hit[1] && hit[2];
}
/// LC 1899. A triplet that nowhere exceeds the target is always safe to
/// merge, so filter to those and check that the survivors hit each target
/// coordinate somewhere -- merging all survivors takes the elementwise max,
/// and only per-coordinate coverage matters.
pub fn merge_triplets(triplets: Vec<Vec<i32>>, target: Vec<i32>) -> bool {
let mut hit = [false; 3];
for t in &triplets {
if t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2] {
for k in 0..3 {
if t[k] == target[k] {
hit[k] = true;
}
}
}
}
hit.iter().all(|&h| h)
}
/** LC 1899. A triplet that nowhere exceeds the target is always safe to merge, so discard the rest and check each target coordinate is hit exactly by some survivor. */
export function mergeTriplets(triplets: number[][], target: number[]): boolean {
const hit: boolean[] = [false, false, false]; // target coordinate achieved by a safe triplet
for (const [a, b, c] of triplets) {
if (a > target[0] || b > target[1] || c > target[2]) continue; // would overshoot somewhere
if (a === target[0]) hit[0] = true;
if (b === target[1]) hit[1] = true;
if (c === target[2]) hit[2] = true;
}
return hit[0] && hit[1] && hit[2];
}
// LC 1899. Merging takes elementwise maxima, so discard any triplet exceeding
// the target anywhere and OR which coordinates the survivors hit exactly.
func mergeTriplets(triplets [][]int, target []int) bool {
var hit [3]bool
for _, t := range triplets {
if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] {
continue // poisoned: it would overshoot any merge it joins
}
for k := 0; k < 3; k++ {
if t[k] == target[k] {
hit[k] = true
}
}
}
return hit[0] && hit[1] && hit[2]
}
// LC 1899. Merging takes elementwise maxima, so discard any triplet that
// exceeds the target anywhere and OR which coordinates the rest hit exactly.
func mergeTriplets(_ triplets: [[Int]], _ target: [Int]) -> Bool {
var hit = [false, false, false]
for t in triplets {
if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] { continue }
for k in 0..<3 where t[k] == target[k] {
hit[k] = true // safe triplet covers coordinate k
}
}
return hit[0] && hit[1] && hit[2]
}
12. Partition Labels
Medium · LC 763
Given a string, split it into as many parts as possible so each letter appears in one part only, returning the part sizes. Record the last occurrence index of every letter, then sweep while extending the current partition's boundary to the last occurrence of each letter seen, closing the part when i reaches the boundary. The invariant is that the boundary is the farthest last occurrence inside the part, making the close point safe.
def partition_labels(s: str) -> list[int]:
"""LC 763. Partition Labels.
Record each letter's last occurrence, then sweep while pushing the
current part's boundary out to the last occurrence of every letter
seen; when i reaches the boundary, seal the part. The invariant:
the boundary is the farthest last occurrence of any letter inside
the part, so closing there strands no letter outside it. O(n)
time, O(1) space (the alphabet is fixed).
"""
last_seen = {ch: i for i, ch in enumerate(s)} # later writes win
sizes: list[int] = []
part_start = boundary = 0
for i, ch in enumerate(s):
boundary = max(boundary, last_seen[ch]) # ch drags the part out
if i == boundary:
sizes.append(i - part_start + 1)
part_start = i + 1
return sizes
// LC 763. Record each letter's last occurrence, then sweep extending the
// current part's boundary to the farthest last occurrence of any letter seen
// inside it. The invariant: when i reaches the boundary, no letter in the
// part occurs again later, so closing there is safe and closing earlier is
// impossible -- which is exactly what maximizes the number of parts.
vector<int> partitionLabels(string s) {
int n = static_cast<int>(s.size());
int last[26] = {0};
for (int i = 0; i < n; ++i) last[s[i] - 'a'] = i;
vector<int> sizes;
int boundary = 0, start = 0;
for (int i = 0; i < n; ++i) {
boundary = max(boundary, last[s[i] - 'a']);
if (i == boundary) { // nothing inside the part appears later
sizes.push_back(i - start + 1);
start = i + 1;
}
}
return sizes;
}
/// LC 763. Record each letter's last occurrence, then sweep extending the
/// current part's boundary to the last occurrence of every letter seen;
/// close the part when i reaches the boundary. The invariant: the boundary
/// is the farthest last occurrence inside the part, so closing there can
/// never strand a letter across parts.
pub fn partition_labels(s: String) -> Vec<i32> {
let b = s.as_bytes();
let mut last = [0usize; 26];
for (i, &c) in b.iter().enumerate() {
last[(c - b'a') as usize] = i;
}
let mut sizes = Vec::new();
let (mut start, mut boundary) = (0usize, 0usize);
for (i, &c) in b.iter().enumerate() {
boundary = boundary.max(last[(c - b'a') as usize]);
if i == boundary {
sizes.push((i - start + 1) as i32);
start = i + 1;
}
}
sizes
}
/** LC 763. Record each letter's LAST occurrence, then sweep extending the part's boundary to the farthest last occurrence seen; i reaching the boundary means nothing inside appears later. */
export function partitionLabels(s: string): number[] {
const last = new Map<string, number>();
for (let i = 0; i < s.length; i++) last.set(s[i], i);
const sizes: number[] = [];
let start = 0;
let boundary = 0; // farthest last-occurrence among letters in the current part
for (let i = 0; i < s.length; i++) {
boundary = Math.max(boundary, last.get(s[i])!);
if (i === boundary) {
sizes.push(i - start + 1); // safe close: every letter here is fully contained
start = i + 1;
}
}
return sizes;
}
// LC 763. Last-occurrence boundary: drag the part's edge out to the last
// occurrence of every letter seen; sealing where i meets it strands nothing.
func partitionLabels(s string) []int {
var last [26]int
for i := 0; i < len(s); i++ {
last[s[i]-'a'] = i
}
var sizes []int
boundary, start := 0, 0
for i := 0; i < len(s); i++ {
if last[s[i]-'a'] > boundary {
boundary = last[s[i]-'a']
}
if i == boundary { // nothing inside the part appears later
sizes = append(sizes, i-start+1)
start = i + 1
}
}
return sizes
}
// LC 763. Push the part boundary out to each letter's last occurrence; when
// i reaches the boundary, no letter inside appears later, so seal the part.
func partitionLabels(_ s: String) -> [Int] {
let chars = Array(s.utf8)
let n = chars.count
var last = [Int](repeating: 0, count: 26)
for i in 0..<n { last[Int(chars[i] - UInt8(ascii: "a"))] = i }
var sizes: [Int] = []
var boundary = 0, start = 0
for i in 0..<n {
boundary = max(boundary, last[Int(chars[i] - UInt8(ascii: "a"))])
if i == boundary { // nothing inside the part appears later
sizes.append(i - start + 1)
start = i + 1
}
}
return sizes
}
13. Valid Parenthesis String
Medium · LC 678
Given a string of '(', ')', and '*' where star can act as an open, a close, or nothing, decide whether it can form a valid parenthesis string. Sweep once tracking a range [lo, hi] of possible open-bracket counts, where '(' increments both, ')' decrements both, and '*' decrements lo and increments hi. Clamp lo at zero, fail immediately if hi drops below zero, and accept at the end only when lo is zero.
def check_valid_string(s: str) -> bool:
"""LC 678. Valid Parenthesis String.
Sweep once tracking [lo, hi], the range of possible unmatched-open
counts over all star choices: '(' raises both, ')' lowers both,
and '*' lowers lo while raising hi. Fail the moment hi drops below
zero and accept only when lo can finish at zero. The invariant:
every integer in [lo, hi] is an achievable open count for some
assignment of the stars seen so far. O(n) time, O(1) space.
"""
lo = hi = 0 # fewest and most unmatched '(' possible so far
for ch in s:
if ch == "(":
lo, hi = lo + 1, hi + 1
elif ch == ")":
lo, hi = lo - 1, hi - 1
else:
lo, hi = lo - 1, hi + 1 # '*' may act as ')', '(' or nothing
if hi < 0:
return False # too many ')' even with every star as '('
# clamp lo at 0: a negative lo only means some stars chosen as
# ')' should be blanks instead -- a real count cannot go below 0
lo = max(lo, 0)
return lo == 0 # some star assignment closes every bracket
// LC 678. Sweep tracking [lo, hi], the range of POSSIBLE open-bracket counts:
// '(' raises both, ')' lowers both, '*' widens one each way. Clamp lo at 0 --
// a star never has to act as a close that would strand the count negative --
// and fail the moment hi < 0, since even all-open stars cannot rescue excess
// ')'. Every count in [lo, hi] stays achievable, so the string is valid iff
// lo == 0 at the end.
bool checkValidString(string s) {
int lo = 0, hi = 0;
for (char c : s) {
if (c == '(') {
++lo;
++hi;
} else if (c == ')') {
--lo;
--hi;
} else { // '*': close, open, or empty
--lo;
++hi;
}
if (hi < 0) return false; // unmatched ')' beyond repair
lo = max(lo, 0); // a '*' is never forced to over-close
}
return lo == 0;
}
/// LC 678. Track the open range [lo, hi] of possible unmatched-'(' counts:
/// '(' bumps both, ')' drops both, '*' drops lo and bumps hi. Clamp lo at 0
/// (a star never has to close what was never open), fail the instant hi goes
/// negative, and accept only when lo reaches exactly 0 at the end.
pub fn check_valid_string(s: String) -> bool {
let (mut lo, mut hi) = (0i32, 0i32);
for c in s.bytes() {
match c {
b'(' => {
lo += 1;
hi += 1;
}
b')' => {
lo -= 1;
hi -= 1;
}
_ => {
lo -= 1;
hi += 1;
}
}
if hi < 0 {
return false; // too many ')' even with every '*' as '('
}
lo = lo.max(0);
}
lo == 0
}
/** LC 678. Track the OPEN-count range [lo, hi]: '(' bumps both, ')' drops both, '*' widens both ways; clamp lo at 0, fail when hi < 0, accept iff lo can land on 0. */
export function checkValidString(s: string): boolean {
let lo = 0; // fewest unmatched opens possible so far
let hi = 0; // most unmatched opens possible so far
for (const ch of s) {
if (ch === "(") {
lo++;
hi++;
} else if (ch === ")") {
lo--;
hi--;
} else {
lo--; // star as ')'
hi++; // star as '('
}
if (hi < 0) return false; // too many ')' even with every star as '('
lo = Math.max(lo, 0); // negative open counts are unreachable states, not credit
}
return lo === 0;
}
// LC 678. Track [lo, hi], the range of possible open counts over all star
// choices; fail the moment hi sinks below zero, accept when lo ends at zero.
func checkValidString(s string) bool {
lo, hi := 0, 0
for i := 0; i < len(s); i++ {
switch s[i] {
case '(':
lo++
hi++
case ')':
lo--
hi--
default: // '*': close, open, or empty
lo--
hi++
}
if hi < 0 {
return false // unmatched ')' beyond repair
}
if lo < 0 {
lo = 0 // a '*' is never forced to over-close
}
}
return lo == 0
}
// LC 678. Track [lo, hi], the range of possible open counts over all star
// choices: fail the moment hi < 0, clamp lo at 0, accept iff lo ends at 0.
func checkValidString(_ s: String) -> Bool {
var lo = 0, hi = 0
for c in s {
if c == "(" {
lo += 1
hi += 1
} else if c == ")" {
lo -= 1
hi -= 1
} else { // '*': close, open, or empty
lo -= 1
hi += 1
}
if hi < 0 { return false } // unmatched ')' beyond repair
lo = max(lo, 0) // a '*' is never forced to over-close
}
return lo == 0
}
14. Candy
Hard · LC 135
Given children's ratings in a line, distribute the minimum candies so each child gets at least one and any child rated above an adjacent neighbor gets more. Sweep left to right giving each rising rating one more candy than its left neighbor, then sweep right to left applying the same rule against the right neighbor. The trick is taking the maximum of the two sweep values rather than overwriting, which satisfies both directional constraints.
def candy(ratings: list[int]) -> int:
"""LC 135. Candy.
Two sweeps over a base of one candy per child: left to right give
each rising rating one more than its left neighbor, then right to
left apply the same rule against the right neighbor, taking the
MAX with the first sweep's value rather than overwriting. WHY one
sweep cannot work: a single pass sees only one neighbor, and a
long descent ahead (5,4,3,2,1) forces raises that propagate
backward, against the sweep direction; the max keeps both
directional constraints satisfied at once. The invariant: after
both sweeps every child out-candies each lower-rated neighbor
using the fewest candies possible. O(n) time, O(n) space.
"""
n = len(ratings)
candies = [1] * n # everyone gets at least one
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
# max, not overwrite: keep the left-neighbor win as well
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)
// LC 135. Two sweeps over a baseline of one candy each. Left to right: a
// rating above its left neighbor gets one more candy than that neighbor.
// Right to left: the same rule against the right neighbor, taking the MAX
// with the first sweep's value rather than overwriting, so both directional
// constraints hold at once. The sum is minimal because every candy above one
// is forced by some chain of strict increases.
int candy(vector<int> ratings) {
int n = static_cast<int>(ratings.size());
vector<int> candies(n, 1);
for (int i = 1; i < n; ++i)
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
int total = candies[n - 1];
for (int i = n - 2; i >= 0; --i) {
if (ratings[i] > ratings[i + 1]) candies[i] = max(candies[i], candies[i + 1] + 1);
total += candies[i];
}
return total;
}
/// LC 135. Two sweeps from one candy each: left-to-right gives a rising
/// rating one more than its left neighbor, right-to-left applies the same
/// rule against the right neighbor. The trick is taking the MAX of the two
/// sweep values instead of overwriting, which satisfies both directional
/// constraints at once for the minimum total.
pub fn candy(ratings: Vec<i32>) -> i32 {
let n = ratings.len();
let mut candies = vec![1i32; n];
for i in 1..n {
if ratings[i] > ratings[i - 1] {
candies[i] = candies[i - 1] + 1;
}
}
for i in (0..n - 1).rev() {
if ratings[i] > ratings[i + 1] {
candies[i] = candies[i].max(candies[i + 1] + 1);
}
}
candies.iter().sum()
}
/** LC 135. Two sweeps from 1 each: left-to-right satisfies rising-over-left, right-to-left satisfies rising-over-right; take the MAX of the two values so both constraints hold. */
export function candy(ratings: number[]): number {
const n = ratings.length;
const candies: number[] = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
let total = candies[n - 1];
for (let i = n - 2; i >= 0; i--) {
// max, not overwrite: the left sweep's value may already exceed right + 1
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
total += candies[i];
}
return total;
}
// LC 135. Two sweeps over a base of one candy each: raise rising ratings
// against the left neighbor, then the right, taking the MAX of both passes.
func candy(ratings []int) int {
n := len(ratings)
candies := make([]int, n)
for i := range candies {
candies[i] = 1
}
for i := 1; i < n; i++ {
if ratings[i] > ratings[i-1] {
candies[i] = candies[i-1] + 1
}
}
total := candies[n-1]
for i := n - 2; i >= 0; i-- {
if ratings[i] > ratings[i+1] && candies[i+1]+1 > candies[i] {
candies[i] = candies[i+1] + 1 // max, not overwrite
}
total += candies[i]
}
return total
}
// LC 135. Two sweeps over a base of one candy each: beat the left neighbor
// going right, then the right neighbor going left, taking the MAX of both.
func candy(_ ratings: [Int]) -> Int {
let n = ratings.count
var candies = [Int](repeating: 1, count: n)
for i in 1..<n where ratings[i] > ratings[i - 1] {
candies[i] = candies[i - 1] + 1
}
var total = candies[n - 1]
for i in stride(from: n - 2, through: 0, by: -1) {
if ratings[i] > ratings[i + 1] {
candies[i] = max(candies[i], candies[i + 1] + 1) // max, not overwrite
}
total += candies[i]
}
return total
}