Arrays & Windows

Arrays, two pointers, windows, and locality

Arrays give contiguous storage, predictable footprint, cache-friendly traversal, and simple serialization. Two-pointer, prefix, sliding-window, monotonic-deque, and in-place partition patterns solve a wide range of streaming problems without per-element allocation.

The best embedded data structure is often a plain array plus a carefully maintained logical length. Contiguous storage minimizes metadata and pointer chasing, works naturally with DMA, and lets the linker account for every byte. Capacity and current length must be separate concepts.

A sliding window avoids recomputing a property for every position. Sum can update by subtracting the outgoing value and adding the incoming one. Maximum needs a monotonic deque of candidate indices: each index enters and leaves once, producing O(n) total work and O(k) workspace.

In-place algorithms trade scratch memory for mutation complexity. memmove chooses copy direction from overlap; dedup uses a read index and a write index; Dutch partition maintains three regions. The proof is a loop invariant describing which prefix or suffix is already final.

Patterns and when they apply

read/write cursors

Compaction, filtering, escaping, and deduplication. Cost: O(n), constant extra storage. Avoid when: Publishing new length before writes complete.

monotonic deque

Window minima/maxima and stable-range constraints. Cost: O(n) time, O(k) caller workspace. Avoid when: Storing values when duplicate indices matter.

three-way partition

Classify events or samples in one pass. Cost: Destroys within-class order. Avoid when: Using it when stable order is required.

Sliding maximum

1. Drop deque-front indices that left the window.
2. Drop deque-back indices whose values cannot beat the new sample.
3. Append the new index.
4. Once the first full window exists, emit the value at the front index.

Every index is pushed and popped at most once, giving linear total work.

Checklist

• Can input and output overlap?
• Is stable order required?
• What happens for n==0 or k>n?
• Does an accumulator need a wider type?
• Is caller workspace large enough?

Easy - In-Place Sample Deduplication

Compressing a burst of ADC samples in place before writing them to flash or shipping them over a slow radio link.

Remove consecutive duplicate ADC samples in place and return the new length. Preserve the first value in each run.

In-place run deduplication with a read/write pair

Collapses consecutive equal samples in place, keeping the first of each run, and returns the new length. len 0 or NULL samples yields 0. Memory beyond the returned length is unspecified.

#include <stddef.h>
#include <stdint.h>

size_t dedup_runs(uint16_t *samples, size_t len) {
    if (samples == NULL || len == 0u) {
        return 0u;
    }
    size_t w = 1u;  /* write cursor: next slot a keeper goes into */
    for (size_t r = 1u; r < len; r++) {
        /* Keep a sample only when it differs from the previous kept one.
           samples[w-1] is always the last surviving value. */
        if (samples[r] != samples[w - 1u]) {
            samples[w] = samples[r];
            w++;
        }
    }
    return w;
}

• Two cursors walk the same array: r reads every sample, w marks where the next distinct value belongs. Because w never passes r, overwriting is safe — you only clobber values you have already decided about.
• Comparing against samples[w-1] (the last kept value) instead of samples[r-1] is the key detail: after a run of duplicates the previous raw sample equals the current one anyway, but the kept-value comparison stays correct even in tricky interleavings.
• The first element is always kept, so w starts at 1 and the loop starts at r = 1; empty input is rejected up front so w-1 can never underflow.
• One pass, no extra buffer: this is the canonical O(n)/O(1) in-place compression pattern used for ADC burst logs.

Cases the tests must cover

• [1,1,2,2,2,3,1] → [1,2,3,1], length 4 (non-consecutive repeats survive)
• [5,5,5,5] → [5], length 1
• [1,2,3] unchanged, length 3
• len 0 and NULL both return 0
• Single element returns 1 unmodified

How it gets written wrong

• Comparing samples[r] with samples[r-1] works here but teaches a fragile habit; comparing with the last kept value generalizes to all in-place filters.
• Writing samples[w++] before the comparison, which duplicates the first element of each run.
• Returning len instead of w so callers log stale tail data.

Medium - Sliding Peak Detector

Peak detection over a sliding window: envelope tracking on an audio stream, spike detection on a current sensor, or windowed maxima for an AGC loop.

For every window of k ADC samples, output the maximum. Use a caller-provided index buffer and perform no dynamic allocation.

Monotonic-deque sliding maximum

