In a deque-based symmetry check that pops both ends, why must the loop stop with one element left?

## The setup A lab tool screens candidate DNA restriction-site strings for two-ended symmetry: the sequence must read identically inward from both ends. Loading the characters into a deque and repeatedly popping one from each end is the natural formulation, because the deque is exactly the structure whose cheap operations are "take from the front" and "take from the back". The loop body is fixed: pop one element from each end and compare them. The only real design decision is the **stopping condition**, and that is where the boundary bug lives. ## Why `size > 0` is wrong Consider a site string of odd length, say five characters. Four iterations at two elements each would consume the whole thing, but the loop consumes two per pass, so after two passes exactly one element remains. With a `size > 0` condition the loop runs a third time: 1. the front pop removes the last remaining element and the deque becomes empty; 2. the back pop is now issued against an **empty** deque. What happens next depends on the deque, and every outcome is bad. A strict implementation raises an underflow error, so a perfectly valid odd-length site is reported as a crash rather than a result. A permissive one returns a sentinel, which then compares unequal to the real character and reports a valid symmetric site as asymmetric — a silent wrong answer, the worse failure. Neither is a property of the algorithm; both are the stopping condition being off by one element. ## Why `size > 1` is right ``` # d holds the site's characters, front to back while size(d) > 1 left = pop_front(d) right = pop_back(d) if left != right return false return true ``` The condition guarantees the two pops in the body always have distinct elements to take. It also gets the three input classes right without any special-casing: - **Even length.** The deque shrinks by two per pass and reaches size 0 exactly. The loop exits, every pair matched, the answer is true. - **Odd length.** The deque reaches size 1 and the loop exits with the middle element still inside. That is correct: a middle element is compared against itself under the symmetry definition, so it can never disqualify the input. Leaving it untested is not a shortcut, it is the right semantics. - **Empty input.** The loop body never runs and the function returns true. Emptiness is vacuously symmetric — there is no pair that disagrees. Interviewers do ask what your code returns for empty input, and "true, vacuously" with the reason is the answer that lands. - **Single element.** Same path as empty: the condition is false immediately, true is returned. ## The invariant, stated properly A good candidate names the invariant rather than tracing examples: **at the top of every iteration, all pairs removed so far have compared equal, and the elements still in the deque form a contiguous middle segment of the original sequence whose own symmetry decides the whole result.** That is why removing a matched pair is a sound reduction — it strictly shrinks the problem to a smaller instance of the same problem — and why the base cases (zero or one element remaining) are true rather than undefined. ## Cost, and the honest caveat Time is O(n): each element is pushed once and popped once, and the comparison is constant. Space is **O(n) extra**, and this is the part candidates skip. Copying the sequence into a deque duplicates it. If you already have random access to the sequence, walking two indices inward from the two ends decides the same question in O(1) extra space, and an interviewer will often ask you to justify the copy. The deque version still earns its place in two situations. First, when the input arrives as a one-pass stream you cannot index — you must materialize it anyway, and a deque materializes it in the shape the algorithm wants. Second, when the elements need normalizing or filtering on the way in (dropping separators, folding case, rejecting characters outside the alphabet); you build the cleaned sequence once during the load and the comparison loop stays trivial. Saying "the copy costs O(n) space, and here is when that is worth paying" is the difference between reciting a technique and judging it. ## The failure modes to watch for Beyond the stopping condition: comparing the *peeks* but forgetting to pop, which loops forever; popping both from the same end, which compares neighbours rather than mirrors and accepts only sequences of one repeated element; and returning false on empty input because "there is nothing to compare", which is a convention error rather than a logic error but still contradicts the definition.