What is the time complexity of Minimum Number of Removals to Make Mountain Array?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Minimum Number of Removals to Make Mountain Array?

This problem uses Array, Binary Search, Dynamic Programming, Greedy. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Minimum Number of Removals to Make Mountain Array?

Insight 1: The problem can be solved by finding the longest mountain subarray within the given array. This involves identifying a peak and calculating the lengths of the increasing sequence before the peak and the decreasing sequence after the peak. Insight 2: Dynamic Programming can be used to efficiently compute the lengths of the Longest Increasing Subsequence (LIS) ending at each index and the Longest Decreasing Subsequence (LDS) starting at each index.

Which companies ask LeetCode 1671. Minimum Number of Removals to Make Mountain Array in interviews?

This problem is frequently asked at PayPal.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Minimum Number of Removals to Make Mountain Array - LeetCode 1671 Solution

Minimum Number of Removals to Make Mountain Array - Complete Solution Guide

Minimum Number of Removals to Make Mountain Array is LeetCode problem 1671, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 . Example 1: Input: nums = [1,3,1] Output: 0 Explanation: The array itself is a mountain array so we do not need to remove any el

Detailed Explanation

The problem asks us to find the minimum number of elements to remove from a given integer array `nums` to make it a 'mountain array'. A mountain array has the following properties: its length is at least 3, and there exists an index `i` (0-indexed) such that the elements from index 0 up to `i` are strictly increasing, and the elements from index `i` to the end are strictly decreasing. In essence, there's a peak, and the array increases to the peak and then decreases. The goal is to find the longest possible mountain subarray by removing the minimum number of elements from the original array.

Solution Approach

The solution uses dynamic programming to find the longest increasing subsequence (LIS) ending at each index and the longest decreasing subsequence (LDS) starting at each index. For each index `i`, the sum of `LIS[i]` and `LDS[i]` gives the length of a potential mountain with peak at `i`. We then iterate through all possible peak indices and find the maximum possible length of a mountain subarray. Finally, we subtract the maximum mountain length from the original array length to find the minimum number of removals.

Step-by-Step Algorithm

