Log inSign up
easyGeeksforGeeksNot Started

Check if Array Represents Min Heap

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array arr of size N, check if it represents a valid Binary Min-Heap.

A binary tree stored in array representation is a Min-Heap if for every node at index i: 1. If 2*i + 1 < N, then arr[i] <= arr[2*i + 1]. 2. If 2*i + 2 < N, then arr[i] <= arr[2*i + 2].

Return true if the array satisfies the min-heap property, otherwise return false.

Example 1 · Example 1: Valid Min-Heap:

Input: arr = [10, 15, 14, 25, 30]
Output: true
Explanation: Root 10 has children 15 and 14 (10 <= 15 and 10 <= 14). Node 15 has children 25 and 30 (15 <= 25 and 15 <= 30). All parent-child relations satisfy arr[parent] <= arr[child]. Min-Heap Tree: (10) / \ (15) (14) / \ (25) (30)

Example 2 · Example 2: Invalid Min-Heap:

Input: arr = [10, 20, 30, 12, 25]
Output: false
Explanation: Node at index 1 is 20. Its left child at index 3 is 12. Since 20 > 12, the min-heap property is violated.

Constraints:

  • 1 <= N <= 105
  • -106 <= arr[i] <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand parent-child array indexing in binary heaps (2i + 1, 2i + 2).
  • Identify the range of internal nodes vs leaves in an array of size N.
  • Implement optimal O(1) space verification.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array represents a binary tree in level-order layout.
  • Verify min-heap or max-heap property.
  • Short-circuit on first violation.

Algorithmic Decision Tree:

  • If arr[i] > arr[2*i + 1] or arr[i] > arr[2*i + 2], return false.
  • Only check nodes that actually possess children (indices up to (N-2)/2).

Connected Patterns:

Build HeapKth Largest Element in an Array

1. Brute Force — Recursive Tree Traversal

Intuition

At index i, check if left child exists and is smaller than arr[i]; if so return false. Do the same for right child. Then recursively call isMinHeap for left and right children.

When to apply: When understanding the property through tree recursion.

