Skip to main content
CodePeet

CodePeet 700 Complete DSA Sheet

Greedy on Reach and Balance

Editorial

How far can you get?

From each square of an array you may jump forward up to as many squares as its number says. Can you reach the last square? The first way anyone writes marks, from every square already reached, every square it can jump to. The greedy way carries one number: the farthest square reachable so far. Both, on 4,000 squares where every jump is long and the square halfway is a 0:

import time

n = 4000
nums = [n - i for i in range(n)]               # from square i you may jump up to nums[i] squares
nums[n // 2] = 0                               # a 0 halfway, which the long jumps fly over

t = time.perf_counter()
can, marks = [False] * n, 0                    # mark every square each reachable square reaches
can[0] = True
for i in range(n):
    if can[i]:
        for j in range(i + 1, min(n, i + nums[i] + 1)):
            can[j] = True
            marks += 1
mark_ms = round((time.perf_counter() - t) * 1000)

t = time.perf_counter()
reach = steps = 0                              # carry only the farthest square reachable so far
for i in range(n):
    if i > reach:
        break
    steps += 1
    reach = max(reach, i + nums[i])
reach_ms = round((time.perf_counter() - t) * 1000)
print(f"marking what each square reaches: {marks} marks, the last square reached: {can[-1]}, {mark_ms} ms")
print(f"the farthest reach: {steps} steps, the last square reached: {reach >= n - 1}, {reach_ms} ms")

# marking what each square reaches: 7996001 marks, the last square reached: True, 925 ms
# the farthest reach: 4000 steps, the last square reached: True, 1 ms
public class Main {
    public static void main(String[] args) {
        int n = 4000;
        int[] nums = new int[n];                     // from square i you may jump up to nums[i] squares
        for (int i = 0; i < n; i++) nums[i] = n - i;
        nums[n / 2] = 0;                             // a 0 halfway, which the long jumps fly over

        long t = System.nanoTime();
        boolean[] can = new boolean[n];              // mark every square each reachable square reaches
        can[0] = true;
        long marks = 0;
        for (int i = 0; i < n; i++) {
            if (!can[i]) continue;
            for (int j = i + 1; j < Math.min(n, i + nums[i] + 1); j++) {
                can[j] = true;
                marks++;
            }
        }
        long markMs = Math.round((System.nanoTime() - t) / 1e6);

        t = System.nanoTime();
        int reach = 0, steps = 0;                    // carry only the farthest square reachable so far
        for (int i = 0; i < n; i++) {
            if (i > reach) break;
            steps++;
            reach = Math.max(reach, i + nums[i]);
        }
        long reachMs = Math.round((System.nanoTime() - t) / 1e6);
        System.out.println("marking what each square reaches: " + marks + " marks, the last square reached: "
                + (can[n - 1] ? "True" : "False") + ", " + markMs + " ms");
        System.out.println("the farthest reach: " + steps + " steps, the last square reached: "
                + (reach >= n - 1 ? "True" : "False") + ", " + reachMs + " ms");
    }
}

// marking what each square reaches: 7996001 marks, the last square reached: True, 26 ms
// the farthest reach: 4000 steps, the last square reached: True, 0 ms
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 4000;
    vector<int> nums(n);                                 // from square i you may jump up to nums[i] squares
    for (int i = 0; i < n; i++) nums[i] = n - i;
    nums[n / 2] = 0;                                     // a 0 halfway, which the long jumps fly over

    auto t = chrono::steady_clock::now();
    vector<bool> can(n, false);                          // mark every square each reachable square reaches
    can[0] = true;
    long long marks = 0;
    for (int i = 0; i < n; i++) {
        if (!can[i]) continue;
        for (int j = i + 1; j < min(n, i + nums[i] + 1); j++) {
            can[j] = true;
            marks++;
        }
    }
    long long markMs = llround(chrono::duration<double, milli>(chrono::steady_clock::now() - t).count());

    t = chrono::steady_clock::now();
    int reach = 0, steps = 0;                            // carry only the farthest square reachable so far
    for (int i = 0; i < n; i++) {
        if (i > reach) break;
        steps++;
        reach = max(reach, i + nums[i]);
    }
    long long reachMs = llround(chrono::duration<double, milli>(chrono::steady_clock::now() - t).count());
    cout << "marking what each square reaches: " << marks << " marks, the last square reached: "
         << (can[n - 1] ? "True" : "False") << ", " << markMs << " ms\n";
    cout << "the farthest reach: " << steps << " steps, the last square reached: " << (reach >= n - 1 ? "True" : "False")
         << ", " << reachMs << " ms\n";
}

// marking what each square reaches: 7996001 marks, the last square reached: True, 11 ms
// the farthest reach: 4000 steps, the last square reached: True, 0 ms
const n = 4000;
const nums = Array.from({ length: n }, (_, i) => n - i);   // from square i you may jump up to nums[i] squares
nums[n / 2] = 0;                                  // a 0 halfway, which the long jumps fly over

let t = performance.now();
const can = new Array(n).fill(false);             // mark every square each reachable square reaches
can[0] = true;
let marks = 0;
for (let i = 0; i < n; i++) {
    if (!can[i]) continue;
    for (let j = i + 1; j < Math.min(n, i + nums[i] + 1); j++) {
        can[j] = true;
        marks++;
    }
}
const markMs = Math.round(performance.now() - t);

t = performance.now();
let reach = 0, steps = 0;                         // carry only the farthest square reachable so far
for (let i = 0; i < n; i++) {
    if (i > reach) break;
    steps++;
    reach = Math.max(reach, i + nums[i]);
}
const reachMs = Math.round(performance.now() - t);
console.log(`marking what each square reaches: ${marks} marks, the last square reached: ${can[n - 1] ? "True" : "False"}, ${markMs} ms`);
console.log(`the farthest reach: ${steps} steps, the last square reached: ${reach >= n - 1 ? "True" : "False"}, ${reachMs} ms`);

// marking what each square reaches: 7996001 marks, the last square reached: True, 34 ms
// the farthest reach: 4000 steps, the last square reached: True, 0 ms
const n = 4000;
const nums: number[] = Array.from({ length: n }, (_, i) => n - i);   // from square i you may jump up to nums[i] squares
nums[n / 2] = 0;                                  // a 0 halfway, which the long jumps fly over

let t = performance.now();
const can: boolean[] = new Array(n).fill(false);  // mark every square each reachable square reaches
can[0] = true;
let marks = 0;
for (let i = 0; i < n; i++) {
    if (!can[i]) continue;
    for (let j = i + 1; j < Math.min(n, i + nums[i] + 1); j++) {
        can[j] = true;
        marks++;
    }
}
const markMs = Math.round(performance.now() - t);

t = performance.now();
let reach = 0, steps = 0;                         // carry only the farthest square reachable so far
for (let i = 0; i < n; i++) {
    if (i > reach) break;
    steps++;
    reach = Math.max(reach, i + nums[i]);
}
const reachMs = Math.round(performance.now() - t);
console.log(`marking what each square reaches: ${marks} marks, the last square reached: ${can[n - 1] ? "True" : "False"}, ${markMs} ms`);
console.log(`the farthest reach: ${steps} steps, the last square reached: ${reach >= n - 1 ? "True" : "False"}, ${reachMs} ms`);

// marking what each square reaches: 7996001 marks, the last square reached: True, 34 ms
// the farthest reach: 4000 steps, the last square reached: True, 0 ms
using System;
using System.Diagnostics;

class Program {
    static void Main() {
        int n = 4000;
        var nums = new int[n];                       // from square i you may jump up to nums[i] squares
        for (int i = 0; i < n; i++) nums[i] = n - i;
        nums[n / 2] = 0;                             // a 0 halfway, which the long jumps fly over

        var sw = Stopwatch.StartNew();
        var can = new bool[n];                       // mark every square each reachable square reaches
        can[0] = true;
        long marks = 0;
        for (int i = 0; i < n; i++) {
            if (!can[i]) continue;
            for (int j = i + 1; j < Math.Min(n, i + nums[i] + 1); j++) {
                can[j] = true;
                marks++;
            }
        }
        long markMs = (long) Math.Round(sw.Elapsed.TotalMilliseconds);

        sw.Restart();
        int reach = 0, steps = 0;                    // carry only the farthest square reachable so far
        for (int i = 0; i < n; i++) {
            if (i > reach) break;
            steps++;
            reach = Math.Max(reach, i + nums[i]);
        }
        long reachMs = (long) Math.Round(sw.Elapsed.TotalMilliseconds);
        Console.WriteLine($"marking what each square reaches: {marks} marks, the last square reached: {(can[n - 1] ? "True" : "False")}, {markMs} ms");
        Console.WriteLine($"the farthest reach: {steps} steps, the last square reached: {(reach >= n - 1 ? "True" : "False")}, {reachMs} ms");
    }
}

// marking what each square reaches: 7996001 marks, the last square reached: True, 11 ms
// the farthest reach: 4000 steps, the last square reached: True, 0 ms
package main

import (
	"fmt"
	"time"
)

func word(b bool) string {
	if b {
		return "True"
	}
	return "False"
}

func main() {
	n := 4000
	nums := make([]int, n) // from square i you may jump up to nums[i] squares
	for i := range nums {
		nums[i] = n - i
	}
	nums[n/2] = 0 // a 0 halfway, which the long jumps fly over

	t := time.Now()
	can := make([]bool, n) // mark every square each reachable square reaches
	can[0] = true
	marks := 0
	for i := 0; i < n; i++ {
		if !can[i] {
			continue
		}
		for j := i + 1; j < n && j <= i+nums[i]; j++ {
			can[j] = true
			marks++
		}
	}
	markMs := time.Since(t).Round(time.Millisecond).Milliseconds()

	t = time.Now()
	reach, steps := 0, 0 // carry only the farthest square reachable so far
	for i := 0; i < n; i++ {
		if i > reach {
			break
		}
		steps++
		if i+nums[i] > reach {
			reach = i + nums[i]
		}
	}
	reachMs := time.Since(t).Round(time.Millisecond).Milliseconds()
	fmt.Printf("marking what each square reaches: %d marks, the last square reached: %s, %d ms\n", marks, word(can[n-1]), markMs)
	fmt.Printf("the farthest reach: %d steps, the last square reached: %s, %d ms\n", steps, word(reach >= n-1), reachMs)
}

// marking what each square reaches: 7996001 marks, the last square reached: True, 6 ms
// the farthest reach: 4000 steps, the last square reached: True, 0 ms

Both reach the last square. Marking made 7,996,001 marks; the farthest reach took 4,000 steps, one a square. In Python that was 925 ms against 1 ms. None of the marks was needed: if a square can be reached, so can every square before it, so the reachable squares are always a stretch from the start, and one number says where it ends.

Two of the lesson's arrays as rows of squares, each square's number inside it and the farthest reach so far written under it. 1 3 0 0 2 0 1: the reach reads 1, 4, 4, 4, 6, 6 and 7; the squares that move it, the 1, the 3 and the 2 at square 4, and the last 1, are green, with arcs from the 1, the 3 and the 2 to where they reach, and the row ends ticked. 2 1 0 3: the reach reads 2, 2 and 2, and the 3 at square 3 is dashed in red, crossed, past the reach of 2. Under them two cards for the run on 4,000 squares: marking every square reached made 7,996,001 marks; the farthest reach took 4,000 steps, one a square. Focal line: one number says how far the jumps can get. Title: the farthest reach.

The farthest reach

Jump Game asks just that. Walk the squares in order: a square past the farthest reach can't be reached, so the walk stops there; otherwise the reach moves to i + nums[i] if that's farther. Two arrays, one that gets through and one that doesn't:

def walk(nums):                                # the farthest square reachable so far, square by square
    reach, seen = 0, []
    for i, x in enumerate(nums):
        if i > reach:
            return f"reach {' '.join(map(str, seen))}, stuck before square {i}: no"
        reach = max(reach, i + x)
        seen.append(reach)
    return f"reach {' '.join(map(str, seen))}: yes"


for nums in ([1, 3, 0, 0, 2, 0, 1], [2, 1, 0, 3]):
    print(" ".join(map(str, nums)) + ":", walk(nums))

# 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
# 2 1 0 3: reach 2 2 2, stuck before square 3: no
import java.util.*;

public class Main {
    static String walk(int[] nums) {                 // the farthest square reachable so far, square by square
        int reach = 0;
        StringJoiner seen = new StringJoiner(" ");
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return "reach " + seen + ", stuck before square " + i + ": no";
            reach = Math.max(reach, i + nums[i]);
            seen.add(String.valueOf(reach));
        }
        return "reach " + seen + ": yes";
    }

    public static void main(String[] args) {
        for (int[] nums : new int[][] {{1, 3, 0, 0, 2, 0, 1}, {2, 1, 0, 3}}) {
            StringJoiner s = new StringJoiner(" ");
            for (int x : nums) s.add(String.valueOf(x));
            System.out.println(s + ": " + walk(nums));
        }
    }
}

// 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
// 2 1 0 3: reach 2 2 2, stuck before square 3: no
#include <bits/stdc++.h>
using namespace std;

string walk(const vector<int>& nums) {              // the farthest square reachable so far, square by square
    int reach = 0;
    string seen;
    for (int i = 0; i < (int) nums.size(); i++) {
        if (i > reach) return "reach " + seen + ", stuck before square " + to_string(i) + ": no";
        reach = max(reach, i + nums[i]);
        seen += (seen.empty() ? "" : " ") + to_string(reach);
    }
    return "reach " + seen + ": yes";
}

int main() {
    for (const auto& nums : vector<vector<int>>{{1, 3, 0, 0, 2, 0, 1}, {2, 1, 0, 3}}) {
        string s;
        for (int x : nums) s += (s.empty() ? "" : " ") + to_string(x);
        cout << s << ": " << walk(nums) << "\n";
    }
}

// 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
// 2 1 0 3: reach 2 2 2, stuck before square 3: no
function walk(nums) {                             // the farthest square reachable so far, square by square
    let reach = 0;
    const seen = [];
    for (let i = 0; i < nums.length; i++) {
        if (i > reach) return `reach ${seen.join(" ")}, stuck before square ${i}: no`;
        reach = Math.max(reach, i + nums[i]);
        seen.push(reach);
    }
    return `reach ${seen.join(" ")}: yes`;
}

for (const nums of [[1, 3, 0, 0, 2, 0, 1], [2, 1, 0, 3]]) console.log(`${nums.join(" ")}: ${walk(nums)}`);

// 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
// 2 1 0 3: reach 2 2 2, stuck before square 3: no
function walk(nums: number[]): string {           // the farthest square reachable so far, square by square
    let reach = 0;
    const seen: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        if (i > reach) return `reach ${seen.join(" ")}, stuck before square ${i}: no`;
        reach = Math.max(reach, i + nums[i]);
        seen.push(reach);
    }
    return `reach ${seen.join(" ")}: yes`;
}

for (const nums of [[1, 3, 0, 0, 2, 0, 1], [2, 1, 0, 3]]) console.log(`${nums.join(" ")}: ${walk(nums)}`);

// 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
// 2 1 0 3: reach 2 2 2, stuck before square 3: no
using System;
using System.Collections.Generic;

class Program {
    static string Walk(int[] nums) {                 // the farthest square reachable so far, square by square
        int reach = 0;
        var seen = new List<int>();
        for (int i = 0; i < nums.Length; i++) {
            if (i > reach) return $"reach {string.Join(" ", seen)}, stuck before square {i}: no";
            reach = Math.Max(reach, i + nums[i]);
            seen.Add(reach);
        }
        return $"reach {string.Join(" ", seen)}: yes";
    }

    static void Main() {
        foreach (var nums in new[] { new[] { 1, 3, 0, 0, 2, 0, 1 }, new[] { 2, 1, 0, 3 } })
            Console.WriteLine($"{string.Join(" ", nums)}: {Walk(nums)}");
    }
}

// 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
// 2 1 0 3: reach 2 2 2, stuck before square 3: no
package main

import (
	"fmt"
	"strings"
)

func join(xs []int) string {
	s := make([]string, len(xs))
	for i, x := range xs {
		s[i] = fmt.Sprint(x)
	}
	return strings.Join(s, " ")
}

func walk(nums []int) string { // the farthest square reachable so far, square by square
	reach := 0
	var seen []int
	for i, x := range nums {
		if i > reach {
			return fmt.Sprintf("reach %s, stuck before square %d: no", join(seen), i)
		}
		if i+x > reach {
			reach = i + x
		}
		seen = append(seen, reach)
	}
	return fmt.Sprintf("reach %s: yes", join(seen))
}

