Monotonic Deque Sliding Maximum in C

Algorithms: Array Techniques November 15, 2026 C

A monotonic deque returns every fixed-window maximum in linear time..

c 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <errno.h>
// Monotonic Deque Sliding Maximum in C
//
// PURPOSE
// A monotonic deque returns every fixed-window maximum in linear time.
//
// METHOD
// Keep candidate indices in decreasing value order. Discard expired indices from the front
// and dominated candidates from the back; the front is the current maximum.
//
// COMPLEXITY
// O(n) time; O(n) allocated index-buffer space in this linear-buffer implementation, with at
// most k live candidates.
//
// CONTRACT
// 1 <= k <= n. output has n-k+1 entries. Writes maximum values and returns output length.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C99: checked calloc/free workspace, const input pointers, explicit size_t lengths. Errors
// return INT_MIN with errno=EINVAL, ERANGE, or ENOMEM. Check errno before using a result.
// Input/output arrays must not alias. No variable-length stack arrays.
//
// EXAMPLE
// Expected return: 6.
// Expected output after call: [3, 3, 5, 5, 6, 7].
// Run: gcc -std=c99 -O2 example.c -o example && ./example
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

static int alg_min(int a, int b) { return a < b ? a : b; }
static int alg_max(int a, int b) { return a > b ? a : b; }
static int alg_checked(int64_t v, int *error) {
    if (v < INT_MIN || v > INT_MAX) { *error = 1; return 0; }
    return (int)v;
}
static int alg_add(int a, int b, int *e) { return alg_checked((int64_t)a+b,e); }
static int alg_sub(int a, int b, int *e) { return alg_checked((int64_t)a-b,e); }
static int alg_mul(int a, int b, int *e) { return alg_checked((int64_t)a*b,e); }

int sliding_maximum(const int *a, size_t a_length, int k, int *output, size_t output_length) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    int *queue = NULL;
    if (a_length > 1000000 || (a_length && !a)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (output_length > 1000000 || (output_length && !output)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = (int)a_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)a_length == n))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)output_length == alg_add(alg_sub(n, k, &alg_error), 1, &alg_error)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((k >= 1) && (k <= n)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    {
        int alg_length = n;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_length < 0 || alg_length > 4000000) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        queue = calloc((size_t)(alg_length ? alg_length : 1), sizeof(*queue));
        if (!queue) { errno = ENOMEM; alg_result = INT_MIN; goto alg_cleanup; }
    }
    int head = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int tail = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int i = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    while (1) {
        int alg_condition = (i < n);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (!alg_condition) break;
        while (1) {
            int alg_condition = ((head < tail) && (queue[head] <= alg_sub(i, k, &alg_error)));
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (!alg_condition) break;
            head = alg_add(head, 1, &alg_error);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        }
        while (1) {
            int alg_condition = ((head < tail) && (a[queue[alg_sub(tail, 1, &alg_error)]] <= a[i]));
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (!alg_condition) break;
            tail = alg_sub(tail, 1, &alg_error);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        }
        queue[tail] = i;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        tail = alg_add(tail, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        int alg_condition_1 = (i >= alg_sub(k, 1, &alg_error));
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_condition_1) {
            output[alg_add(alg_sub(i, k, &alg_error), 1, &alg_error)] = a[queue[head]];
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        }
        i = alg_add(i, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    }
    alg_result = alg_add(alg_sub(n, k, &alg_error), 1, &alg_error);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    goto alg_cleanup;
alg_cleanup:
    free(queue);
    return alg_result;
}

int main(void) {
    int a[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    int output[] = {0, 0, 0, 0, 0, 0};
    int result = sliding_maximum(a, 8, k, output, 6);
    printf("%d\n", result);
    // Expected output: [3, 3, 5, 5, 6, 7]
    for (int alg_print = 0; alg_print < 6; alg_print++) printf("%d ", output[alg_print]);
    printf("\n");
    if (errno) { perror("algorithm"); return 1; }
    return 0;
}

Related Posts

Kadane Maximum Subarray in PHP
Kadane Maximum Subarray in PHP
Kadane Maximum Subarray in C#
Kadane Maximum Subarray in C#
Kadane Maximum Subarray in C++
Kadane Maximum Subarray in C++
Kadane Maximum Subarray in C
Kadane Maximum Subarray in C
Kadane Maximum Subarray in Python
Kadane Maximum Subarray in Python
Prefix Sum Range Query in Python
Prefix Sum Range Query in Python