Algorithm

  1. Step 1: Base case: if index >= n, return true.
  2. Step 2: If 2*i + 1 < n and arr[i] > arr[2*i + 1], return false.
  3. Step 3: If 2*i + 2 < n and arr[i] > arr[2*i + 2], return false.
  4. Step 4: Return isMinHeap(2*i + 1) && isMinHeap(2*i + 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 bool isMinHeapHelper(const vector<int>& arr, int n, int i) {
8 if (i >= n) return true;
9 int left = 2 * i + 1;
10 int right = 2 * i + 2;
11
12 if (left < n && arr[i] > arr[left]) return false;
13 if (right < n && arr[i] > arr[right]) return false;
14
15 return isMinHeapHelper(arr, n, left) && isMinHeapHelper(arr, n, right);
16 }
17
18 bool isMinHeap(const vector<int>& arr) {
19 return isMinHeapHelper(arr, arr.size(), 0);
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> arr = {10, 15, 14, 25, 30};
26 cout << "Is Min Heap (Recursive): " << (sol.isMinHeap(arr) ? "true" : "false") << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N) — O(N) to visit all nodes.
  • Space complexity: O(log N) — O(log N) for the recursion stack.

Why Brute Force Doesn't Scale:

Queue BFS incurs memory allocation penalties. The direct loop has zero memory overhead and optimal cache locality.

Validating an array of 107 elements takes ~10ms iteratively vs ~250ms with queue BFS.

2. Better — Queue-based BFS Verification

Intuition

Enqueue index 0. While queue is not empty, pop index i, verify that its left and right children are >= arr[i], and push children into queue if they have descendants.

When to apply: When recursion stack limit is a concern and iterative BFS is desired.

Algorithm

  1. Step 1: Enqueue index 0.
  2. Step 2: While queue is not empty, dequeue curr.
  3. Step 3: Check left child 2*curr + 1: if within bounds and arr[curr] > arr[left], return false.
  4. Step 4: Check right child 2*curr + 2: if within bounds and arr[curr] > arr[right], return false.
  5. Step 5: Push left and right children if they are internal nodes.
  6. Step 6: Return true if queue empties without violations.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8 bool isMinHeap(const vector<int>& arr) {
9 int n = arr.size();
10 if (n <= 1) return true;
11 queue<int> q;
12 q.push(0);
13
14 while (!q.empty()) {
15 int curr = q.front();
16 q.pop();
17
18 int left = 2 * curr + 1;
19 int right = 2 * curr + 2;
20
21 if (left < n) {
22 if (arr[curr] > arr[left]) return false;
23 q.push(left);
24 }
25 if (right < n) {
26 if (arr[curr] > arr[right]) return false;
27 q.push(right);
28 }
29 }
30 return true;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> arr = {10, 15, 14, 25, 30};
37 cout << "Is Min Heap (BFS): " << (sol.isMinHeap(arr) ? "true" : "false") << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — O(N) processing each node in queue.
  • Space complexity: O(N) — O(N) auxiliary space for queue.

3. Optimal — Single Iterative Pass Over Internal Nodes

Intuition

Because an array representation is implicitly level-order, we can iterate sequentially from index 0 to (n/2)-1. We check if arr[i] > arr[2i+1], or if right child exists and arr[i] > arr[2i+2]. Returns false immediately upon violation.

When to apply: Standard optimal approach in production and interviews.

Algorithm

  1. Step 1: Let n = arr.length. If n <= 1, return true.
  2. Step 2: Loop i from 0 up to (n / 2) - 1.
  3. Step 3: If arr[i] > arr[2 * i + 1], return false.
  4. Step 4: If 2 * i + 2 < n and arr[i] > arr[2 * i + 2], return false.
  5. Step 5: If all internal nodes pass, return true.

Interactive Trace for Check if Array Represents Min Heap

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Check node at index 0 (10)
Visual state
Values and pointers at this exact step
tree
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
10
15
14
25
30
0
↑ check
1
2
3
4
Binary Heap Tree Topology
10#n0
15#n1
14#n2
25#n3
30#n4
Check / comparison
10 <= 15 and 10 <= 14
Decision / next transition
Node 10 satisfies min-heap property.
Why this step matters

Step 1: Check node at index 0 (10). Left child = 15 (idx 1), right child = 14 (idx 2).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 bool isMinHeap(const vector<int>& arr) {
8 int n = arr.size();
9 for (int i = 0; i <= (n - 2) / 2; i++) {
10 int left = 2 * i + 1;
11 int right = 2 * i + 2;
12
13 if (arr[i] > arr[left]) return false;
14 if (right < n && arr[i] > arr[right]) return false;
15 }
16 return true;
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<int> arr = {10, 15, 14, 25, 30};
23 cout << "Is Min Heap (Optimal): " << (sol.isMinHeap(arr) ? "true" : "false") << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N) — O(N) linear scan over at most N/2 nodes with early exit.
  • Space complexity: O(1) — O(1) strict auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Range Recursive TraversalO(N)O(N) recursion stackRecursively verify min-heap property for node i, then recurse on left and right subtrees.Recursion overhead.
2.Better — Queue-based BFS VerificationO(N)O(N) queuePush root to queue, process level by level, verify children and push them.Unnecessary queue allocations.
3.Optimal — Single Iterative Pass Over Internal NodesOptimalO(N)O(1)Loop i from 0 to floor(N/2) - 1. Check left child (2*i + 1) and right child (2*i + 2). Return false if arr[i] > child.None.

Common Pitfalls & Crucial Edge Cases

Looping until N instead of (N-2)/2

Accesses out-of-bounds indices for leaf nodes.

Forgetting boundary check on right child

Right child (2*i + 2) might equal n when left child is the final element.

Strict inequality (< instead of <=)

Duplicate values are valid in heaps.

Crucial Edge Cases to Validate:

  • Single element array (N = 1) — Returns true; trivial min-heap.
  • Array of length 2 — Only checks left child.
  • All elements equal — Valid min-heap since parent <= child holds.
  • Descending sorted array — Violates min-heap property on the very first comparison (index 0).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the formula for parent-to-child indices (2i + 1, 2i + 2) and child-to-parent index (i - 1) / 2 clearly.
  2. Point out that the loop bound can be strictly limited to (N - 2) / 2.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Up to which index do internal nodes have children in an array of size N?

Back to DSA Sheet