func main() {
	for _, nums := range [][]int{{1, 3, 0, 0, 2, 0, 1}, {2, 1, 0, 3}} {
		fmt.Printf("%s: %s\n", join(nums), walk(nums))
	}
}

// 1 3 0 0 2 0 1: reach 1 4 4 4 6 6 7: yes
// 2 1 0 3: reach 2 2 2, stuck before square 3: no

In 1 3 0 0 2 0 1 the 3 at square 1 carries the reach to 4, over both 0s, and the 2 at square 4 carries it to the end. In 2 1 0 3 the reach stays at 2, the 0, and square 3 is never reached. Greedy stays ahead: no way of jumping gets farther than the reach after the same squares, so when the reach stops short, nothing gets through. One pass, O(n).

How Far Can You Reach? Walk both arrays yourself: at each square, tap where the farthest reach goes, and see the second walk caught at a square past it. Then change any square's jump and watch its walk run again.

How Far Can You Reach?: walk both arrays by hand, moving the farthest reach at each square, then change a jump and walk again

Jumps in layers

Jump Game II wants the fewest jumps to the last square, which can always be reached. The squares one jump can land on form a stretch, and the next stretch ends at the farthest any square in this one reaches. That's BFS in layers, kept as two numbers: where this stretch ends, and how far the next one goes:

nums = [1, 2, 1, 1, 3, 1, 2, 1]
jumps, end, far, ends = 0, 0, 0, []            # end: where this jump's stretch of squares stops
for i in range(len(nums) - 1):
    far = max(far, i + nums[i])                # the farthest the next jump can land
    if i == end:                               # the stretch is used up: one more jump, to the farthest
        jumps, end = jumps + 1, far
        ends.append(end)
print(f"{' '.join(map(str, nums))}: {jumps} jumps, the stretches ending at", " ".join(map(str, ends)))

# 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 1, 3, 1, 2, 1};
        int jumps = 0, end = 0, far = 0;             // end: where this jump's stretch of squares stops
        StringJoiner ends = new StringJoiner(" "), s = new StringJoiner(" ");
        for (int x : nums) s.add(String.valueOf(x));
        for (int i = 0; i < nums.length - 1; i++) {
            far = Math.max(far, i + nums[i]);        // the farthest the next jump can land
            if (i == end) {                          // the stretch is used up: one more jump, to the farthest
                jumps++;
                end = far;
                ends.add(String.valueOf(end));
            }
        }
        System.out.println(s + ": " + jumps + " jumps, the stretches ending at " + ends);
    }
}

// 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 1, 1, 3, 1, 2, 1};
    int jumps = 0, end = 0, far = 0;                     // end: where this jump's stretch of squares stops
    string ends, s;
    for (int x : nums) s += (s.empty() ? "" : " ") + to_string(x);
    for (int i = 0; i + 1 < (int) nums.size(); i++) {
        far = max(far, i + nums[i]);                     // the farthest the next jump can land
        if (i == end) {                                  // the stretch is used up: one more jump, to the farthest
            jumps++;
            end = far;
            ends += (ends.empty() ? "" : " ") + to_string(end);
        }
    }
    cout << s << ": " << jumps << " jumps, the stretches ending at " << ends << "\n";
}

// 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7
const nums = [1, 2, 1, 1, 3, 1, 2, 1];
let jumps = 0, end = 0, far = 0;                  // end: where this jump's stretch of squares stops
const ends = [];
for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i]);             // the farthest the next jump can land
    if (i === end) {                              // the stretch is used up: one more jump, to the farthest
        jumps++;
        end = far;
        ends.push(end);
    }
}
console.log(`${nums.join(" ")}: ${jumps} jumps, the stretches ending at ${ends.join(" ")}`);

// 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7
const nums: number[] = [1, 2, 1, 1, 3, 1, 2, 1];
let jumps = 0, end = 0, far = 0;                  // end: where this jump's stretch of squares stops
const ends: number[] = [];
for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i]);             // the farthest the next jump can land
    if (i === end) {                              // the stretch is used up: one more jump, to the farthest
        jumps++;
        end = far;
        ends.push(end);
    }
}
console.log(`${nums.join(" ")}: ${jumps} jumps, the stretches ending at ${ends.join(" ")}`);

// 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7
using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] nums = { 1, 2, 1, 1, 3, 1, 2, 1 };
        int jumps = 0, end = 0, far = 0;             // end: where this jump's stretch of squares stops
        var ends = new List<int>();
        for (int i = 0; i < nums.Length - 1; i++) {
            far = Math.Max(far, i + nums[i]);        // the farthest the next jump can land
            if (i == end) {                          // the stretch is used up: one more jump, to the farthest
                jumps++;
                end = far;
                ends.Add(end);
            }
        }
        Console.WriteLine($"{string.Join(" ", nums)}: {jumps} jumps, the stretches ending at {string.Join(" ", ends)}");
    }
}

// 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7
package main

import (
	"fmt"
	"strings"
)

func main() {
	nums := []int{1, 2, 1, 1, 3, 1, 2, 1}
	jumps, end, far := 0, 0, 0 // end: where this jump's stretch of squares stops
	var ends, s []string
	for _, x := range nums {
		s = append(s, fmt.Sprint(x))
	}
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] > far {
			far = i + nums[i] // the farthest the next jump can land
		}
		if i == end { // the stretch is used up: one more jump, to the farthest
			jumps++
			end = far
			ends = append(ends, fmt.Sprint(end))
		}
	}
	fmt.Printf("%s: %d jumps, the stretches ending at %s\n", strings.Join(s, " "), jumps, strings.Join(ends, " "))
}

// 1 2 1 1 3 1 2 1: 4 jumps, the stretches ending at 1 3 4 7

Four jumps for 1 2 1 1 3 1 2 1: the stretches end at squares 1, 3, 4 and 7, the last of them the end. A jump is counted when the walk uses up a stretch, not at every square. Shortest Paths with BFS has the same layers on a graph; here they're always one stretch of squares, so a queue isn't needed.

The lesson's array 1 2 1 1 3 1 2 1 as a row of squares, numbered 0 to 7 underneath, coloured by the stretch of squares the jumps so far can reach, each stretch with a band and a name under it: the start, square 0; jump 1, square 1; jump 2, squares 2 to 3; jump 3, square 4; jump 4, squares 5 to 7. Green arcs above the row follow one route, from 0 to 1 to 3 to 4 to 7. Two cards: 4 jumps to the end, the stretches end at 1, 3, 4 and 7; one route, 0 → 1 → 3 → 4 → 7. Focal line: count a jump when a stretch is used up, not at every square. Title: stretches of one jump.

A window of starts

Jump Game VII has a string of 0s and 1s and jumps of between minJump and maxJump squares, landing only on 0s. A 0 at i is reachable when some reachable 0 lies between i − maxJump and i − minJump. Rather than look back over that range at every square, keep a count of the reachable squares inside it: add the square that comes in, take off the one that goes out:

def reachable(s, lo, hi):                      # a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
    can = [False] * len(s)
    can[0] = True
    count = 0                                  # how many reachable squares the window holds
    for i in range(1, len(s)):
        if i - lo >= 0 and can[i - lo]:
            count += 1                         # the square coming into the window
        if i - hi - 1 >= 0 and can[i - hi - 1]:
            count -= 1                         # the square going out of it
        can[i] = s[i] == "0" and count > 0
    return [i for i, c in enumerate(can) if c]


for s, lo, hi in (("0100100010", 2, 4), ("0011100", 1, 2)):
    got = reachable(s, lo, hi)
    print(f"{s}, jumps of {lo} to {hi}: reachable", " ".join(map(str, got)) + ",",
          "the end reached" if got[-1] == len(s) - 1 else "the end not reached")

# 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
# 0011100, jumps of 1 to 2: reachable 0 1, the end not reached
import java.util.*;

public class Main {
    static List<Integer> reachable(String s, int lo, int hi) {   // a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
        boolean[] can = new boolean[s.length()];
        can[0] = true;
        int count = 0;                               // how many reachable squares the window holds
        for (int i = 1; i < s.length(); i++) {
            if (i - lo >= 0 && can[i - lo]) count++;         // the square coming into the window
            if (i - hi - 1 >= 0 && can[i - hi - 1]) count--; // the square going out of it
            can[i] = s.charAt(i) == '0' && count > 0;
        }
        List<Integer> got = new ArrayList<>();
        for (int i = 0; i < can.length; i++) if (can[i]) got.add(i);
        return got;
    }