Writes one maximum for each complete window. Caller supplies k index slots; input and output must not overlap.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool sliding_max(const int16_t *in,size_t n,size_t k,
                 int16_t *out,size_t out_cap,size_t *deque,
                 size_t deque_cap,size_t *written){
    if(!written)return false;
    *written=0u;
    if(k==0u||k>n)return true;
    size_t need=n-k+1u;
    if(!in||!out||!deque||out_cap<need||deque_cap<k)return false;
    size_t front=0u,count=0u;
    for(size_t i=0u;i<n;++i){
        while(count>0u&&deque[front]+k<=i){front=(front+1u)%deque_cap;--count;}
        while(count>0u){
            size_t back=(front+count-1u)%deque_cap;
            if(in[deque[back]]>in[i])break;
            --count;
        }
        deque[(front+count)%deque_cap]=i; ++count;
        if(i+1u>=k)out[(*written)++]=in[deque[front]];
    }
    return true;
}

• Deque indices always increase logically and remain inside the current window.
• Their values decrease from front to back, so the front is the maximum.
• A circular k-slot index deque keeps fixed workspace while every index enters and leaves once.

Cases the tests must cover

• k zero and k>n
• k one
• duplicates
• strictly rising/falling
• negative samples
• insufficient output/deque capacity

How it gets written wrong

• Define aliasing policy explicitly; this version requires disjoint input/output.
• Modulo may be expensive on tiny MCUs; a power-of-two deque can use a validated mask.

Easy - Median-of-Three Filter

Removing single-sample spikes from a noisy sensor before it reaches a control loop - the standard first line of defence on a mechanically noisy ADC input.

Apply a median-of-three filter to a sample array. Define the first and last output values without reading outside the buffer.

Median-of-three spike filter

out[i] is the median of in[i-1], in[i], in[i+1]. Endpoints replicate the nearest interior median-free value: out[0]=in[0], out[n-1]=in[n-1]. n<3 copies input verbatim. in and out may be the same buffer.

#include <stddef.h>
#include <stdint.h>

static int16_t med3(int16_t a, int16_t b, int16_t c) {
    /* The median is the value that is neither the max nor the min:
       sum all three and subtract the extremes. int32_t avoids overflow. */
    int32_t sum = (int32_t)a + (int32_t)b + (int32_t)c;
    int32_t hi = a > b ? a : b; hi = hi > c ? hi : c;
    int32_t lo = a < b ? a : b; lo = lo < c ? lo : c;
    return (int16_t)(sum - hi - lo);
}

void median3(const int16_t *in, int16_t *out, size_t n) {
    if (in == NULL || out == NULL || n == 0u) return;
    if (n < 3u) {  /* not enough context to filter: pass through */
        for (size_t i = 0u; i < n; i++) out[i] = in[i];
        return;
    }
    out[0] = in[0];  /* defined endpoints: no read outside the buffer */
    for (size_t i = 1u; i + 1u < n; i++) {
        out[i] = med3(in[i - 1u], in[i], in[i + 1u]);
    }
    out[n - 1u] = in[n - 1u];
}

• A median filter kills single-sample spikes (ESD glitches, ADC bit errors) without the phase smear of a moving average, because it picks the middle value instead of blending.
• The sum-minus-extremes trick finds the median with three compares and no branching sort; widening to int32_t first keeps -32768 + -32768 + -32768 from wrapping.
• Endpoints have no left/right neighbor, so the contract defines them as pass-through copies. Filtering them with a fabricated neighbor would invent data.
• Because each output depends only on inputs at i-1..i+1 and out[i] is written after in[i] was read for its own window, in-place operation (in == out) is safe as long as the caller accepts that windows after position i see filtered earlier values; pass separate buffers when that matters.

Cases the tests must cover

• [0, 100, 0] → [0, 0, 0] (spike removed)
• [1, 2, 3, 4] → [1, 2, 3, 4] (monotonic data untouched)
• [-32768, -32768, -32768] → -32768 without overflow
• n = 2 copies both samples
• First and last outputs always equal first and last inputs

How it gets written wrong

• Computing the median with (a+b+c) in int16_t — overflow on large negative triples.
• Reading in[i+1] at i == n-1, a one-past-the-end read that crashes on MPU-guarded buffers.
• Sorting three elements with a swap network and getting an endpoint case wrong; the arithmetic form has no ordering bugs.

Medium - Longest Stable Sensor Window

