Two Pointers
A sorted array and a target sum. Two of the values add up to it, and finding which two by trying every pair costs about half of n squared comparisons. At a hundred thousand values the judge stops the program long before the answer arrives.
The array is sorted, and that already pays for something cheaper. Put one index at each end and add the two values. Whatever the comparison says, one of those two indices is finished and can be dropped.
Every step of that walk is in the trace below. The two indices carry markers, and the stretch either one has finished with fades to dots.
const std = @import("std");
/// The problem, as text.
///
/// There is no stdin under WASI in a browser tab, so the four lines a judge
/// would feed the program live in the file instead: the sorted values, the
/// target sums to look for, some words to test for symmetry, and a row of
/// heights for the last section.
const input =
\\2 3 5 8 11 17 20 24
\\25 5 44 31 100 4
\\racecar level abcba noon zig
\\1 8 6 2 5 4 8 3 7
;
/// One line, or an error if the input ran out.
fn readLine(reader: *std.Io.Reader) ![]const u8 {
return (try reader.takeDelimiter('\n')) orelse error.MissingRow;
}
/// Read one line of whitespace-separated integers into `out`.
///
/// The parameter is a `*std.Io.Reader` and not a string, so the same function
/// reads a file on a judge and a literal here. Only the reader passed in
/// changes.
fn readRow(reader: *std.Io.Reader, out: []i32) ![]i32 {
const line = try readLine(reader);
var count: usize = 0;
var fields = std.mem.tokenizeScalar(u8, line, ' ');
while (fields.next()) |field| {
if (count == out.len) return error.RowTooLong;
out[count] = try std.fmt.parseInt(i32, field, 10);
count += 1;
}
return out[0..count];
}
/// Indices of two values that add up to `target`, or null.
///
/// `items` must be sorted, and the sorting is what leaves only one move. The
/// value at `hi` is the largest partner `lo` has left, so a sum below the
/// target says `lo` is in no pair at all and `lo` moves up. The value at `lo`
/// is the smallest partner `hi` has left, so a sum above the target says the
/// same about `hi` and `hi` moves down. Each step drops one index for good,
/// which is what keeps the whole search to a single pass.
fn twoSum(items: []const i32, target: i32) ?[2]usize {
if (items.len < 2) return null;
var lo: usize = 0;
var hi: usize = items.len - 1;
while (lo < hi) {
const sum = items[lo] + items[hi];
if (sum == target) return .{ lo, hi };
if (sum < target) lo += 1 else hi -= 1;
}
return null;
}
/// Right-align a value in a cell of `width` characters.
///
/// A width on a signed integer prints a sign with it, so `{d:>4}` renders 7 as
/// ` +7`. Writing the digits first and padding them by hand keeps the columns
/// free of plus signs nobody asked for.
fn writeCell(out: *std.Io.Writer, value: i32, width: usize) !void {
var digits: [12]u8 = undefined;
const text = try std.mem.print(&digits, "{d}", .{value});
try out.splatByteAll(' ', width - text.len);
try out.writeAll(text);
}
/// The array with the live range drawn in: `>` at `lo`, `<` at `hi`, and a dot
/// for every index the search has already discarded.
fn writeWindow(out: *std.Io.Writer, items: []const i32, lo: usize, hi: usize) !void {
for (items, 0..) |value, i| {
if (i < lo or i > hi) {
try out.writeAll(" .");
} else if (i == lo) {
try out.writeByte('>');
try writeCell(out, value, 3);
} else if (i == hi) {
try writeCell(out, value, 3);
try out.writeByte('<');
} else {
try writeCell(out, value, 4);
}
}
try out.writeByte('\n');
}
const Search = struct { pair: ?[2]usize, steps: usize };
/// The same walk as `twoSum`, printing the pair and the verdict at each step.
///
/// The printing lives here so `twoSum` stays the shape you would paste into a
/// solution. The step count comes back with the answer, because the count is
/// the claim worth checking: it never reaches the length of the array.
fn traceTwoSum(out: *std.Io.Writer, items: []const i32, target: i32) !Search {
if (items.len < 2) return .{ .pair = null, .steps = 0 };
var lo: usize = 0;
var hi: usize = items.len - 1;
var steps: usize = 0;
while (lo < hi) {
const sum = items[lo] + items[hi];
steps += 1;
try out.print(" step {d} ", .{steps});
try writeCell(out, items[lo], 2);
try out.writeAll(" + ");
try writeCell(out, items[hi], 2);
try out.writeAll(" = ");
try writeCell(out, sum, 3);
const verdict = if (sum == target) "match" else if (sum < target) "too small" else "too big";
try out.print(" {s}", .{verdict});
try out.splatByteAll(' ', 11 - verdict.len);
try writeWindow(out, items, lo, hi);
if (sum == target) return .{ .pair = .{ lo, hi }, .steps = steps };
if (sum < target) lo += 1 else hi -= 1;
}
return .{ .pair = null, .steps = steps };
}
/// True when `text` reads the same in both directions.
///
/// The movement is the one above with the comparison changed. Equal bytes at
/// the two ends settle both positions at once, so both indices move and the
/// untested middle shrinks by two. A mismatch ends the walk, because the pair
/// that failed is a pair in every reading of the string.
fn isPalindrome(text: []const u8) bool {
if (text.len == 0) return true;
var lo: usize = 0;
var hi: usize = text.len - 1;
while (lo < hi) {
if (text[lo] != text[hi]) return false;
lo += 1;
hi -= 1;
}
return true;
}
/// `isPalindrome` with the settled bytes printed as dots.
fn tracePalindrome(out: *std.Io.Writer, text: []const u8) !bool {
if (text.len == 0) return true;
var lo: usize = 0;
var hi: usize = text.len - 1;
var steps: usize = 0;
while (lo < hi) {
steps += 1;
const matched = text[lo] == text[hi];
try out.print(" step {d} {c} {s} {c} ", .{
steps,
text[lo],
if (matched) "=" else "!",
text[hi],
});
var row_buf: [256]u8 = undefined;
var row: std.Io.Writer = .fixed(&row_buf);
for (text, 0..) |byte, i| {
if (i < lo or i > hi) {
try row.writeAll(" . ");
} else if (i == lo) {
try row.print(">{c} ", .{byte});
} else if (i == hi) {
try row.print(" {c}<", .{byte});
} else {
try row.print(" {c} ", .{byte});
}
}
try out.writeAll(std.mem.trimEnd(u8, row.buffered(), " "));
try out.writeByte('\n');
if (!matched) return false;
lo += 1;
hi -= 1;
}
try out.print(" {d} steps, nothing left to pair\n", .{steps});
return true;
}
const Area = struct { best: i32, lo: usize, hi: usize };
/// The largest rectangle between two of `heights`, water held between two
/// walls on a flat floor.
///
/// The area is the shorter wall times the distance, so the shorter wall is the
/// one that limits it. Every pair still containing that wall is narrower than
/// the pair just measured and no taller, so none of them can beat it, and the
/// wall can be dropped. The trace prints the side that moved.
fn maxArea(out: *std.Io.Writer, heights: []const i32) !Area {
if (heights.len < 2) return .{ .best = 0, .lo = 0, .hi = 0 };
var lo: usize = 0;
var hi: usize = heights.len - 1;
var found: Area = .{ .best = 0, .lo = 0, .hi = 0 };
var steps: usize = 0;
while (lo < hi) {
const height = @min(heights[lo], heights[hi]);
const width: i32 = @intCast(hi - lo);
const area = height * width;
if (area > found.best) found = .{ .best = area, .lo = lo, .hi = hi };
steps += 1;
const shorter_is_left = heights[lo] < heights[hi];
try out.print(" {d:>4} {d:>3} {d:>3}", .{ steps, lo, hi });
try writeCell(out, heights[lo], 6);
try writeCell(out, heights[hi], 6);
try writeCell(out, width, 7);
try writeCell(out, area, 6);
try writeCell(out, found.best, 6);
try out.print(" {s}\n", .{if (shorter_is_left) "lo" else "hi"});
if (shorter_is_left) lo += 1 else hi -= 1;
}
return found;
}
pub fn main(init: std.process.Init) !void {
var buf: [4096]u8 = undefined;
var file_writer = std.Io.File.stdout().writerStreaming(init.io, &buf);
const out = &file_writer.interface;
var reader: std.Io.Reader = .fixed(input);
var value_storage: [64]i32 = undefined;
var target_storage: [64]i32 = undefined;
var height_storage: [64]i32 = undefined;
const values = try readRow(&reader, &value_storage);
const targets = try readRow(&reader, &target_storage);
const words = try readLine(&reader);
const heights = try readRow(&reader, &height_storage);
try out.print("{d} sorted values parsed from the input\n", .{values.len});
try out.writeAll(" idx ");
for (0..values.len) |i| try out.print("{d:>4}", .{i});
try out.writeAll("\n val ");
for (values) |v| try writeCell(out, v, 4);
try out.writeAll("\n\n");
// The traced walk, and the untraced one it has to agree with.
try out.writeAll("two values that add up to 25\n");
const traced = try traceTwoSum(out, values, 25);
const pair = traced.pair.?;
try out.print(
" items[{d}] + items[{d}] = {d} + {d} = 25 in {d} steps\n",
.{ pair[0], pair[1], values[pair[0]], values[pair[1]], traced.steps },
);
try out.print(
" plain twoSum agrees -> {}\n\n",
.{std.meta.eql(twoSum(values, 25), traced.pair)},
);
// One step retires one index, so the step count is bounded by the length
// of the array however the values fall.
try out.writeAll("every target, with the steps it cost\n");
try out.writeAll(" target pair values steps\n");
var sink: std.Io.Writer.Discarding = .init(&.{});
var worst: usize = 0;
for (targets) |target| {
const found = try traceTwoSum(&sink.writer, values, target);
worst = @max(worst, found.steps);
try writeCell(out, target, 8);
if (found.pair) |p| {
try out.print(" {d:>2},{d:>2} ", .{ p[0], p[1] });
try writeCell(out, values[p[0]], 2);
try out.writeAll(" +");
try writeCell(out, values[p[1]], 3);
} else {
try out.writeAll(" - -");
}
try out.print(" {d:>5}\n", .{found.steps});
}
try out.print(" one index retires per step, so {d} values allow {d} steps at most\n", .{
values.len,
values.len - 1,
});
try out.print(" the worst row above took {d}\n\n", .{worst});
// The same movement over bytes.
try out.writeAll("racecar, checked from both ends\n");
const symmetric = try tracePalindrome(out, "racecar");
try out.print(" palindrome -> {}\n\n", .{symmetric});
try out.writeAll("zig, where the first pair already answers it\n");
const asymmetric = try tracePalindrome(out, "zig");
try out.print(" palindrome -> {}\n\n", .{asymmetric});
try out.writeAll("every word on the third input line\n");
var word_fields = std.mem.tokenizeScalar(u8, words, ' ');
while (word_fields.next()) |word| {
try out.print(" {s:<9}{}\n", .{ word, isPalindrome(word) });
}
try out.writeAll("\n");
// Discarding a candidate needs an argument, not a hunch. Here it is the
// shorter wall that can be thrown away.
try out.writeAll("most water between two walls\n");
try out.writeAll(" step lo hi h[lo] h[hi] width area best moved\n");
const water = try maxArea(out, heights);
try out.print(" best {d} between index {d} and index {d}\n", .{
water.best,
water.lo,
water.hi,
});
try out.flush();
}Only one index can move
/// Indices of two values that add up to `target`, or null.
///
/// `items` must be sorted, and the sorting is what leaves only one move. The
/// value at `hi` is the largest partner `lo` has left, so a sum below the
/// target says `lo` is in no pair at all and `lo` moves up. The value at `lo`
/// is the smallest partner `hi` has left, so a sum above the target says the
/// same about `hi` and `hi` moves down. Each step drops one index for good,
/// which is what keeps the whole search to a single pass.
fn twoSum(items: []const i32, target: i32) ?[2]usize {
if (items.len < 2) return null;
var lo: usize = 0;
var hi: usize = items.len - 1;
while (lo < hi) {
const sum = items[lo] + items[hi];
if (sum == target) return .{ lo, hi };
if (sum < target) lo += 1 else hi -= 1;
}
return null;
}lo and hi bracket the values still in play. Everything outside
items[lo..hi + 1] has been ruled out already. Take the sum of the two values
they point at. Three things can happen and none of them leaves a choice.
The sum equals the target, and the search is over.
The sum is below the target. Everything above hi is already gone, so
items[hi] is the largest partner lo has left, and even that pairing came up
short. No pair containing lo reaches the target. lo is finished, and
lo += 1 drops it.
The sum is above the target. The mirror image holds. items[lo] is the
smallest partner hi has left and the sum is still too big, so hi belongs to
no pair either and hi -= 1 drops it.
Every step removes exactly one index, and no index ever comes back. hi - lo
starts at items.len - 1 and falls by one per step. The loop therefore runs
fewer times than the array has values. One comparison per index, against one
comparison per pair.
The argument leans on the sorting twice, once at each end, and an unsorted
array breaks both halves at once: a large value sitting in the middle is
exactly what the reasoning assumed could not be there. Nothing in the function
checks, so sort first.
Sorting covers std.mem.sort and the
comparator it takes.
Both indices here move towards each other and stop when they meet. Two indices moving the same way, with a contiguous stretch of the array held between them, answer a different family of questions and rest on a different argument: Sliding Window.
What the search throws away
/// The same walk as `twoSum`, printing the pair and the verdict at each step.
///
/// The printing lives here so `twoSum` stays the shape you would paste into a
/// solution. The step count comes back with the answer, because the count is
/// the claim worth checking: it never reaches the length of the array.
fn traceTwoSum(out: *std.Io.Writer, items: []const i32, target: i32) !Search {
if (items.len < 2) return .{ .pair = null, .steps = 0 };
var lo: usize = 0;
var hi: usize = items.len - 1;
var steps: usize = 0;
while (lo < hi) {
const sum = items[lo] + items[hi];
steps += 1;
try out.print(" step {d} ", .{steps});
try writeCell(out, items[lo], 2);
try out.writeAll(" + ");
try writeCell(out, items[hi], 2);
try out.writeAll(" = ");
try writeCell(out, sum, 3);
const verdict = if (sum == target) "match" else if (sum < target) "too small" else "too big";
try out.print(" {s}", .{verdict});
try out.splatByteAll(' ', 11 - verdict.len);
try writeWindow(out, items, lo, hi);
if (sum == target) return .{ .pair = .{ lo, hi }, .steps = steps };
if (sum < target) lo += 1 else hi -= 1;
}
return .{ .pair = null, .steps = steps };
}> sits at lo, < sits at hi, and a dot is an index the walk has already
finished with:
step 1 2 + 24 = 26 too big > 2 3 5 8 11 17 20 24<
step 2 2 + 20 = 22 too small > 2 3 5 8 11 17 20< .
step 3 3 + 20 = 23 too small .> 3 5 8 11 17 20< .
step 4 5 + 20 = 25 match . .> 5 8 11 17 20< .Step one drops 24 from the right. Step two overshoots in the other direction and drops 2 from the left. The live range closes from whichever side the last comparison pointed at, which is why the dots at the two ends do not grow at the same rate.
Running the same walk for every target on the second input line gives the cost of each search:
target pair values steps
25 2, 6 5 + 20 4
5 0, 1 2 + 3 7
44 6, 7 20 + 24 7
31 4, 6 11 + 20 6
100 - - 7
4 - - 7Nothing costs more than seven steps over eight values, including the two targets with no answer. The array cannot make a sum below 5 or above 44, so 4 and 100 are out of reach. A failing search learns that the way a successful one finds its pair, by walking until the indices meet.
The same walk over bytes
/// True when `text` reads the same in both directions.
///
/// The movement is the one above with the comparison changed. Equal bytes at
/// the two ends settle both positions at once, so both indices move and the
/// untested middle shrinks by two. A mismatch ends the walk, because the pair
/// that failed is a pair in every reading of the string.
fn isPalindrome(text: []const u8) bool {
if (text.len == 0) return true;
var lo: usize = 0;
var hi: usize = text.len - 1;
while (lo < hi) {
if (text[lo] != text[hi]) return false;
lo += 1;
hi -= 1;
}
return true;
}Swap the sum for an equality test and the movement carries over to a string read from both ends. A match settles two positions at once, so both indices move and the untested middle loses two bytes per step:
step 1 r = r >r a c e c a r<
step 2 a = a . >a c e c a< .
step 3 c = c . . >c e c< . .
3 steps, nothing left to pairSeven bytes and three steps. The e in the middle needs no partner, and
while (lo < hi) walks past it without a case of its own.
A mismatch is an answer by itself:
step 1 z ! g >z i g<The pair that failed appears in every reading of the string, so no later comparison can rescue it, and the function returns on the spot.
The comparison is a byte comparison. For ASCII the byte pairs and the character
pairs are the same pairs. été reads the same in both directions and its five
bytes do not, because the leading byte of a two-byte character never equals the
byte that follows it. Anything beyond ASCII needs the string decoded first.
Throwing a candidate away needs an argument
/// The largest rectangle between two of `heights`, water held between two
/// walls on a flat floor.
///
/// The area is the shorter wall times the distance, so the shorter wall is the
/// one that limits it. Every pair still containing that wall is narrower than
/// the pair just measured and no taller, so none of them can beat it, and the
/// wall can be dropped. The trace prints the side that moved.
fn maxArea(out: *std.Io.Writer, heights: []const i32) !Area {
if (heights.len < 2) return .{ .best = 0, .lo = 0, .hi = 0 };
var lo: usize = 0;
var hi: usize = heights.len - 1;
var found: Area = .{ .best = 0, .lo = 0, .hi = 0 };
var steps: usize = 0;
while (lo < hi) {
const height = @min(heights[lo], heights[hi]);
const width: i32 = @intCast(hi - lo);
const area = height * width;
if (area > found.best) found = .{ .best = area, .lo = lo, .hi = hi };
steps += 1;
const shorter_is_left = heights[lo] < heights[hi];
try out.print(" {d:>4} {d:>3} {d:>3}", .{ steps, lo, hi });
try writeCell(out, heights[lo], 6);
try writeCell(out, heights[hi], 6);
try writeCell(out, width, 7);
try writeCell(out, area, 6);
try writeCell(out, found.best, 6);
try out.print(" {s}\n", .{if (shorter_is_left) "lo" else "hi"});
if (shorter_is_left) lo += 1 else hi -= 1;
}
return found;
}Read the numbers as walls standing on a flat floor. Water poured between two of
them reaches the height of the shorter wall and spans the gap. The area is
@min(heights[lo], heights[hi]) * (hi - lo).
The ends of the array are the widest pair available, and every later pair is narrower. A step is only worth taking if it buys height in exchange, and that settles which wall to drop. Take the shorter of the two. Any other pair containing that wall is narrower than the pair just measured and no taller than the wall itself. Its area is therefore below the number already recorded. The shorter wall cannot appear in the answer, so dropping it costs nothing:
step lo hi h[lo] h[hi] width area best moved
1 0 8 1 7 8 8 8 lo
2 1 8 8 7 7 49 49 hi
3 1 7 8 3 6 18 49 hi
4 1 6 8 8 5 40 49 hiStep two records 49, and the four rows the program prints after these never
beat it. Note step four, where the two walls are the same height. The argument
then applies to both of them, so either one may go, and the code drops hi
only because < had to be written one way round.
Dropping the taller wall instead would compile and would sometimes agree. There is no argument behind it, and the pair it discards can be the answer.