    public static void main(String[] args) {
        Object[][] runs = {{"0100100010", 2, 4}, {"0011100", 1, 2}};
        for (Object[] r : runs) {
            String s = (String) r[0];
            int lo = (int) r[1], hi = (int) r[2];
            List<Integer> got = reachable(s, lo, hi);
            StringJoiner j = new StringJoiner(" ");
            for (int x : got) j.add(String.valueOf(x));
            System.out.println(s + ", jumps of " + lo + " to " + hi + ": reachable " + j + ", "
                    + (got.get(got.size() - 1) == s.length() - 1 ? "the end reached" : "the end not reached"));
        }
    }
}

// 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
// 0011100, jumps of 1 to 2: reachable 0 1, the end not reached
#include <bits/stdc++.h>
using namespace std;

vector<int> reachable(const string& s, int lo, int hi) {   // a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
    vector<bool> can(s.size(), false);
    can[0] = true;
    int count = 0;                                       // how many reachable squares the window holds
    for (int i = 1; i < (int) s.size(); i++) {
        if (i - lo >= 0 && can[i - lo]) count++;         // the square coming into the window
        if (i - hi - 1 >= 0 && can[i - hi - 1]) count--; // the square going out of it
        can[i] = s[i] == '0' && count > 0;
    }
    vector<int> got;
    for (int i = 0; i < (int) can.size(); i++) if (can[i]) got.push_back(i);
    return got;
}

int main() {
    vector<tuple<string, int, int>> runs = {{"0100100010", 2, 4}, {"0011100", 1, 2}};
    for (auto& [s, lo, hi] : runs) {
        vector<int> got = reachable(s, lo, hi);
        cout << s << ", jumps of " << lo << " to " << hi << ": reachable";
        for (int x : got) cout << " " << x;
        cout << ", " << (got.back() == (int) s.size() - 1 ? "the end reached" : "the end not reached") << "\n";
    }
}

// 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
// 0011100, jumps of 1 to 2: reachable 0 1, the end not reached
function reachable(s, lo, hi) {                   // a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
    const can = new Array(s.length).fill(false);
    can[0] = true;
    let count = 0;                                // how many reachable squares the window holds
    for (let i = 1; i < s.length; i++) {
        if (i - lo >= 0 && can[i - lo]) count++;          // the square coming into the window
        if (i - hi - 1 >= 0 && can[i - hi - 1]) count--;  // the square going out of it
        can[i] = s[i] === "0" && count > 0;
    }
    return can.flatMap((c, i) => (c ? [i] : []));
}

for (const [s, lo, hi] of [["0100100010", 2, 4], ["0011100", 1, 2]]) {
    const got = reachable(s, lo, hi);
    console.log(`${s}, jumps of ${lo} to ${hi}: reachable ${got.join(" ")}, ${got[got.length - 1] === s.length - 1 ? "the end reached" : "the end not reached"}`);
}

// 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
// 0011100, jumps of 1 to 2: reachable 0 1, the end not reached
function reachable(s: string, lo: number, hi: number): number[] {   // a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
    const can: boolean[] = new Array(s.length).fill(false);
    can[0] = true;
    let count = 0;                                // how many reachable squares the window holds
    for (let i = 1; i < s.length; i++) {
        if (i - lo >= 0 && can[i - lo]) count++;          // the square coming into the window
        if (i - hi - 1 >= 0 && can[i - hi - 1]) count--;  // the square going out of it
        can[i] = s[i] === "0" && count > 0;
    }
    return can.flatMap((c, i) => (c ? [i] : []));
}

const runs: [string, number, number][] = [["0100100010", 2, 4], ["0011100", 1, 2]];
for (const [s, lo, hi] of runs) {
    const got = reachable(s, lo, hi);
    console.log(`${s}, jumps of ${lo} to ${hi}: reachable ${got.join(" ")}, ${got[got.length - 1] === s.length - 1 ? "the end reached" : "the end not reached"}`);
}

// 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
// 0011100, jumps of 1 to 2: reachable 0 1, the end not reached
using System;
using System.Collections.Generic;

class Program {
    static List<int> Reachable(string s, int lo, int hi) {   // a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
        var can = new bool[s.Length];
        can[0] = true;
        int count = 0;                               // how many reachable squares the window holds
        for (int i = 1; i < s.Length; i++) {
            if (i - lo >= 0 && can[i - lo]) count++;         // the square coming into the window
            if (i - hi - 1 >= 0 && can[i - hi - 1]) count--; // the square going out of it
            can[i] = s[i] == '0' && count > 0;
        }
        var got = new List<int>();
        for (int i = 0; i < can.Length; i++) if (can[i]) got.Add(i);
        return got;
    }

    static void Main() {
        foreach (var (s, lo, hi) in new[] { ("0100100010", 2, 4), ("0011100", 1, 2) }) {
            var got = Reachable(s, lo, hi);
            Console.WriteLine($"{s}, jumps of {lo} to {hi}: reachable {string.Join(" ", got)}, "
                + (got[got.Count - 1] == s.Length - 1 ? "the end reached" : "the end not reached"));
        }
    }
}

// 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
// 0011100, jumps of 1 to 2: reachable 0 1, the end not reached
package main

import (
	"fmt"
	"strings"
)

func reachable(s string, lo, hi int) []int { // a 0 at i is reachable from a reachable 0 in [i - hi, i - lo]
	can := make([]bool, len(s))
	can[0] = true
	count := 0 // how many reachable squares the window holds
	for i := 1; i < len(s); i++ {
		if i-lo >= 0 && can[i-lo] {
			count++ // the square coming into the window
		}
		if i-hi-1 >= 0 && can[i-hi-1] {
			count-- // the square going out of it
		}
		can[i] = s[i] == '0' && count > 0
	}
	var got []int
	for i, c := range can {
		if c {
			got = append(got, i)
		}
	}
	return got
}

func main() {
	runs := []struct {
		s      string
		lo, hi int
	}{{"0100100010", 2, 4}, {"0011100", 1, 2}}
	for _, r := range runs {
		got := reachable(r.s, r.lo, r.hi)
		parts := make([]string, len(got))
		for i, x := range got {
			parts[i] = fmt.Sprint(x)
		}
		end := "the end not reached"
		if got[len(got)-1] == len(r.s)-1 {
			end = "the end reached"
		}
		fmt.Printf("%s, jumps of %d to %d: reachable %s, %s\n", r.s, r.lo, r.hi, strings.Join(parts, " "), end)
	}
}

// 0100100010, jumps of 2 to 4: reachable 0 2 3 5 6 7 9, the end reached
// 0011100, jumps of 1 to 2: reachable 0 1, the end not reached

With jumps of 2 to 4, 0100100010 reaches 0, 2, 3, 5, 6, 7 and 9, the end. With jumps of 1 to 2, 0011100 reaches only 0 and 1: three 1s in a row are wider than any jump. O(n), where looking back over the range at every square is O(n × (maxJump − minJump)).

A tank that restarts

Gas Station: stations stand in a circle, with gas[i] to take on at station i and cost[i] to drive to the next. From which station does a car that starts empty make it round, if any? If the total gas is less than the total cost, none. Otherwise one pass finds it: run a tank from a start, and when it goes below 0 at station i, start again after i:

gas, cost = [4, 1, 5, 2, 3, 6], [3, 4, 2, 5, 4, 2]
tank, start, dry = 0, 0, []
for i in range(len(gas)):
    tank += gas[i] - cost[i]
    if tank < 0:                               # nothing from start to i can reach i + 1: start after it
        dry.append(i)
        start, tank = i + 1, 0
print(f"gas {sum(gas)} for cost {sum(cost)}:", "a start exists" if sum(gas) >= sum(cost) else "no start",
      f"| ran dry at {' and '.join(map(str, dry))}, so start at {start}")

# gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] gas = {4, 1, 5, 2, 3, 6}, cost = {3, 4, 2, 5, 4, 2};
        int tank = 0, start = 0, totalGas = 0, totalCost = 0;
        StringJoiner dry = new StringJoiner(" and ");
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {                          // nothing from start to i can reach i + 1: start after it
                dry.add(String.valueOf(i));
                start = i + 1;
                tank = 0;
            }
        }
        System.out.println("gas " + totalGas + " for cost " + totalCost + ": " + (totalGas >= totalCost ? "a start exists" : "no start")
                + " | ran dry at " + dry + ", so start at " + start);
    }
}

// gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> gas = {4, 1, 5, 2, 3, 6}, cost = {3, 4, 2, 5, 4, 2};
    int tank = 0, start = 0, totalGas = 0, totalCost = 0;
    string dry;
    for (int i = 0; i < (int) gas.size(); i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) {                                  // nothing from start to i can reach i + 1: start after it
            dry += (dry.empty() ? "" : " and ") + to_string(i);
            start = i + 1;
            tank = 0;
        }
    }
    cout << "gas " << totalGas << " for cost " << totalCost << ": " << (totalGas >= totalCost ? "a start exists" : "no start")
         << " | ran dry at " << dry << ", so start at " << start << "\n";
}

// gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5
const gas = [4, 1, 5, 2, 3, 6], cost = [3, 4, 2, 5, 4, 2];
let tank = 0, start = 0;
const dry = [];
for (let i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) {                               // nothing from start to i can reach i + 1: start after it
        dry.push(i);
        start = i + 1;
        tank = 0;
    }
}
const sum = (xs) => xs.reduce((s, x) => s + x, 0);
console.log(`gas ${sum(gas)} for cost ${sum(cost)}: ${sum(gas) >= sum(cost) ? "a start exists" : "no start"} | ran dry at ${dry.join(" and ")}, so start at ${start}`);

// gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5
const gas: number[] = [4, 1, 5, 2, 3, 6], cost: number[] = [3, 4, 2, 5, 4, 2];
let tank = 0, start = 0;
const dry: number[] = [];
for (let i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) {                               // nothing from start to i can reach i + 1: start after it
        dry.push(i);
        start = i + 1;
        tank = 0;
    }
}
const sum = (xs: number[]) => xs.reduce((s, x) => s + x, 0);
console.log(`gas ${sum(gas)} for cost ${sum(cost)}: ${sum(gas) >= sum(cost) ? "a start exists" : "no start"} | ran dry at ${dry.join(" and ")}, so start at ${start}`);

// gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static void Main() {
        int[] gas = { 4, 1, 5, 2, 3, 6 }, cost = { 3, 4, 2, 5, 4, 2 };
        int tank = 0, start = 0;
        var dry = new List<int>();
        for (int i = 0; i < gas.Length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {                          // nothing from start to i can reach i + 1: start after it
                dry.Add(i);
                start = i + 1;
                tank = 0;
            }
        }
        Console.WriteLine($"gas {gas.Sum()} for cost {cost.Sum()}: {(gas.Sum() >= cost.Sum() ? "a start exists" : "no start")} | ran dry at {string.Join(" and ", dry)}, so start at {start}");
    }
}

// gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5
package main

import (
	"fmt"
	"strings"
)

func main() {
	gas, cost := []int{4, 1, 5, 2, 3, 6}, []int{3, 4, 2, 5, 4, 2}
	tank, start, totalGas, totalCost := 0, 0, 0, 0
	var dry []string
	for i := range gas {
		totalGas += gas[i]
		totalCost += cost[i]
		tank += gas[i] - cost[i]
		if tank < 0 { // nothing from start to i can reach i + 1: start after it
			dry = append(dry, fmt.Sprint(i))
			start, tank = i+1, 0
		}
	}
	verdict := "no start"
	if totalGas >= totalCost {
		verdict = "a start exists"
	}
	fmt.Printf("gas %d for cost %d: %s | ran dry at %s, so start at %d\n", totalGas, totalCost, verdict, strings.Join(dry, " and "), start)
}

// gas 21 for cost 20: a start exists | ran dry at 1 and 4, so start at 5

The total is 21 against 20, so a start exists. From 0 the tank runs dry at station 1, so the start moves to 2; it runs dry again at 4, so the start moves to 5, and from 5 the car makes it round. No station between a failed start and its failure can do better: each would begin that stretch with a tank no fuller than the one that ran dry, at the same station. So the start after the last failure is the only one left, and the total says it works.

The lesson's six stations in a circle, gas 4, 1, 5, 2, 3 and 6 and cost 3, 4, 2, 5, 4 and 2, as two bar charts of the tank after each station, from a zero line. One pass from station 0: the tank reads 1, then minus 2 at station 1, red and crossed, so a new start is marked at 2; then 3, 0 and minus 1 at station 4, red and crossed, so a new start at 5; then 4. From 5, all the way round, stations 5, 0, 1, 2, 3 and 4: the tank reads 4, 5, 2, 5, 2 and 1, all green, each station ticked. Two cards: gas 21 for cost 20, so some start makes it round; start at 5, the tank never goes below 0. Focal line: no start up to a dry station gets past it. Title: start after the last dry station.

A range of open brackets

Valid Parenthesis String lets each '' be '(', ')' or nothing. Instead of trying every choice, keep the range of how many brackets can be open, its lowest and its highest. A '(' raises both, a ')' lowers both, and a '' widens the range by one each way. If the highest drops below 0 there are too many ')'; the lowest never goes below 0; the string is valid if the lowest can end at 0. Minimum Add to Make Parentheses Valid is the same walk with one balance:

def valid(s):                                  # the fewest and the most brackets that can be open; '*' is (, ) or nothing
    lo = hi = 0
    for ch in s:
        lo, hi = (lo + 1, hi + 1) if ch == "(" else (lo - 1, hi - 1) if ch == ")" else (lo - 1, hi + 1)
        if hi < 0:
            return False                       # more ')' than any choice can open
        lo = max(lo, 0)
    return lo == 0


def to_add(s):                                 # a balance that never goes below 0
    open_, add = 0, 0
    for ch in s:
        if ch == "(":
            open_ += 1
        elif open_:
            open_ -= 1
        else:
            add += 1                           # a ')' with nothing open needs a '(' before it
    return add, open_                          # and every '(' still open needs a ')'


for s in ("((*)*)", "(*()*))("):
    print(f"{s}:", "valid" if valid(s) else "not valid")
before, after = to_add(")((())(")
print(f")((())(: add {before + after}, {before} '(' and {after} ')'")

# ((*)*): valid
# (*()*))(: not valid
# )((())(: add 3, 1 '(' and 2 ')'
public class Main {
    static boolean valid(String s) {                 // the fewest and the most brackets that can be open; '*' is (, ) or nothing
        int lo = 0, hi = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') { lo++; hi++; }
            else if (ch == ')') { lo--; hi--; }
            else { lo--; hi++; }
            if (hi < 0) return false;                // more ')' than any choice can open
            lo = Math.max(lo, 0);
        }
        return lo == 0;
    }

    static int[] toAdd(String s) {                   // a balance that never goes below 0
        int open = 0, add = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') open++;
            else if (open > 0) open--;
            else add++;                              // a ')' with nothing open needs a '(' before it
        }
        return new int[] {add, open};                // and every '(' still open needs a ')'
    }

    public static void main(String[] args) {
        for (String s : new String[] {"((*)*)", "(*()*))("}) System.out.println(s + ": " + (valid(s) ? "valid" : "not valid"));
        int[] a = toAdd(")((())(");
        System.out.println(")((())(: add " + (a[0] + a[1]) + ", " + a[0] + " '(' and " + a[1] + " ')'");
    }
}

// ((*)*): valid
// (*()*))(: not valid
// )((())(: add 3, 1 '(' and 2 ')'
#include <bits/stdc++.h>
using namespace std;

