Mountain Subarray Queries

Problem Overview

A range [l, r] is a mountain if values first go non-decreasing, then non-increasing (either phase alone is allowed).

Intuition

A range [l, r] is a mountain if values first go non-decreasing, then non-increasing (either phase alone is allowed). From any index the ascending run and descending run each have a farthest reachable end, and those ends can be precomputed once. A query then only checks whether the ascent from l and the descent from that peak together cover r.

Algorithm

1Build up[i]: scan right-to-left; if arr[i] ≤ arr[i+1] set up[i] = up[i+1], else up[i] = i. This is the end of the non-decreasing run starting at i.
2Build down[i] the same way for non-increasing runs (arr[i] ≥ arr[i+1]).
3For each query [l, r], let peak = up[l].
4Answer true if peak ≥ r (the whole range is non-decreasing) or down[peak] ≥ r (after the peak the descent reaches r); otherwise false.

Example Walkthrough

Input: arr = [1, 3, 5, 4, 2], queries = [[0, 4], [1, 3], [3, 4]]

1. up = [2, 2, 2, 3, 4] and down = [0, 1, 4, 4, 4].
2. Query [0,4]: peak = up[0] = 2, down[2] = 4 ≥ 4 → true (1,3,5 then 4,2).
3. Query [1,3]: peak = up[1] = 2, down[2] = 4 ≥ 3 → true.
4. Query [3,4]: peak = up[3] = 3, but 3 < 4; down[3] = 4 ≥ 4 → true (pure descent).

Output: [true, true, true]

Common Pitfalls

• Plateaus count: use ≤ on the ascent and ≥ on the descent, not strict inequalities.
• A pure ascent or pure descent is a valid mountain for this problem — do not require both slopes.
• peak = up[l] is the first place the ascent from l stops; do not search for a local maximum inside [l, r] separately.
• Indices in queries are 0-based; compare peak and down[peak] against r inclusively.

Mountain Subarray Queries.java

Java


import java.util.*;

class Solution {

    // Approach: Precompute two rightward reach arrays. up[i] is the farthest
    // index reachable from i while the sequence stays non-decreasing; down[i]
    // is the farthest while it stays non-increasing. For query [l, r], the
    // non-decreasing stretch from l ends at peak = up[l]. The range is a
    // mountain iff it ends before/at that peak (pure ascent) or the
    // non-increasing stretch from the peak reaches r (ascent then descent).
    // Complexity: O(n + q) time and O(n) space.
    public ArrayList<Boolean> processQueries(int[] arr, int[][] queries) {
        int n = arr.length;

        int[] up = new int[n];
        int[] down = new int[n];

        up[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] <= arr[i + 1]) {
                up[i] = up[i + 1];
            } else {
                up[i] = i;
            }
        }

        down[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] >= arr[i + 1]) {
                down[i] = down[i + 1];
            } else {
                down[i] = i;
            }
        }

        ArrayList<Boolean> ans = new ArrayList<>();

        for (int[] q : queries) {
            int l = q[0];
            int r = q[1];

            int peak = up[l];

            if (peak >= r || down[peak] >= r) {
                ans.add(true);
            } else {
                ans.add(false);
            }
        }

        return ans;
    }
}

Was this solution helpful?