874. Heap-Ordered or Not

A binary heap is not a tree of pointers. It is a plain array read as a complete binary tree: index 0 is the root, and the children of index i sit at 2i + 1 and 2i + 2.

Given n values in that layout, decide which heap rule the array obeys and print exactly one word:

min every parent is <= both of its children max every parent is >= both of its children both both rules hold neither neither rule holds

1 3 2 7 8 5 4 -> min 9 7 8 3 2 6 1 -> max 4 4 4 4 4 -> both 1 2 3 4 5 0 -> neither

Check the first one by hand. Index 0 holds 1, its children are index 1 (3) and index 2 (2), and 1 <= 3 and 1 <= 2. Index 1 holds 3 with children index 3 (7) and index 4 (8). Index 2 holds 2 with children index 5 (5) and index 6 (4). Every parent is smaller, so the answer is min.

The third row is both because every parent equals its children, and <= and >= are both satisfied by equality. A single value is both too: it has no children, so there is nothing to violate.

The fourth row fails the min rule at index 2, which holds 3 and has child index 5 holding 0. It fails the max rule at index 0, which holds 1 and has child index 1 holding 2.

## What most people try first

Building an actual tree of nodes, then walking it. That works and is a lot of code for nothing, because the array IS the tree. Every parent-child pair in the whole structure is (i, 2i + 1) or (i, 2i + 2) for some i, so a single flat loop over i visits every relationship exactly once.

The other common attempt is checking only the root, or only the first level. The rule is about every parent, and a violation can sit anywhere.

## The method

isMin = true, isMax = true for i from 0 to n-1: for c in (2i+1, 2i+2): if c < n: if a[i] > a[c]: isMin = false if a[i] < a[c]: isMax = false report both / min / max / neither

## Why one pass is enough

The complete-tree layout guarantees that if index c exists then its parent (c - 1) / 2 also exists and is smaller than c. So iterating i upward and looking DOWN covers every edge, and no edge is missed or counted twice. The loop is O(n), and it does not depend on the values at all.

## The boundary that breaks a careless implementation

The child index must be tested against n before it is read. The last parent is at index (n - 2) / 2, and for even n that parent has only a left child. Reading a[2i + 2] there is an out-of-bounds read, which in C is whatever happened to be in memory and can flip the answer either way.

The second boundary is n = 1. No edges exist, both flags stay true, and the answer is both. A program that starts with isMin = false and sets it true on the first satisfied edge answers neither here, which is wrong.

## What is NOT an overflow here

Values reach 10^9 in magnitude and the only arithmetic is on INDICES, which are at most 2n + 2, about 400002. The largest signed 32-bit integer is 2147483647, so nothing here comes close and no value needs a 64-bit type. The comparisons never combine two values, so there is no sum to overflow.

## Why this problem is worth doing before any of the others

Every heap in this block is this array. The sift routines in problems 875 and 876 move values along exactly these parent-child edges, and if the index arithmetic is not automatic yet, those two are impossible to debug.

## Cost

Time O(n). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`