Deciding when a sensor has settled: waiting for a scale to stabilise, a temperature to plateau, or a motor to reach steady state before acting on the reading.

Find the longest contiguous range whose maximum minus minimum is at most tolerance. Return start and length.

Longest window with bounded spread (two deques)

Returns the start and length of the longest contiguous range where max-min <= tolerance. Caller provides scratch storage for two index deques of n entries. Empty input yields {0,0}.

#include <stddef.h>
#include <stdint.h>

typedef struct { size_t start; size_t len; } range_t;

range_t longest_stable(const int16_t *samples, size_t n,
                       uint16_t tolerance, size_t *scratch) {
    range_t best = { 0u, 0u };
    if (samples == NULL || n == 0u) return best;
    /* scratch[0..n)   = deque of indices with decreasing values (front = max)
       scratch[n..2n)  = deque of indices with increasing values (front = min) */
    size_t *maxq = scratch;
    size_t *minq = scratch + n;
    size_t maxh = 0u, maxt = 0u, minh = 0u, mint = 0u;
    size_t lo = 0u;
    for (size_t hi = 0u; hi < n; hi++) {
        while (maxt > maxh && samples[maxq[maxt - 1u]] <= samples[hi]) maxt--;
        maxq[maxt++] = hi;
        while (mint > minh && samples[minq[mint - 1u]] >= samples[hi]) mint--;
        minq[mint++] = hi;
        /* Shrink from the left while the window violates the spread. */
        while (samples[maxq[maxh]] - samples[minq[minh]] > (int16_t)tolerance) {
            lo++;
            if (maxq[maxh] < lo) maxh++;
            if (minq[minh] < lo) minh++;
        }
        if (hi - lo + 1u > best.len) {
            best.start = lo;
            best.len = hi - lo + 1u;
        }
    }
    return best;
}

• Brute force checks every (start, end) pair in O(n^2) or worse. The sliding window keeps a valid range [lo, hi] and only ever moves both ends forward, giving O(n).
• Two monotonic deques track the window max and min: the max-deque stores indices of strictly decreasing values so its front is always the maximum; the min-deque mirrors it. Each index enters and leaves each deque once — the amortized O(1) per sample.
• When max - min exceeds tolerance, lo advances until the window is legal again; deque entries that fell behind lo are lazily discarded from the fronts.
• The subtraction is done in int (both operands are int16_t, difference fits in int), and tolerance is compared as a non-negative value, so no unsigned wrap can fake a small spread.
• Scratch is caller-owned so the function is heap-free; each deque needs at most n entries because every index appears at most once.

Cases the tests must cover

• [1,2,3,10,2,3] tol 2 → window [1,2,3] or [2,3] of length 3
• Constant array, tol 0 → whole array
• Strictly rising by 5 each step, tol 3 → every window length 1
• Single element returns {0,1}
• Alternating extremes [0,100,0,100] tol 10 → length 1

How it gets written wrong

• Using strict vs non-strict comparisons inconsistently between the two deques, which breaks the monotonic invariant.
• Subtracting int16_t values in unsigned arithmetic — (0 - 100) wraps huge and the spread test never fires.
• Forgetting to drop deque fronts that slid left of lo, resurrecting stale extrema.
• Allocating the deques with malloc inside a function the sheet requires to run on caller storage.

Medium - Implement memmove

Shifting a buffer in place - consuming the front of a receive buffer and moving the tail down, which every parser that keeps a partial frame does.

Copy n bytes correctly when source and destination overlap. Do not call memcpy, memmove, or allocate temporary storage.

Overlap-safe byte move

Copies n bytes as if through a temporary array, including overlapping source/destination ranges.

#include <stddef.h>
#include <stdint.h>

void *rb_memmove(void *dst, const void *src, size_t n) {
    unsigned char *d = (unsigned char *)dst;
    const unsigned char *s = (const unsigned char *)src;
    if (d == s || n == 0u) return dst;
    uintptr_t da = (uintptr_t)d;
    uintptr_t sa = (uintptr_t)s;
    if (da < sa || (da > sa && da - sa >= n)) {
        for (size_t i = 0u; i < n; ++i) d[i] = s[i];
    } else {
        for (size_t i = n; i != 0u; --i) d[i - 1u] = s[i - 1u];
    }
    return dst;
}

