Minimum Number of Removals to Make Mountain Array

Minimum Number of Removals to Make Mountain Array - Problem

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums, return the minimum number of elements to remove to make nums a mountain array.

Input & Output

Example 1 — Basic Mountain

$ Input: nums = [1,3,1]

› Output: 0

💡 Note: The array [1,3,1] is already a mountain array with peak at index 1: 1 < 3 > 1. No removals needed.

Example 2 — Need Removals

$ Input: nums = [2,1,1,5,6,2,3,1]

› Output: 3

💡 Note: We can form mountain [2,5,6,3,1] by removing elements at indices 1, 2, and 7. This gives us 8 - 5 = 3 removals.

Example 3 — Small Array

$ Input: nums = [4,3,2,1,1,2,3,1]

› Output: 4

💡 Note: We can form mountain [1,2,3,1] from the latter part. This requires removing 4 elements.

Constraints

3 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array that needs to become a mountain

Find Peak

Identify optimal peak position and calculate mountain length

Remove Elements

Remove minimum elements to form valid mountain

Key Takeaway

🎯 Key Insight: Find the longest mountain subsequence using LIS+LDS, then remove the remaining elements

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to find the longest possible mountain subsequence and remove the rest. Best approach uses binary search optimization on LIS/LDS calculation. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsequences	O(2ⁿ)	O(n)	Try every possible peak position and check all possible mountain subsequences
Optimized DP with Binary Search	O(n log n)	O(n)	Use binary search to optimize LIS and LDS calculations from O(n²) to O(n log n)
Dynamic Programming - LIS/LDS Approach	O(n²)	O(n)	Calculate longest increasing subsequence ending at each position and longest decreasing subsequence starting at each position

Brute Force - Try All Subsequences — Algorithm Steps

For each position i as potential peak
Generate all increasing subsequences ending at i
Generate all decreasing subsequences starting at i
Find the longest valid mountain combination

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible subsequences

Validate

Check if each forms a valid mountain

Maximize

Find longest valid mountain subsequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isMountain(int* arr, int size) {
    if (size < 3) return false;
    int i = 0;
    while (i < size - 1 && arr[i] < arr[i + 1]) i++;
    if (i == 0 || i == size - 1) return false;
    while (i < size - 1 && arr[i] > arr[i + 1]) i++;
    return i == size - 1;
}

int generateSubsequences(int* nums, int numsSize, int idx, int* current, int currentSize) {
    if (idx == numsSize) {
        return isMountain(current, currentSize) ? currentSize : 0;
    }
    
    current[currentSize] = nums[idx];
    int withCurrent = generateSubsequences(nums, numsSize, idx + 1, current, currentSize + 1);
    int withoutCurrent = generateSubsequences(nums, numsSize, idx + 1, current, currentSize);
    
    return withCurrent > withoutCurrent ? withCurrent : withoutCurrent;
}

int solution(int* nums, int numsSize) {
    if (numsSize < 3) return numsSize;
    
    int* current = (int*)malloc(numsSize * sizeof(int));
    int maxMountainLength = generateSubsequences(nums, numsSize, 0, current, 0);
    free(current);
    return numsSize - maxMountainLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each element can be included or excluded, leading to 2^n possible subsequences to check

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth for generating subsequences

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler