What is the time complexity of Longest Mountain in Array?

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

What data structures are used to solve Longest Mountain in Array?

This problem uses Array, Two Pointers, Dynamic Programming, Enumeration. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Longest Mountain in Array?

Insight 1: Iterate through the array and identify potential 'peaks' which form the mountain's apex. Insight 2: Use two pointers, one to find the increasing slope leading up to the peak and another to find the decreasing slope after the peak.

Which companies ask LeetCode 845. Longest Mountain in Array in interviews?

This problem is frequently asked at Databricks, Faire, SoFi.

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

Longest Mountain in Array - LeetCode 845 Solution

Longest Mountain in Array - Complete Solution Guide

Longest Mountain in Array is LeetCode problem 845, a Medium 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 arr , return the length of the longest subarray, which is a mountain . Return 0 if there is no mountain subarray. Example 1: Input: arr = [2,1,4,7,3,2,5] Output: 5 Explanation: The largest mountain is [1,4,7,3,2] which ha

Detailed Explanation

The problem asks us to find the length of the longest "mountain" subarray within a given integer array `arr`. A mountain subarray is defined as a subarray of at least length 3 where there exists an index `i` such that the elements strictly increase up to `i` and strictly decrease after `i`. In simpler terms, a mountain has a peak, with elements increasing to the left of the peak and decreasing to the right. If no such mountain exists, the function should return 0.

Solution Approach

The solution uses a single-pass approach with a sliding window technique. It iterates through the array, identifying potential starting points of a mountain. For each starting point, it attempts to find an increasing sequence followed by a decreasing sequence. If both sequences are found, it calculates the length of the mountain and updates the maximum length found so far. If either the increasing or decreasing sequence is missing, the algorithm moves to the next potential starting point.

Step-by-Step Algorithm

Step 1: Initialize `max_len` to 0 to store the length of the longest mountain found so far and `i` to 0 to iterate through the array.
Step 2: The outer `while` loop iterates through the array while `i` is less than `n` (the length of the array).
Step 3: `base` is assigned the value of `i`. This marks the potential start of a mountain.
Step 4: The inner `while` loop finds the increasing slope (upslope) by incrementing `i` as long as `i + 1` is within bounds and `arr[i] < arr[i+1]`.
Step 5: After finding the upslope, check if `i > base`. If it's true, an upslope was found. Set `peak = i`.
Step 6: The next inner `while` loop finds the decreasing slope (downslope) by incrementing `i` as long as `i + 1` is within bounds and `arr[i] > arr[i+1]`.
Step 7: After finding the downslope, check if `i > peak`. If true, both upslope and downslope were found, meaning a valid mountain exists.
Step 8: If a valid mountain exists, calculate its length (`i - base + 1`) and update `max_len` if the current mountain is longer than the previous `max_len`.
Step 9: If `i == base`, it means no upslope was found, so increment `i` to move to the next element. This avoids getting stuck in an infinite loop when the current element is not the start of any ascending sequence.
Step 10: Repeat steps 3-9 until the entire array has been processed. Return `max_len`.

Key Insights

Insight 1: Iterate through the array and identify potential 'peaks' which form the mountain's apex.
Insight 2: Use two pointers, one to find the increasing slope leading up to the peak and another to find the decreasing slope after the peak.
Insight 3: Handle cases where there is only an increasing or decreasing sequence, or where no increasing/decreasing sequence exists at all.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Dynamic Programming, Enumeration.

Companies

Asked at: Databricks, Faire, SoFi.

Longest Mountain in Array | LeetCode 845

Medium

Array Two Pointers Dynamic Programming Enumeration

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }
        
        int max_len = 0;
        int i = 0;
        
        while (i < n) {
            int base = i;
            
            // 1. Find an upslope
            while (i + 1 < n && arr[i] < arr[i+1]) {
                i += 1;
            }
            
            // If an upslope was found (i moved from base)
            if (i > base) {
                int peak = i;
                
                // 2. Find a downslope
                while (i + 1 < n && arr[i] > arr[i+1]) {
                    i += 1;
                }
                
                // If a downslope was also found (i moved from peak)
                if (i > peak) {
                    // A valid mountain is found
                    max_len = Math.max(max_len, i - base + 1);
                }
                
                // If no downslope, it was just an upslope.
                // In either case (mountain or just upslope), i is now at the end of the feature.
                // The outer loop will continue scanning from this new position of i.
            
            } else { // i == base, no upslope found from this point
                // Move to the next element
                i += 1;
            }
        }
        
        return max_len;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 845: Longest Mountain in Array - Detailed explanation and solution approaches.

