Check if an array represents a min-heap

Given an integer array arr viewed as a complete binary tree (children of index i are 2i+1 and 2i+2), return true if it represents a valid min-heap — every node is ≤ both of its children — and false otherwise. An empty array is a valid heap.

Hints

· Stuck? Reveal one nudge at a time.

The min-heap property is local: each parent ≤ its children.

Only indices 0 .. n/2 - 1 have children; leaves can't violate anything.

Scan those internal nodes and compare each to its present children.

Common doubts

Indices n/2 .. n-1 are leaves — they have no children, so there is nothing to check.

No — the property is parent ≤ child, so equal children are fine.

No — the property is local per edge, so checking every parent-child pair once is exactly checking the whole heap.

Interview follow-ups

· What an interviewer asks next.

Flip the comparison: every parent must be ≥ its children.

That's harder — a heap's property is local, but a BST's is a global ordering, so you'd rebuild the tree and inorder-check.

Fun facts

Because the property is purely local, this is one of the few tree checks that needs no traversal state at all.
The same n/2 boundary shows up in build-heap, which only sifts indices 0 .. n/2 - 1.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: arr = [1, 3, 5, 4, 8]
Output: true
Every parent is ≤ its children.

Example 2

Input: arr = [1, 5, 3, 8, 4]
Output: false
Node 5 (index 1) has child 4 (index 4) which is smaller — violation.

Constraints

- 0 <= arr.length <= 10^5 - -10^9 <= arr[i] <= 10^9

A min-heap is valid exactly when every parent is ≤ its children. So checking is a single scan: for each node that has a child, compare it to that child. Only indices 0 .. n/2 - 1 have children (the rest are leaves), so you never need to look past the halfway point — and each comparison is O(1), giving O(n) overall.

The recursive version phrases the same check as "the subtree at i is a min-heap iff arr[i] ≤ each present child and each child's subtree is a min-heap." The iterative version just loops over the internal nodes. Both examine every parent-child edge once.

Prerequisites

Before you start

· Concepts used directly in the solution.

Array-as-tree. children of i are 2i+1 and 2i+2.

Internal nodes. only indices 0 .. n/2-1 have a child.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Min-heap or max-heap?”

Min-heap — parent ≤ children.

“Is an empty or single-element array valid?”

Yes, both are trivially valid heaps.

The ideal opening — say it like this

A min-heap just needs every parent ≤ its children, so I scan indices 0 to n/2-1 and compare each to its children.

If any parent exceeds a child I return false; otherwise it's a valid min-heap. O(n).

Understand the problem

Worked example — arr = [1, 3, 5, 4, 8]

i=0: children 3,5 -> 1 <= 3 and 1 <= 5 -> ok
i=1: children 4,8 -> 3 <= 4 and 3 <= 8 -> ok
no more internal nodes -> true

Key observations

1Aha

The property is local

Only parent-vs-child comparisons matter; no ancestor/descendant check is needed.

2Aha

Leaves never violate

Indices n/2 .. n-1 have no children, so the loop can stop at n/2.

3Aha

One pass, O(n)

Each parent-child edge is checked exactly once.

Brute force vs optimal

	Recursive check	Iterative scan
Idea	Subtree is a heap iff node ≤ children and children's subtrees are heaps	Loop internal nodes, compare to children
Time	O(n)	O(n)
Space	O(log n)	O(1)

Both check every edge; the iterative scan uses O(1) space. Full code is in the Approaches selector below.

Summary

Key takeaway

An array is a min-heap iff every internal node (index 0 .. n/2-1) is ≤ its present children. One O(n) scan decides it.

for i in 0 .. n/2 - 1:
    if left  exists and arr[i] > arr[left]:  return false
    if right exists and arr[i] > arr[right]: return false
return true