bool valid(const string& s) {                       // the fewest and the most brackets that can be open; '*' is (, ) or nothing
    int lo = 0, hi = 0;
    for (char ch : s) {
        if (ch == '(') { lo++; hi++; }
        else if (ch == ')') { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;                        // more ')' than any choice can open
        lo = max(lo, 0);
    }
    return lo == 0;
}

pair<int, int> toAdd(const string& s) {              // a balance that never goes below 0
    int open = 0, add = 0;
    for (char ch : s) {
        if (ch == '(') open++;
        else if (open > 0) open--;
        else add++;                                      // a ')' with nothing open needs a '(' before it
    }
    return {add, open};                                  // and every '(' still open needs a ')'
}

int main() {
    for (string s : {"((*)*)", "(*()*))("}) cout << s << ": " << (valid(s) ? "valid" : "not valid") << "\n";
    auto [before, after] = toAdd(")((())(");
    cout << ")((())(: add " << before + after << ", " << before << " '(' and " << after << " ')'\n";
}

// ((*)*): valid
// (*()*))(: not valid
// )((())(: add 3, 1 '(' and 2 ')'
function valid(s) {                               // the fewest and the most brackets that can be open; '*' is (, ) or nothing
    let lo = 0, hi = 0;
    for (const ch of s) {
        if (ch === "(") { lo++; hi++; }
        else if (ch === ")") { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;                 // more ')' than any choice can open
        lo = Math.max(lo, 0);
    }
    return lo === 0;
}

function toAdd(s) {                               // a balance that never goes below 0
    let open = 0, add = 0;
    for (const ch of s) {
        if (ch === "(") open++;
        else if (open > 0) open--;
        else add++;                               // a ')' with nothing open needs a '(' before it
    }
    return [add, open];                           // and every '(' still open needs a ')'
}

for (const s of ["((*)*)", "(*()*))("]) console.log(`${s}: ${valid(s) ? "valid" : "not valid"}`);
const [before, after] = toAdd(")((())(");
console.log(`)((())(: add ${before + after}, ${before} '(' and ${after} ')'`);

// ((*)*): valid
// (*()*))(: not valid
// )((())(: add 3, 1 '(' and 2 ')'
function valid(s: string): boolean {              // the fewest and the most brackets that can be open; '*' is (, ) or nothing
    let lo = 0, hi = 0;
    for (const ch of s) {
        if (ch === "(") { lo++; hi++; }
        else if (ch === ")") { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;                 // more ')' than any choice can open
        lo = Math.max(lo, 0);
    }
    return lo === 0;
}

function toAdd(s: string): [number, number] {     // a balance that never goes below 0
    let open = 0, add = 0;
    for (const ch of s) {
        if (ch === "(") open++;
        else if (open > 0) open--;
        else add++;                               // a ')' with nothing open needs a '(' before it
    }
    return [add, open];                           // and every '(' still open needs a ')'
}

for (const s of ["((*)*)", "(*()*))("]) console.log(`${s}: ${valid(s) ? "valid" : "not valid"}`);
const [before, after] = toAdd(")((())(");
console.log(`)((())(: add ${before + after}, ${before} '(' and ${after} ')'`);

// ((*)*): valid
// (*()*))(: not valid
// )((())(: add 3, 1 '(' and 2 ')'
using System;

class Program {
    static bool Valid(string s) {                    // the fewest and the most brackets that can be open; '*' is (, ) or nothing
        int lo = 0, hi = 0;
        foreach (char ch in s) {
            if (ch == '(') { lo++; hi++; }
            else if (ch == ')') { lo--; hi--; }
            else { lo--; hi++; }
            if (hi < 0) return false;                // more ')' than any choice can open
            lo = Math.Max(lo, 0);
        }
        return lo == 0;
    }

    static (int, int) ToAdd(string s) {              // a balance that never goes below 0
        int open = 0, add = 0;
        foreach (char ch in s) {
            if (ch == '(') open++;
            else if (open > 0) open--;
            else add++;                              // a ')' with nothing open needs a '(' before it
        }
        return (add, open);                          // and every '(' still open needs a ')'
    }

    static void Main() {
        foreach (var s in new[] { "((*)*)", "(*()*))(" }) Console.WriteLine($"{s}: {(Valid(s) ? "valid" : "not valid")}");
        var (before, after) = ToAdd(")((())(");
        Console.WriteLine($")((())(: add {before + after}, {before} '(' and {after} ')'");
    }
}

// ((*)*): valid
// (*()*))(: not valid
// )((())(: add 3, 1 '(' and 2 ')'
package main

import "fmt"

func valid(s string) bool { // the fewest and the most brackets that can be open; '*' is (, ) or nothing
	lo, hi := 0, 0
	for _, ch := range s {
		switch ch {
		case '(':
			lo, hi = lo+1, hi+1
		case ')':
			lo, hi = lo-1, hi-1
		default:
			lo, hi = lo-1, hi+1
		}
		if hi < 0 {
			return false // more ')' than any choice can open
		}
		if lo < 0 {
			lo = 0
		}
	}
	return lo == 0
}

func toAdd(s string) (int, int) { // a balance that never goes below 0
	open, add := 0, 0
	for _, ch := range s {
		if ch == '(' {
			open++
		} else if open > 0 {
			open--
		} else {
			add++ // a ')' with nothing open needs a '(' before it
		}
	}
	return add, open // and every '(' still open needs a ')'
}

func main() {
	for _, s := range []string{"((*)*)", "(*()*))("} {
		verdict := "not valid"
		if valid(s) {
			verdict = "valid"
		}
		fmt.Printf("%s: %s\n", s, verdict)
	}
	before, after := toAdd(")((())(")
	fmt.Printf(")((())(: add %d, %d '(' and %d ')'\n", before+after, before, after)
}

// ((*)*): valid
// (*()*))(: not valid
// )((())(: add 3, 1 '(' and 2 ')'

(()) is valid: some choice of its stars closes every bracket. (()))( isn't: its last '(' is still open at the end, whatever the stars are. In )((())( the first ')' has nothing to close, so one '(' goes in front, and two '(' are still open at the end: 3 to add. Stacks matches brackets with a stack; here one or two counts are all the walk needs.

Two passes for two neighbours

Candy: children stand in a row, each with a rating; each gets at least one candy, and a child rated higher than a neighbour gets more than that neighbour. Each child has two neighbours, and one pass sees only one side. Pass left to right for the left neighbours, right to left for the right ones, and give each child the larger of the two:

ratings = [2, 4, 3, 5, 2, 1, 1, 3]
n = len(ratings)
left = [1] * n                                 # one more than the left neighbour when rated higher
for i in range(1, n):
    if ratings[i] > ratings[i - 1]:
        left[i] = left[i - 1] + 1
right = [1] * n                                # one more than the right neighbour when rated higher
for i in range(n - 2, -1, -1):
    if ratings[i] > ratings[i + 1]:
        right[i] = right[i + 1] + 1
candy = [max(a, b) for a, b in zip(left, right)]
print(f"{sum(candy)} candies:", " ".join(map(str, candy)), "| left pass", " ".join(map(str, left)),
      "| right pass", " ".join(map(str, right)))

# 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1
import java.util.*;

public class Main {
    static String join(int[] xs) {
        StringJoiner j = new StringJoiner(" ");
        for (int x : xs) j.add(String.valueOf(x));
        return j.toString();
    }

    public static void main(String[] args) {
        int[] ratings = {2, 4, 3, 5, 2, 1, 1, 3};
        int n = ratings.length;
        int[] left = new int[n], right = new int[n], candy = new int[n];
        Arrays.fill(left, 1);                        // one more than the left neighbour when rated higher
        for (int i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        Arrays.fill(right, 1);                       // one more than the right neighbour when rated higher
        for (int i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
        int total = 0;
        for (int i = 0; i < n; i++) {
            candy[i] = Math.max(left[i], right[i]);
            total += candy[i];
        }
        System.out.println(total + " candies: " + join(candy) + " | left pass " + join(left) + " | right pass " + join(right));
    }
}

// 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1
#include <bits/stdc++.h>
using namespace std;

string join(const vector<int>& xs) {
    string s;
    for (int x : xs) s += (s.empty() ? "" : " ") + to_string(x);
    return s;
}

int main() {
    vector<int> ratings = {2, 4, 3, 5, 2, 1, 1, 3};
    int n = ratings.size();
    vector<int> left(n, 1), right(n, 1), candy(n);       // one more than a neighbour rated lower, from each side
    for (int i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
    int total = 0;
    for (int i = 0; i < n; i++) total += candy[i] = max(left[i], right[i]);
    cout << total << " candies: " << join(candy) << " | left pass " << join(left) << " | right pass " << join(right) << "\n";
}

// 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1
const ratings = [2, 4, 3, 5, 2, 1, 1, 3];
const n = ratings.length;
const left = new Array(n).fill(1);                // one more than the left neighbour when rated higher
for (let i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
const right = new Array(n).fill(1);               // one more than the right neighbour when rated higher
for (let i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
const candy = left.map((a, i) => Math.max(a, right[i]));
console.log(`${candy.reduce((s, x) => s + x, 0)} candies: ${candy.join(" ")} | left pass ${left.join(" ")} | right pass ${right.join(" ")}`);

// 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1
const ratings: number[] = [2, 4, 3, 5, 2, 1, 1, 3];
const n = ratings.length;
const left: number[] = new Array(n).fill(1);      // one more than the left neighbour when rated higher
for (let i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
const right: number[] = new Array(n).fill(1);     // one more than the right neighbour when rated higher
for (let i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
const candy = left.map((a, i) => Math.max(a, right[i]));
console.log(`${candy.reduce((s, x) => s + x, 0)} candies: ${candy.join(" ")} | left pass ${left.join(" ")} | right pass ${right.join(" ")}`);

// 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1
using System;
using System.Linq;

class Program {
    static void Main() {
        int[] ratings = { 2, 4, 3, 5, 2, 1, 1, 3 };
        int n = ratings.Length;
        var left = Enumerable.Repeat(1, n).ToArray();    // one more than the left neighbour when rated higher
        for (int i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        var right = Enumerable.Repeat(1, n).ToArray();   // one more than the right neighbour when rated higher
        for (int i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
        var candy = left.Select((a, i) => Math.Max(a, right[i])).ToArray();
        Console.WriteLine($"{candy.Sum()} candies: {string.Join(" ", candy)} | left pass {string.Join(" ", left)} | right pass {string.Join(" ", right)}");
    }
}

// 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1
package main

import (
	"fmt"
	"strings"
)

func join(xs []int) string {
	s := make([]string, len(xs))
	for i, x := range xs {
		s[i] = fmt.Sprint(x)
	}
	return strings.Join(s, " ")
}

func main() {
	ratings := []int{2, 4, 3, 5, 2, 1, 1, 3}
	n := len(ratings)
	left, right, candy := make([]int, n), make([]int, n), make([]int, n)
	for i := range left {
		left[i], right[i] = 1, 1 // one more than a neighbour rated lower, from each side
	}
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	total := 0
	for i := range candy {
		candy[i] = left[i]
		if right[i] > candy[i] {
			candy[i] = right[i]
		}
		total += candy[i]
	}
	fmt.Printf("%d candies: %s | left pass %s | right pass %s\n", total, join(candy), join(left), join(right))
}

// 13 candies: 1 2 1 3 2 1 1 2 | left pass 1 2 1 2 1 1 1 2 | right pass 1 2 1 3 2 1 1 1

13 candies: 1 2 1 3 2 1 1 2. The child rated 5 gets 2 from the left pass, as it's rated above a 3, and 3 from the right pass, as it's above a 2 that's above a 1; it needs the 3. Each pass gives the fewest its side allows, so the larger of the two keeps both rules, and anything smaller breaks one.

Spotting it

The problemWhat the walk keepsWhy it's safe
Jump GameThe farthest reachReachable squares are a stretch from the start
Jump Game IIThis stretch's end, the next one'sBFS layers, one jump each
Jump Game VIIReachable squares in the windowOnly the window can reach i
Gas StationA tank, restarted after it runs dryNo start up to a failure gets past it
Valid Parenthesis StringThe lowest and highest open countEvery choice of stars lies in range
CandyTwo passes, then the largerEach pass meets one neighbour

Near misses: when the state is a set of choices rather than one number, such as the cheapest way to jump when each square costs something, it's Dynamic Programming; the proof idea, an exchange, is Introduction to Greedy Algorithms.

Mistakes that look right

Two of these run below in every language. The others are just as common:

  • Restarting at the station that failed: it can't be the start either; start after it.
  • Candy in one pass: the right neighbours go unseen.
  • A jump at every square: Jump Game II counts a jump when a stretch is used up.
  • Stopping at a 0: a 0 blocks only when the reach can't get past it.
  • The lowest open count below 0: a '*' can't close a bracket that isn't open; keep it at 0.
  • No check of the total: the one pass always names a start; only the total says it works.
def start(gas, cost, after):                   # Gas Station's one pass; the mistake restarts at the failing station
    tank, s = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            s, tank = (i + 1 if after else i), 0
    return s


def laps(gas, cost, s):                        # does a car from s make it round?
    tank = 0
    for k in range(len(gas)):
        i = (s + k) % len(gas)
        tank += gas[i] - cost[i]
        if tank < 0:
            return f"runs dry leaving {i}"
    return "makes it round"


gas, cost = [4, 1, 5, 2, 3, 6], [3, 4, 2, 5, 4, 2]
wrong, right = start(gas, cost, False), start(gas, cost, True)
print(f"restart at the failing station: {wrong}, which {laps(gas, cost, wrong)}; after it: {right}, which {laps(gas, cost, right)}")

ratings = [2, 4, 3, 5, 2, 1, 1, 3]             # Candy in one pass, left to right only
one = [1] * len(ratings)
for i in range(1, len(ratings)):
    if ratings[i] > ratings[i - 1]:
        one[i] = one[i - 1] + 1
bad = [i for i in range(len(ratings) - 1) if ratings[i] > ratings[i + 1] and one[i] <= one[i + 1]]
print(f"one pass: {sum(one)} candies, but child {bad[0]}, rated {ratings[bad[0]]}, gets no more than child {bad[0] + 1}, rated {ratings[bad[0] + 1]}")

# restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
# one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1
import java.util.*;

public class Main {
    static int start(int[] gas, int[] cost, boolean after) {   // Gas Station's one pass; the mistake restarts at the failing station
        int tank = 0, s = 0;
        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                s = after ? i + 1 : i;
                tank = 0;
            }
        }
        return s;
    }

    static String laps(int[] gas, int[] cost, int s) {   // does a car from s make it round?
        int tank = 0;
        for (int k = 0; k < gas.length; k++) {
            int i = (s + k) % gas.length;
            tank += gas[i] - cost[i];
            if (tank < 0) return "runs dry leaving " + i;
        }
        return "makes it round";
    }

    public static void main(String[] args) {
        int[] gas = {4, 1, 5, 2, 3, 6}, cost = {3, 4, 2, 5, 4, 2};
        int wrong = start(gas, cost, false), right = start(gas, cost, true);
        System.out.println("restart at the failing station: " + wrong + ", which " + laps(gas, cost, wrong) + "; after it: "
                + right + ", which " + laps(gas, cost, right));

        int[] ratings = {2, 4, 3, 5, 2, 1, 1, 3};    // Candy in one pass, left to right only
        int[] one = new int[ratings.length];
        Arrays.fill(one, 1);
        for (int i = 1; i < ratings.length; i++) if (ratings[i] > ratings[i - 1]) one[i] = one[i - 1] + 1;
        int bad = -1, total = 0;
        for (int x : one) total += x;
        for (int i = 0; i + 1 < ratings.length && bad < 0; i++) if (ratings[i] > ratings[i + 1] && one[i] <= one[i + 1]) bad = i;
        System.out.println("one pass: " + total + " candies, but child " + bad + ", rated " + ratings[bad] + ", gets no more than child "
                + (bad + 1) + ", rated " + ratings[bad + 1]);
    }
}

// restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
// one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1
#include <bits/stdc++.h>
using namespace std;

int start(const vector<int>& gas, const vector<int>& cost, bool after) {   // the mistake restarts at the failing station
    int tank = 0, s = 0;
    for (int i = 0; i < (int) gas.size(); i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            s = after ? i + 1 : i;
            tank = 0;
        }
    }
    return s;
}

string laps(const vector<int>& gas, const vector<int>& cost, int s) {   // does a car from s make it round?
    int tank = 0, n = gas.size();
    for (int k = 0; k < n; k++) {
        int i = (s + k) % n;
        tank += gas[i] - cost[i];
        if (tank < 0) return "runs dry leaving " + to_string(i);
    }
    return "makes it round";
}

int main() {
    vector<int> gas = {4, 1, 5, 2, 3, 6}, cost = {3, 4, 2, 5, 4, 2};
    int wrong = start(gas, cost, false), right = start(gas, cost, true);
    cout << "restart at the failing station: " << wrong << ", which " << laps(gas, cost, wrong) << "; after it: " << right
         << ", which " << laps(gas, cost, right) << "\n";

    vector<int> ratings = {2, 4, 3, 5, 2, 1, 1, 3};      // Candy in one pass, left to right only
    vector<int> one(ratings.size(), 1);
    for (size_t i = 1; i < ratings.size(); i++) if (ratings[i] > ratings[i - 1]) one[i] = one[i - 1] + 1;
    int bad = -1, total = 0;
    for (int x : one) total += x;
    for (size_t i = 0; i + 1 < ratings.size() && bad < 0; i++) if (ratings[i] > ratings[i + 1] && one[i] <= one[i + 1]) bad = i;
    cout << "one pass: " << total << " candies, but child " << bad << ", rated " << ratings[bad] << ", gets no more than child "
         << bad + 1 << ", rated " << ratings[bad + 1] << "\n";
}

// restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
// one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1
function start(gas, cost, after) {                // Gas Station's one pass; the mistake restarts at the failing station
    let tank = 0, s = 0;
    for (let i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            s = after ? i + 1 : i;
            tank = 0;
        }
    }
    return s;
}

function laps(gas, cost, s) {                     // does a car from s make it round?
    let tank = 0;
    for (let k = 0; k < gas.length; k++) {
        const i = (s + k) % gas.length;
        tank += gas[i] - cost[i];
        if (tank < 0) return `runs dry leaving ${i}`;
    }
    return "makes it round";
}

const gas = [4, 1, 5, 2, 3, 6], cost = [3, 4, 2, 5, 4, 2];
const wrong = start(gas, cost, false), right = start(gas, cost, true);
console.log(`restart at the failing station: ${wrong}, which ${laps(gas, cost, wrong)}; after it: ${right}, which ${laps(gas, cost, right)}`);

const ratings = [2, 4, 3, 5, 2, 1, 1, 3];         // Candy in one pass, left to right only
const one = new Array(ratings.length).fill(1);
for (let i = 1; i < ratings.length; i++) if (ratings[i] > ratings[i - 1]) one[i] = one[i - 1] + 1;
const bad = ratings.findIndex((r, i) => i + 1 < ratings.length && r > ratings[i + 1] && one[i] <= one[i + 1]);
console.log(`one pass: ${one.reduce((s, x) => s + x, 0)} candies, but child ${bad}, rated ${ratings[bad]}, gets no more than child ${bad + 1}, rated ${ratings[bad + 1]}`);

// restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
// one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1
function start(gas: number[], cost: number[], after: boolean): number {   // the mistake restarts at the failing station
    let tank = 0, s = 0;
    for (let i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            s = after ? i + 1 : i;
            tank = 0;
        }
    }
    return s;
}

function laps(gas: number[], cost: number[], s: number): string {   // does a car from s make it round?
    let tank = 0;
    for (let k = 0; k < gas.length; k++) {
        const i = (s + k) % gas.length;
        tank += gas[i] - cost[i];
        if (tank < 0) return `runs dry leaving ${i}`;
    }
    return "makes it round";
}

const gas = [4, 1, 5, 2, 3, 6], cost = [3, 4, 2, 5, 4, 2];
const wrong = start(gas, cost, false), right = start(gas, cost, true);
console.log(`restart at the failing station: ${wrong}, which ${laps(gas, cost, wrong)}; after it: ${right}, which ${laps(gas, cost, right)}`);

const ratings: number[] = [2, 4, 3, 5, 2, 1, 1, 3];   // Candy in one pass, left to right only
const one: number[] = new Array(ratings.length).fill(1);
for (let i = 1; i < ratings.length; i++) if (ratings[i] > ratings[i - 1]) one[i] = one[i - 1] + 1;
const bad = ratings.findIndex((r, i) => i + 1 < ratings.length && r > ratings[i + 1] && one[i] <= one[i + 1]);
console.log(`one pass: ${one.reduce((s, x) => s + x, 0)} candies, but child ${bad}, rated ${ratings[bad]}, gets no more than child ${bad + 1}, rated ${ratings[bad + 1]}`);

// restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
// one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1
using System;
using System.Linq;

class Program {
    static int Start(int[] gas, int[] cost, bool after) {   // Gas Station's one pass; the mistake restarts at the failing station
        int tank = 0, s = 0;
        for (int i = 0; i < gas.Length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                s = after ? i + 1 : i;
                tank = 0;
            }
        }
        return s;
    }

    static string Laps(int[] gas, int[] cost, int s) {   // does a car from s make it round?
        int tank = 0;
        for (int k = 0; k < gas.Length; k++) {
            int i = (s + k) % gas.Length;
            tank += gas[i] - cost[i];
            if (tank < 0) return $"runs dry leaving {i}";
        }
        return "makes it round";
    }

    static void Main() {
        int[] gas = { 4, 1, 5, 2, 3, 6 }, cost = { 3, 4, 2, 5, 4, 2 };
        int wrong = Start(gas, cost, false), right = Start(gas, cost, true);
        Console.WriteLine($"restart at the failing station: {wrong}, which {Laps(gas, cost, wrong)}; after it: {right}, which {Laps(gas, cost, right)}");

        int[] ratings = { 2, 4, 3, 5, 2, 1, 1, 3 };  // Candy in one pass, left to right only
        var one = Enumerable.Repeat(1, ratings.Length).ToArray();
        for (int i = 1; i < ratings.Length; i++) if (ratings[i] > ratings[i - 1]) one[i] = one[i - 1] + 1;
        int bad = Enumerable.Range(0, ratings.Length - 1).First(i => ratings[i] > ratings[i + 1] && one[i] <= one[i + 1]);
        Console.WriteLine($"one pass: {one.Sum()} candies, but child {bad}, rated {ratings[bad]}, gets no more than child {bad + 1}, rated {ratings[bad + 1]}");
    }
}

// restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
// one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1
package main

import "fmt"

func start(gas, cost []int, after bool) int { // Gas Station's one pass; the mistake restarts at the failing station
	tank, s := 0, 0
	for i := range gas {
		tank += gas[i] - cost[i]
		if tank < 0 {
			if after {
				s = i + 1
			} else {
				s = i
			}
			tank = 0
		}
	}
	return s
}

func laps(gas, cost []int, s int) string { // does a car from s make it round?
	tank, n := 0, len(gas)
	for k := 0; k < n; k++ {
		i := (s + k) % n
		tank += gas[i] - cost[i]
		if tank < 0 {
			return fmt.Sprintf("runs dry leaving %d", i)
		}
	}
	return "makes it round"
}

func main() {
	gas, cost := []int{4, 1, 5, 2, 3, 6}, []int{3, 4, 2, 5, 4, 2}
	wrong, right := start(gas, cost, false), start(gas, cost, true)
	fmt.Printf("restart at the failing station: %d, which %s; after it: %d, which %s\n", wrong, laps(gas, cost, wrong), right, laps(gas, cost, right))

	ratings := []int{2, 4, 3, 5, 2, 1, 1, 3} // Candy in one pass, left to right only
	one := make([]int, len(ratings))
	total := 0
	for i := range one {
		one[i] = 1
		if i > 0 && ratings[i] > ratings[i-1] {
			one[i] = one[i-1] + 1
		}
		total += one[i]
	}
	bad := -1
	for i := 0; i+1 < len(ratings) && bad < 0; i++ {
		if ratings[i] > ratings[i+1] && one[i] <= one[i+1] {
			bad = i
		}
	}
	fmt.Printf("one pass: %d candies, but child %d, rated %d, gets no more than child %d, rated %d\n", total, bad, ratings[bad], bad+1, ratings[bad+1])
}

// restart at the failing station: 4, which runs dry leaving 4; after it: 5, which makes it round
// one pass: 11 candies, but child 4, rated 2, gets no more than child 5, rated 1

Restarting at 4, the station that ran dry, gives a car that runs dry leaving 4 at once; the start after it, 5, makes it round. One pass of Candy gives 11 candies, but child 4, rated 2, gets no more than child 5, rated 1: the right pass is what fixes it.

Check yourself

Quiz

1 / 6

Multiple choice

From each square you may jump forward up to its number. Can you reach the last square of [3, 0, 2, 0, 0, 1]?

Practice

The problems in this group, each mapped to the idea it trains:

  1. Jump Game: the farthest reach.
  2. Jump Game II: jumps in layers, one stretch each.
  3. Jump Game VII: a count over a window of starts.
  4. Gas Station: a tank that restarts after it runs dry, and the total.
  5. Valid Parenthesis String: the range of open brackets.
  6. Minimum Add to Make Parentheses Valid: a balance that never goes below 0.
  7. Candy: two passes, the larger of the two.