• Numeric byte addresses avoid relational comparison of unrelated pointers in the overlap decision.
• When destination starts inside the source range, copy backward so unread bytes are not overwritten.
• unsigned char may inspect and copy object representation bytes.

Cases the tests must cover

• no overlap
• dst==src
• overlap left
• overlap right
• n==0

How it gets written wrong

• Pointer-to-uintptr_t mapping is implementation-defined and uintptr_t is optional; this model targets embedded implementations that provide meaningful flat byte addresses.
• Both ranges must be valid for n bytes.

Easy - Rotate a Sample Buffer

Re-basing a circular sample log so the oldest entry is first before dumping it over a link, or aligning a frame after resynchronising to a delimiter.

Rotate an array right by k positions in place. Support k larger than the array and use no second sample buffer.

Triple-reversal in-place rotation

Rotates samples right by k positions, in place. k may exceed n (it is reduced modulo n). NULL or n==0 is a no-op.

#include <stddef.h>
#include <stdint.h>

static void reverse(int16_t *a, size_t lo, size_t hi) {
    /* Reverse the half-open range [lo, hi) by swapping from both ends. */
    while (lo < hi && hi - lo > 1u) {
        int16_t tmp = a[lo];
        a[lo] = a[hi - 1u];
        a[hi - 1u] = tmp;
        lo++;
        hi--;
    }
}

void rotate_right(int16_t *samples, size_t n, size_t k) {
    if (samples == NULL || n == 0u) return;
    k %= n;                 /* rotating by n is the identity */
    if (k == 0u) return;
    reverse(samples, 0u, n);        /* whole array */
    reverse(samples, 0u, k);        /* first k land in front, flipped */
    reverse(samples, k, n);         /* the rest follow, flipped back */
}

• Right-rotating [1,2,3,4,5] by 2 gives [4,5,1,2,3]. Reversal does it in three steps: reverse everything → [5,4,3,2,1], reverse the first k → [4,5,3,2,1], reverse the rest → [4,5,1,2,3].
• Each element is swapped at most twice, so the whole rotation is O(n) with zero extra storage — no temporary copy of the array is ever needed.
• k %= n is mandatory: a k of n + 2 must behave like 2, and without the reduction the second reverse range [0,k) would index past the buffer.
• The reverse helper uses half-open ranges and the hi - lo > 1 guard so a one-element or empty range terminates immediately instead of underflowing size_t.

Cases the tests must cover

• [1,2,3,4,5] k=2 → [4,5,1,2,3]
• k = n leaves the array unchanged
• k = n + 1 behaves like k = 1
• n = 1 with any k is a no-op
• NULL with n = 5 does not crash

How it gets written wrong

• Skipping k %= n and walking off the end for large k.
• Off-by-one in the second and third reversals: the boundary is exactly k, half-open on both sides.
• Using a Juggling/gcd algorithm with signed indices — correct but far easier to get wrong than three reversals.

Easy - Maximum-Energy Burst

Finding the highest-energy window in a captured burst: the loudest segment of an audio clip, the peak-current episode in a motor log, the most active span in a vibration trace.

Find the contiguous signed-sample range with the largest sum and return its start, length, and sum. Define the result for an all-negative input.

Kadane's maximum-sum burst with indices

Returns start, length, and sum of the contiguous range with the largest sum. For all-negative input it returns the single largest (least negative) sample. Empty input yields {0,0,0}.

#include <stddef.h>
#include <stdint.h>

typedef struct { size_t start; size_t len; int32_t sum; } burst_t;

burst_t max_subarray(const int16_t *samples, size_t n) {
    burst_t best = { 0u, 0u, 0 };
    if (samples == NULL || n == 0u) return best;
    int32_t run = samples[0];   /* best sum of a range ending here */
    size_t run_start = 0u;
    best.sum = run;
    best.len = 1u;
    for (size_t i = 1u; i < n; i++) {
        /* Either extend the running range or restart at this sample —
           whichever is worth more. A negative run only drags us down. */
        if (run + samples[i] < samples[i]) {
            run = samples[i];
            run_start = i;
        } else {
            run += samples[i];
        }
        if (run > best.sum) {   /* strict: keep the earliest longest win */
            best.sum = run;
            best.start = run_start;
            best.len = i - run_start + 1u;
        }
    }
    return best;
}

