LeetCode in Ruby: test the invariant behind three useful patterns

A solution works for the sample, then fails on an empty array or a repeated value. Often the missing piece is not another Ruby trick. It is a sentence describing what remains true after each loop iteration.

This lab implements three recurring interview patterns: lower-bound binary search, a sliding window and a min-heap. Each has an explicit invariant, boundary tests and a small independent oracle. The purpose is to make mistakes observable before submitting a solution, not to promise that memorizing three templates covers a particular percentage of LeetCode.

Binary search: return a boundary, not just a match

Lower bound finds the first index whose value is at least the target. If none exists, it returns the array's length. This handles duplicates naturally and is useful even when an exact match is absent.

def lower_bound(values, target)
  left, right = 0, values.length
  while left < right
    middle = left + (right - left) / 2
    if values[middle] < target
      left = middle + 1
    else
      right = middle
    end
  end
  left
end

The candidate boundary lies in the closed interval from left to right, while the inspected elements occupy the half-open range before right. Initially that boundary can be anywhere from zero to length. Values strictly before left are too small; values at or beyond right, when present, are large enough.

When the middle value is too small, the answer must be after it, so left becomes middle plus one. Otherwise middle remains a possible answer, so right becomes middle. Each update shrinks the interval. When the endpoints meet, the boundary is determined.

An empty array needs no special branch: both endpoints are zero and the loop never runs. For [1, 1, 4], searching for one returns zero, searching for three returns two, and searching for five returns three.

The precondition is sorted input. Checking that on every call would add linear work and obscure the logarithmic search itself. Validate sorting where the data is constructed if the surrounding application cannot guarantee it.

Sliding window: never move the left edge backward

For the longest substring without repeated characters, remember the latest position of each character:

def longest_unique_length(text)
  last_seen = {}
  left = 0
  best = 0
  text.each_char.with_index do |char, right|
    previous = last_seen[char]
    left = [left, previous + 1].max if previous
    last_seen[char] = right
    best = [best, right - left + 1].max
  end
  best
end

The active window contains no duplicate characters. When a character repeats inside it, move left just past that character's previous position. If the previous occurrence is already outside the window, leave left where it is.

The max operation expresses that second case. Remove it and "abba" becomes a useful counterexample: after the second b moves left forward, the final a must not drag left back to its old position.

The code uses Ruby character iteration, so a multibyte character such as é is not counted as several bytes. That still does not define user-perceived characters: a base letter and combining mark may be separate iteration elements. The String reference distinguishes character and grapheme operations. Match the unit to the problem statement rather than calling every string length a character count.

With a last-seen Hash, the loop performs one pass and uses storage proportional to distinct characters. Those are algorithmic descriptions under ordinary Hash lookup assumptions, not measured latency promises for every Ruby implementation.

Heap: repair one path after each change

The downloadable MinHeap supports Integer values. Its invariant is that each parent is no greater than either child. Push appends at the end and moves the new value toward the root until the invariant holds.

Pop first checks the empty case, returning nil. It removes the final element, returns immediately for a former singleton, and otherwise moves that final value to the root. Repeatedly swapping with the smaller child repairs the one affected downward path.

Those early cases prevent the empty-array negative-index mistakes that can hide in a compact implementation. Duplicates and negative integers are valid. Nil is not a stored value, so nil unambiguously means that the heap was empty.

The tree height grows logarithmically with its size. Each push or nonempty pop follows at most one root-to-leaf path; there is no need to sort the entire collection after each operation. The tests intentionally use a sorted array as a slower, simpler comparison.

Give the tests a different route to the answer

For binary search, the oracle scans from the start for the first qualifying value. One hundred generated sorted arrays and targets are checked against it.

For the window, the oracle enumerates every substring of a short generated string and checks whether its characters are unique. This is inefficient but easy to inspect. The optimized method is compared against it on another hundred cases.

For the heap, two hundred seeded push/pop decisions are mirrored in a sorted array. Each pop must agree, and draining the remaining heap must reproduce the remaining sorted contents. Fixed seeds make failures reproducible. The bounded cases supplement reasoning; they do not prove correctness for all inputs.

A Ruby-specific default worth checking

The lab also calls a method with an omitted items = [] argument twice. Ruby creates a fresh default array for each call. Passing the same explicit array twice does share mutations. Do not import another language's default-argument warning without testing the target language.

This is a small example of a broader habit: separate language semantics from algorithmic assumptions. A correct invariant can still be undermined by an incorrect belief about indexing, mutation or text encoding.

Run the checks

Download the complete algorithms and tests. They were run with Ruby 3.3.2 and Minitest 6.0.6; install that exact test gem version if missing.

ruby example.rb --seed 42

The local result was 7 tests and 316 assertions, with no failures or errors. No online judge was contacted. Before adapting a pattern to a new problem, write its precondition and invariant first, then choose the smallest input that would expose a violation.