awelgorithms

Empty window versus one-cell window

Updated

Empty is R < L, often R = L-1 or the sentinel R = -1 with L = 0. One-cell is L == R. They are different: one-cell has a[L], empty has no cell.

What to focus on

Length 0 vs length 1. Do not read a[L] on empty. Shrinking a one-cell window produces empty (L becomes R+1), not another one-cell. The array itself is nonempty. Emptiness is a window state.

Worked examples

one cell

a = [4, 1, 9], L=2 R=2
  1. L == R
  2. covers index 2
  3. a[2] = 9

Result: [9] · length 1

empty by R < L

a = [4, 1, 9], L=2 R=1
  1. R = L-1
  2. covers no index
  3. do not read a[2]

Result: empty · length 0

sentinel empty

a = [7], L=0 R=-1
  1. R = -1 is the empty sentinel at the left
  2. index 0 is not in the window yet

Result: empty · length 0

Try it

Write describe(L, R). L is the left index. R is the right index. Empty is R < L. One-cell is L == R. The window includes a[L..R] only when L ≤ R. Print length and whether a cell is readable. Do not read a[L] on empty. On a=[4, 1, 9] with (2, 2) and (2, 1); a=[7] with (0, 0) and (0, -1).

a is nonempty. The window may be empty (R < L) or one cell (L == R).