• Kadane's insight: the best range ending at position i either extends the best range ending at i-1 or starts fresh at i. Whichever sum is bigger wins — one pass, O(n).
• Sums accumulate in int32_t: n * 32767 overflows int16_t quickly, and the energy of a burst is exactly what the caller wants reported.
• Restarting when run + x < x handles the all-negative case for free: the run restarts at every sample, and best simply tracks the largest single element.
• Using > (not >=) when updating best means ties keep the earliest burst, which is the deterministic behavior telemetry tools expect.

Cases the tests must cover

• [-2, 3, 4, -1, -5] → sum 7, start 1, len 2
• [-5, -1, -3] → sum -1, the single largest element
• [1, 2, 3] → whole array, sum 6
• Two equal-sum bursts → the earlier one is returned
• n = 1 returns that element

How it gets written wrong

• Resetting the run to 0 instead of restarting at x, which breaks the all-negative contract (you would report sum 0 for an empty range).
• Accumulating in int16_t and wrapping on long loud bursts.
• Recording best.len from stale run_start when the run was restarted on the same iteration.

Medium - Partition Three Event Types

Sorting a mixed event buffer into three priority classes in place before the dispatcher walks it - critical, normal, deferred.

Reorder an array containing only LOW, NORMAL, and CRITICAL events in one pass without another array while preserving no ordering within a class.

One-pass three-way partition (Dutch flag)

Reorders events in place so all LOW come first, then NORMAL, then CRITICAL. Order within a class is not preserved. O(n), single pass, no second array.

#include <stddef.h>
#include <stdint.h>

typedef enum { EV_LOW = 0, EV_NORMAL = 1, EV_CRITICAL = 2 } event_class_t;

static void swap_ev(event_class_t *a, event_class_t *b) {
    event_class_t t = *a; *a = *b; *b = t;
}

void partition_events(event_class_t *events, size_t n) {
    if (events == NULL) return;
    size_t lo = 0u;    /* next slot for a LOW */
    size_t mid = 0u;   /* current element under inspection */
    size_t hi = n;     /* one past the CRITICAL region */
    while (mid < hi) {
        if (events[mid] == EV_LOW) {
            swap_ev(&events[lo], &events[mid]);
            lo++;
            mid++;    /* swapped-in value came from the checked region */
        } else if (events[mid] == EV_CRITICAL) {
            hi--;
            swap_ev(&events[mid], &events[hi]);
            /* do NOT advance mid: the value swapped back is unexamined */
        } else {
            mid++;    /* NORMAL stays put, region just grows */
        }
    }
}

• Three regions grow inside one array: [0,lo) is LOW, [lo,mid) is NORMAL, [hi,n) is CRITICAL, and [mid,hi) is still unexamined. When the unexamined region is empty, the partition is done.
• LOW swaps into the front and mid can advance, because the element swapped forward came from the already-checked NORMAL region.
• CRITICAL swaps to the back and mid must stay: the element that came back from position hi-1 has never been inspected.
• Each swap places at least one element into its final region, so the loop is a true single O(n) pass — this is the same partition step at the heart of dual-pivot quicksort.

Cases the tests must cover

• [C,N,L,N,C,L] → [L,L,N,N,C,C] (any within-class order)
• Already partitioned input stays partitioned
• All one class → unchanged
• n = 0 and NULL are no-ops
• Two elements reversed get swapped

How it gets written wrong

• Advancing mid after the CRITICAL swap — the swapped-in element is then never classified.
• Using three output lists and concatenating: simple but violates the no-second-array contract.
• Counting-sort style two passes are fine asymptotically but touch memory twice; the Dutch-flag pass is cache-friendlier.

Medium - Merge Busy Time Ranges

Reconciling reserved time ranges: which windows a radio is already committed to transmit in, which flash sectors an erase already covers, which timer slots are taken.

Given sorted possibly overlapping [start,end) peripheral busy ranges, merge them in place and return the number of disjoint ranges.

In-place merge of sorted busy ranges

Merges overlapping or touching [start,end) ranges (sorted by start) in place and returns the count of disjoint ranges. The merged ranges occupy the front of the array.

#include <stddef.h>
#include <stdint.h>

typedef struct { uint32_t start; uint32_t end; } range_t;