Topics

Array Two Pointers Dynamic Programming Enumeration

Companies

DatabricksFaireSoFi

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:845

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

10 steps

1
Step 1: Initialize `max_len` to 0 to store the length of the longest mountain found so far and `i` to 0 to iterate through the array.
2
Step 2: The outer `while` loop iterates through the array while `i` is less than `n` (the length of the array).
3
Step 3: `base` is assigned the value of `i`. This marks the potential start of a mountain.
4
Step 4: The inner `while` loop finds the increasing slope (upslope) by incrementing `i` as long as `i + 1` is within bounds and `arr[i] < arr[i+1]`.
5
Step 5: After finding the upslope, check if `i > base`. If it's true, an upslope was found. Set `peak = i`.
6
Step 6: The next inner `while` loop finds the decreasing slope (downslope) by incrementing `i` as long as `i + 1` is within bounds and `arr[i] > arr[i+1]`.
7
Step 7: After finding the downslope, check if `i > peak`. If true, both upslope and downslope were found, meaning a valid mountain exists.
8
Step 8: If a valid mountain exists, calculate its length (`i - base + 1`) and update `max_len` if the current mountain is longer than the previous `max_len`.
9
Step 9: If `i == base`, it means no upslope was found, so increment `i` to move to the next element. This avoids getting stuck in an infinite loop when the current element is not the start of any ascending sequence.
10
Step 10: Repeat steps 3-9 until the entire array has been processed. Return `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)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the array in a single pass, and the inner loops move the index `i` forward without resetting it. This ensures that each element is visited a limited number of times, leading to a linear time complexity. The space complexity is constant because the algorithm only uses a fixed number of variables, regardless of the size of the input array.

📖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

Dynamic Programming

We can use dynamic programming to calculate the length of the increasing and decreasing subsequences at each index. Then, for each index, we can combine the lengths of the increasing and decreasing subsequences to potentially find a mountain. This approach requires two arrays: one for increasing lengths and one for decreasing lengths.

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

Trade-offs: The dynamic programming approach uses O(n) space, making it less space-efficient than the provided O(1) space solution. However, it might be easier to understand for some.

✨

Key Insights

1Insight 1: Iterate through the array and identify potential 'peaks' which form the mountain's apex.
2Insight 2: Use two pointers, one to find the increasing slope leading up to the peak and another to find the decreasing slope after the peak.
3Insight 3: Handle cases where there is only an increasing or decreasing sequence, or where no increasing/decreasing sequence exists at all.

📚

Key Terms Explained

For Students

Array

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

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Empty array or array with fewer than 3 elements. The initial check `if n < 3: return 0` handles this by returning 0, as a mountain requires at least 3 elements.
Edge case 2: Array with all equal elements. The increasing and decreasing `while` loops won't execute, and `max_len` will remain 0, which is the correct result.
Edge case 3: Strictly increasing or strictly decreasing array. The algorithm will correctly identify that there's no mountain and return 0.
Edge case 4: Multiple mountains within the array. The algorithm correctly identifies each mountain and updates `max_len` accordingly, ensuring the longest mountain is found.
Edge case 5: Mountain starting at the very beginning or ending at the very end of the array. The algorithm handles these cases correctly by considering the array boundaries within the while loop conditions.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling edge cases where there is no upslope or downslope. Failing to increment `i` after encountering a flat or decreasing sequence can lead to infinite loops.

✗Common mistake 2: Not checking array boundaries within the while loops, leading to `IndexError` or `ArrayIndexOutOfBoundsException` errors.

✗Common mistake 3: Forgetting to add 1 to the difference `i - base` when calculating the length of the mountain.

✗Common mistake 4: Not initializing `max_len` to 0, which can lead to incorrect results if no mountain is found.

✅

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 patterns of upward and downward trends. A 'mountain' pattern could represent a temporary market surge followed by a correction.

🏦Real-world scenario 2: Analyzing sensor data from a machine to detect performance peaks and declines. A 'mountain' could indicate a period of high efficiency followed by a decrease due to wear and tear or other factors.

🎮Real-world scenario 3: Signal processing where you want to find patterns of increasing and decreasing signal strength. This algorithm could help identify signal peaks.

💡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

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

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

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

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: October 4, 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

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

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

@AlgoMasterJul 6

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

@InterviewProJun 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.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

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 "Longest Mountain in Array"?

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

🤖 Need help with this problem?