Step 1: Initialize two arrays, `lis` and `lds`, of the same size as `nums`, filled with 1s. `lis[i]` will store the length of the longest increasing subsequence ending at index `i`, and `lds[i]` will store the length of the longest decreasing subsequence starting at index `i`.
Step 2: Calculate the `lis` array. Iterate through `nums` from left to right. For each index `i`, iterate through all indices `j` from 0 to `i-1`. If `nums[i] > nums[j]`, update `lis[i]` to be the maximum of its current value and `lis[j] + 1`.
Step 3: Calculate the `lds` array. Iterate through `nums` from right to left. For each index `i`, iterate through all indices `j` from `n-1` down to `i+1`. If `nums[i] > nums[j]`, update `lds[i]` to be the maximum of its current value and `lds[j] + 1`.
Step 4: Find the maximum length of a mountain subarray. Iterate through `nums` from index 1 to `n-2`. For each index `i`, check if `lis[i] > 1` and `lds[i] > 1` (ensuring there's an increasing part before the peak and a decreasing part after the peak). If both conditions are met, calculate the length of the mountain as `lis[i] + lds[i] - 1`. Update the `max_len` if the current mountain length is greater.
Step 5: Return the minimum number of removals, which is `n - max_len`.

Key Insights

Insight 1: The problem can be solved by finding the longest mountain subarray within the given array. This involves identifying a peak and calculating the lengths of the increasing sequence before the peak and the decreasing sequence after the peak.
Insight 2: Dynamic Programming can be used to efficiently compute the lengths of the Longest Increasing Subsequence (LIS) ending at each index and the Longest Decreasing Subsequence (LDS) starting at each index.
Insight 3: To form a valid mountain, both the increasing and decreasing parts must have lengths greater than 1. This is because the peak element must have elements both before and after it.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: Array, Binary Search, Dynamic Programming, Greedy.

Companies

Asked at: PayPal.

Minimum Number of Removals to Make Mountain Array | LeetCode 1671

Hard

Array Binary Search Dynamic Programming Greedy

Time: O(n^2)Space: O(n)

Solution Code

Available in:

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        
        // lis[i] = length of Longest Increasing Subsequence ending at index i
        int[] lis = new int[n];
        for (int i = 0; i < n; i++) {
            lis[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }
        
        // lds[i] = length of Longest Decreasing Subsequence starting at index i
        int[] lds = new int[n];
        for (int i = 0; i < n; i++) {
            lds[i] = 1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }
        
        int max_len = 0;
        for (int i = 1; i < n - 1; i++) {
            // A valid mountain peak must have a strictly increasing part before it
            // and a strictly decreasing part after it.
            if (lis[i] > 1 && lds[i] > 1) {
                // Length of mountain = LIS on left + LDS on right - 1 (for the peak)
                int current_len = lis[i] + lds[i] - 1;
                max_len = Math.max(max_len, current_len);
            }
        }
        
        return n - max_len;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1671: Minimum Number of Removals to Make Mountain Array - Detailed explanation and solution approaches.

Topics

Array Binary Search Dynamic Programming Greedy

Companies

PayPal

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1671

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize two arrays, `lis` and `lds`, of the same size as `nums`, filled with 1s. `lis[i]` will store the length of the longest increasing subsequence ending at index `i`, and `lds[i]` will store the length of the longest decreasing subsequence starting at index `i`.
2
Step 2: Calculate the `lis` array. Iterate through `nums` from left to right. For each index `i`, iterate through all indices `j` from 0 to `i-1`. If `nums[i] > nums[j]`, update `lis[i]` to be the maximum of its current value and `lis[j] + 1`.
3
Step 3: Calculate the `lds` array. Iterate through `nums` from right to left. For each index `i`, iterate through all indices `j` from `n-1` down to `i+1`. If `nums[i] > nums[j]`, update `lds[i]` to be the maximum of its current value and `lds[j] + 1`.
4
Step 4: Find the maximum length of a mountain subarray. Iterate through `nums` from index 1 to `n-2`. For each index `i`, check if `lis[i] > 1` and `lds[i] > 1` (ensuring there's an increasing part before the peak and a decreasing part after the peak). If both conditions are met, calculate the length of the mountain as `lis[i] + lds[i] - 1`. Update the `max_len` if the current mountain length is greater.
5
Step 5: Return the minimum number of removals, which is `n - max_len`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n^2) because we have nested loops to calculate both the `lis` and `lds` arrays, each taking O(n^2) time. The final loop to find the maximum mountain length takes O(n) time, but this is dominated by the O(n^2) complexity of the LIS and LDS calculations. The space complexity is O(n) because we use two arrays, `lis` and `lds`, each of size `n` to store the lengths of the increasing and decreasing subsequences.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Binary Search Optimization for LIS

Instead of using nested loops to calculate the LIS and LDS, binary search can be used to optimize the calculation. This would involve maintaining a tail array representing the smallest tail of all increasing subsequences of a given length. Binary search is then used to find the appropriate position to update the tail array.

Time: O(n log n)Space: O(n)

Trade-offs: This approach improves the time complexity to O(n log n) but adds complexity to the implementation. It's beneficial for larger input arrays where the performance gain is significant.

✨

Key Insights

1Insight 1: The problem can be solved by finding the longest mountain subarray within the given array. This involves identifying a peak and calculating the lengths of the increasing sequence before the peak and the decreasing sequence after the peak.
2Insight 2: Dynamic Programming can be used to efficiently compute the lengths of the Longest Increasing Subsequence (LIS) ending at each index and the Longest Decreasing Subsequence (LDS) starting at each index.
3Insight 3: To form a valid mountain, both the increasing and decreasing parts must have lengths greater than 1. This is because the peak element must have elements both before and after it.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Edge Cases

Edge case 1: Input array is already a mountain array (e.g., [1, 3, 2]). The solution correctly identifies the mountain and returns 0 removals.
Edge case 2: Input array has no possible mountain array (e.g., array is decreasing or increasing). The `if lis[i] > 1 and lds[i] > 1` condition ensures that only valid mountain peaks are considered. Also the problem states: It is guaranteed that you can make a mountain array out of `nums`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking for `lis[i] > 1` and `lds[i] > 1` before calculating the mountain length. This can lead to including indices that are not valid mountain peaks, resulting in incorrect results.

✗Common mistake 2: Incorrectly calculating the length of the mountain. Remember that `lis[i]` and `lds[i]` both include the peak element, so the total length should be `lis[i] + lds[i] - 1`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing stock prices to identify peak values and trends. The increasing and decreasing subsequences can represent periods of growth and decline.

🏦Real-world scenario 2: Signal processing, where identifying peaks and valleys in a signal is important for feature extraction and pattern recognition. The increasing and decreasing parts relate to trends in signal intensity.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Can binary search be applied to non-sorted arrays?

Binary search requires a monotonic property, not necessarily sorted data. It can be applied to any search space where you can determine if the answer is in the left or right half. Examples include searching rotated arrays or finding minimum in optimization problems.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Minimum Number of Removals to Make Mountain Array"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?