size_t merge_ranges(range_t *ranges, size_t n) {
    if (ranges == NULL || n == 0u) return 0u;
    size_t w = 0u;  /* index of the last merged (output) range */
    for (size_t r = 1u; r < n; r++) {
        if (ranges[r].start <= ranges[w].end) {
            /* Overlapping or adjacent: extend the current merged range. */
            if (ranges[r].end > ranges[w].end) {
                ranges[w].end = ranges[r].end;
            }
        } else {
            /* Disjoint: commit a new output range. */
            w++;
            ranges[w] = ranges[r];
        }
    }
    return w + 1u;
}

• Because input is sorted by start, any range that overlaps the current merged range starts before it ends — one left-to-right pass suffices, no nested loops.
• The write cursor w trails the read cursor r, so compacting in place never destroys unread data: the same read/write pair pattern as dedup.
• Using <= makes touching ranges [0,5) and [5,9) merge into [0,9), which is what 'busy time' wants — back-to-back bookings read as one busy block.
• The max check on end matters because a later-starting range can be entirely inside the merged one (nested intervals).

Cases the tests must cover

• [1,3) [2,6) [8,9) → [1,6) [8,9), count 2
• Nested [0,10) [2,3) → [0,10), count 1
• Touching [0,5) [5,9) → [0,9), count 1
• All disjoint → count n, values unchanged
• n = 1 returns 1

How it gets written wrong

• Comparing against ranges[r-1] instead of the merged ranges[w] — a chain of three overlapping ranges then fails to merge fully.
• Extending end unconditionally, shrinking the merged range when a nested interval ends earlier.
• Sorting inside this function: the contract says input is already sorted; sorting here would change the complexity guarantee.

Medium - Product Except Current Channel

Cross-channel normalisation on a multi-channel sensor: scaling each channel by the product of the others without a division per channel.

For each channel, output the product of every other channel gain without division. Detect int32 overflow and use only the output array for prefix state.

Product except self with overflow detection

out[i] = product of all in[j], j != i, without division. Returns false on int32 overflow (outputs up to the failing index are valid). Uses only out for prefix state.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

static bool mul_ok(int32_t a, int32_t b, int32_t *res) {
    int64_t wide = (int64_t)a * (int64_t)b;  /* 64-bit canary */
    if (wide > INT32_MAX || wide < INT32_MIN) return false;
    *res = (int32_t)wide;
    return true;
}

bool product_except_self(const int16_t *in, int32_t *out, size_t n) {
    if (in == NULL || out == NULL || n == 0u) return false;
    /* Pass 1: out[i] = product of everything left of i. */
    int32_t run = 1;
    for (size_t i = 0u; i < n; i++) {
        out[i] = run;
        if (!mul_ok(run, in[i], &run)) return false;
    }
    /* Pass 2: walk back, folding in the product of everything right of i. */
    run = 1;
    for (size_t i = n; i-- > 0u;) {
        if (!mul_ok(out[i], run, &out[i])) return false;
        if (!mul_ok(run, in[i], &run)) return false;
    }
    return true;
}

• The product 'everything except i' splits into (everything left of i) x (everything right of i). Two passes compute those halves without ever dividing — division would break on zeros and is often missing on small cores anyway.
• Pass 1 stores left-products directly in out; pass 2 walks backward carrying the right-product in one register, so the only extra state is a single int32_t.
• Every multiply goes through an int64_t canary and is range-checked: 16 channels of gain 100 each overflows int32_t fast, and silent wrap in a gain stage corrupts the whole mix.
• The backward loop idiom `for (i = n; i-- > 0;)` is the safe way to iterate a size_t down to 0 without the infinite-loop underflow of i >= 0.

Cases the tests must cover

• [1,2,3,4] → [24,12,8,6]
• Array containing a zero: only the zero's slot gets a nonzero product
• Two zeros → all outputs 0
• [30000, 30000, 30000] returns false (overflow), no wrapped outputs reported as valid
• n = 1 → out[0] = 1 (empty product)

How it gets written wrong

• Using the total-product/divide-by-self trick: division by a zero channel and int16 rounding both break it.
• Checking overflow after the int32_t multiply already wrapped — that is undefined behavior for signed types; widen before multiplying.
• Writing pass 2 as i >= 0 with size_t, looping forever when i wraps to SIZE_MAX.

Medium - Run-Length Encode Samples

Compressing telemetry that is mostly unchanging before it goes over a link that charges by the byte - LoRaWAN, cellular IoT, or a battery-limited BLE connection.

Encode a sample stream as (value,count) pairs into caller storage. Split counts above 65535 into multiple runs and report failure with no partial output when capacity is insufficient.

Run-length encoder with overflow splitting

Counts the runs first and returns false without touching output when capacity is insufficient. Runs longer than 65535 are split into multiple entries.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { int16_t value; uint16_t count; } run_t;

bool rle_encode(const int16_t *in, size_t n, run_t *out, size_t cap, size_t *runs)
{
    size_t needed = 0U;
    size_t i, w = 0U;
    if ((out == NULL) || (runs == NULL)) return false;
    if ((in == NULL) && (n != 0U)) return false;
    for (i = 0U; i < n; ) {                 /* pass 1: how many entries? */
        int16_t v = in[i];
        uint32_t run = 0U;
        while ((i < n) && (in[i] == v)) { ++run; ++i; }
        needed += (run + 65534U) / 65535U;   /* chunks of at most 65535 */
    }
    if (needed > cap) return false;          /* no partial output */
    for (i = 0U; i < n; ) {                 /* pass 2: write */
        int16_t v = in[i];
        uint32_t run = 0U;
        while ((i < n) && (in[i] == v)) { ++run; ++i; }
        while (run > 65535U) { out[w].value = v; out[w].count = 65535U; ++w; run -= 65535U; }
        out[w].value = v;
        out[w].count = (uint16_t)run;
        ++w;
    }
    *runs = w;
    return true;
}

int main(void)
{
    int16_t in[] = { 7, 7, 7, 2, 2, 9 };
    run_t out[8];
    size_t runs = 0U;
    assert(rle_encode(in, 6U, out, 8U, &runs));
    assert(runs == 3U);
    assert(out[0].value == 7 && out[0].count == 3U);
    assert(out[1].value == 2 && out[1].count == 2U);
    assert(out[2].value == 9 && out[2].count == 1U);
    assert(!rle_encode(in, 6U, out, 2U, &runs));   /* capacity: untouched output */
    assert(rle_encode(NULL, 0U, out, 8U, &runs) && runs == 0U);
    return 0;
}

• Two passes keep failure atomic: sizing never writes, writing never fails.
• uint32_t run prevents count overflow before the 65535 split.
• A run of exactly 65535 fits one entry; 65536 needs two.

Cases the tests must cover

• three mixed runs
• capacity too small returns false with output untouched
• empty input yields zero runs
• NULL input with n>0 rejected
• a run of 65536 splits into two entries

How it gets written wrong

• Writing before knowing the total leaves a corrupt partial stream.
• uint16_t run counting would wrap at 65536 before the split logic sees it.

Easy - Byte-Value Histogram

Building the distribution of a byte-valued signal for auto-exposure, threshold selection, or detecting a stuck ADC bit.

Build a 256-bin histogram of a byte buffer using a caller-provided zeroed table, then report the most frequent byte and its count.

Byte histogram and mode

bins must be a caller-provided zeroed array of 256 uint32_t. histogram_peak returns the first byte with the maximal count and stores that count.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

void histogram_u8(const uint8_t *data, size_t n, uint32_t *bins)
{
    size_t i;
    for (i = 0U; i < n; ++i) bins[data[i]] += 1U;
}

uint8_t histogram_peak(const uint32_t *bins, uint32_t *count)
{
    uint8_t best = 0U;
    uint16_t b;
    for (b = 0U; b < 256U; ++b) {
        if (bins[b] > bins[best]) best = (uint8_t)b;
    }
    *count = bins[best];
    return best;
}

int main(void)
{
    uint8_t data[] = { 5U, 1U, 5U, 5U, 2U, 1U };
    uint32_t bins[256] = { 0U };
    uint32_t count = 0U;
    histogram_u8(data, sizeof data, bins);
    assert(bins[5] == 3U && bins[1] == 2U && bins[2] == 1U);
    assert(histogram_peak(bins, &count) == 5U && count == 3U);
    return 0;
}

• The byte value is the index: direct addressing, O(1) per sample.
• uint32_t bins survive 4 GiSamples; uint16_t would wrap on long DMA captures.
• Strictly-greater comparison keeps the LOWEST byte on ties: deterministic.

Cases the tests must cover

• counts per bin
• peak is the most frequent byte
• tie keeps the lower byte value
• all-equal input peaks at that byte with count n
• empty input leaves every bin zero

How it gets written wrong

• A uint16_t bin overflows on streams longer than 65535 samples.
• Zeroing is the caller's contract: document it or counts leak between captures.

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.