Search Blogs

Showing results for "Mountain Array"

Found 3 results

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Try the QuestionBefore reading the explanation, try solving the problem yourself:👉 https://leetcode.com/problems/peak-index-in-a-mountain-array/Solving it first helps strengthen your problem-solving intuition, especially for binary search problems.Problem StatementYou are given an integer array arr that is guaranteed to be a mountain array.A mountain array is defined as an array where:Elements strictly increase until a peak element.After the peak, elements strictly decrease.Example:[0, 2, 5, 7, 6, 3, 1] ^ peakYour task is to return the index of the peak element.Constraints3 <= arr.length <= 10^50 <= arr[i] <= 10^6arr is guaranteed to be a mountain arrayImportant implications:The peak always exists.There will be exactly one peak.The array strictly increases before the peak and strictly decreases after it.Example WalkthroughExample 1Inputarr = [0,1,0]Visualization0 1 0 ^Output1Example 2Inputarr = [0,2,1,0]Visualization0 2 1 0 ^Output1Example 3Inputarr = [0,10,5,2]Visualization0 10 5 2 ^Output1Understanding the Mountain Array StructureA mountain array always looks like this:increasing → peak → decreasingGraphically: peak /\ / \ / \Because of this structure:Before the peak → numbers increaseAfter the peak → numbers decreaseThis property makes the problem perfect for binary search.Approach 1 — Brute Force (Check Every Element)The simplest way is to check every element and determine if it is greater than its neighbors.AlgorithmTraverse the array from index 1 to n-2.For each element check:arr[i] > arr[i-1] AND arr[i] > arr[i+1]If true, return i.Implementationpublic int peakIndexInMountainArray(int[] arr) { for(int i = 1; i < arr.length - 1; i++){ if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){ return i; } } return -1;}Time ComplexityO(n)We may need to check every element.Space ComplexityO(1)Approach 2 — Linear Scan Using Increasing TrendSince the array first increases then decreases, we can detect where the increase stops.Key IdeaTraverse the array and check when:arr[i] > arr[i+1]This means we reached the peak.Implementationpublic int peakIndexInMountainArray(int[] arr) { for(int i = 0; i < arr.length - 1; i++){ if(arr[i] > arr[i+1]){ return i; } } return -1;}Example0 2 5 7 6 3 1 ^At index 3:7 > 6So index 3 is the peak.Time ComplexityO(n)Space ComplexityO(1)Approach 3 — Modified Binary Search (Optimal Solution)Because the array has a mountain structure, binary search can be used.Core IntuitionCompare:arr[mid]arr[mid+1]Two situations are possible.Case 1 — Increasing Slopearr[mid] < arr[mid+1]Example:1 3 5 7 ^This means the peak is on the right side.Move the search space to the right.left = mid + 1Case 2 — Decreasing Slopearr[mid] > arr[mid+1]Example:7 5 3 1 ^This means the peak lies on the left side including mid.right = midOptimal Java Implementationclass Solution { public int peakIndexInMountainArray(int[] arr) { int i = 0; int j = arr.length - 1; while(i < j){ int mid = i + (j - i) / 2; if(arr[mid] < arr[mid + 1]){ i = mid + 1; } else{ j = mid; } } return i; }}Step-by-Step ExampleArray[0,2,5,7,6,3,1]Iteration 1mid = 3arr[mid] = 7arr[mid+1] = 6Decreasing slope → move left.Iteration 2Search space narrows until:peak index = 3Time ComplexityO(log n)Binary search halves the search space each iteration.Space ComplexityO(1)No extra memory is required.Why Binary Search Works HereBecause the array behaves like a mountain curve.If you are standing at index mid:If the right side is higher, go right.If the left side is higher, go left.Eventually you will reach the top of the mountain (the peak).Key Takeaways✔ A mountain array increases then decreases✔ There is exactly one peak✔ Brute force and linear scan work in O(n) time✔ Binary search exploits the mountain structure✔ Optimal solution runs in O(log n) timeFinal ThoughtsThis problem is a classic example of binary search applied to array patterns rather than sorted values.Understanding the slope comparison technique used here will help solve other problems such as:Find Peak ElementMountain Array SearchBitonic Array ProblemsMastering these patterns significantly improves binary search problem-solving skills for coding interviews.

LeetCodeBinary SearchMountain ArrayMediumJava

LeetCode 845: Longest Mountain in Array – Java Solution with Peak Expansion

IntroductionA mountain subarray is a contiguous portion of an array that first strictly increases and then strictly decreases.For example:[1, 4, 7, 3, 2] ↑ PeakThe array increases toward 7 and decreases after 7, making it a valid mountain of length 5.The goal is to find the longest mountain subarray in the given array.This problem is useful for understanding an important array pattern:Find a valid peak → expand around the peak → calculate the complete structure.The follow-up also asks for a solution using one pass and O(1) extra space, making it a good interview problem for learning how to optimize array traversal.Problem StatementProblem Link -: longest mountain subarrayGiven an integer array arr, return the length of the longest contiguous subarray that forms a mountain.A valid mountain must:Contain at least 3 elements.Strictly increase toward a peak.Strictly decrease after the peak.Have the peak somewhere between the first and last element.For example:[2, 1, 4, 7, 3, 2, 5]The longest mountain is:[1, 4, 7, 3, 2] ↑ peakTherefore:Answer = 5Understanding the PatternThe most important observation is that every valid mountain has a peak.A peak is an element satisfying:arr[i - 1] < arr[i] > arr[i + 1]For example:1 4 7 3 2 ↑ iAt index 2:4 < 77 > 3Therefore, 7 is a peak.Once a peak is found, the complete mountain can be discovered by expanding: peak ↓1 → 4 → 7 ← 3 ← 2 ←──── ────→The left side continues while values are increasing toward the peak.The right side continues while values are decreasing away from the peak.Approach: Expand Around Every PeakThe solution can be divided into three simple steps.Find every possible peakTraverse the array from index 1 to n - 2.For every index:arr[i - 1] < arr[i] && arr[i] > arr[i + 1]If this condition is true, i is a valid mountain peak.Expand toward the leftStarting from the peak, move left while:arr[left] > arr[left - 1]This finds how far the increasing portion extends.Expand toward the rightStarting from the peak, move right while:arr[right] > arr[right + 1]This finds how far the decreasing portion extends.The peak is counted from both sides, so:mountain length = leftLength + rightLength - 1Java SolutionThe following implementation follows the peak-expansion approach while keeping the extra space at O(1).class Solution { // Finds how far the mountain extends toward the left public int lef(int st, int[] arr) { int len = 1; // Keep moving left while the sequence is strictly increasing // toward the peak. while (st > 0 && arr[st] > arr[st - 1]) { len++; st--; } return len; } // Finds how far the mountain extends toward the right public int righ(int st, int[] arr) { int len = 1; // Keep moving right while the sequence is strictly decreasing // after the peak. while (st < arr.length - 1 && arr[st] > arr[st + 1]) { len++; st++; } return len; } public int longestMountain(int[] arr) { // A mountain must contain at least 3 elements. if (arr.length < 3) { return 0; } int ans = 0; // The first and last elements cannot be peaks, // so start from index 1 and stop at n - 2. for (int i = 1; i < arr.length - 1; i++) { // Check whether arr[i] is a valid peak. if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) { // Count the increasing part including the peak. int left = lef(i, arr); // Count the decreasing part including the peak. int right = righ(i, arr); // The peak is counted twice, so subtract 1. int mountainLength = left + right - 1; ans = Math.max(ans, mountainLength); } } return ans; }}Dry RunConsider:arr = [2, 1, 4, 7, 3, 2, 5]Start scanning from index 1.Index 12 1 4 ↑1 is not a peak because:2 < 1 ❌Move forward.Index 22 1 4 7 3 2 5 ↑For 4:1 < 4 > 7Not a peak.Index 32 1 4 7 3 2 5 ↑For 7:4 < 7 > 3So 7 is a valid peak.Expand leftStarting at 7:1 < 4 < 7The left side is:[1, 4, 7]Length:3Expand rightStarting at 7:7 > 3 > 2The right side is:[7, 3, 2]Length:3The peak 7 was counted twice:3 + 3 - 1 = 5Therefore:Longest mountain = 5Why the Peak Is Counted TwiceThis is an important detail in the implementation.Suppose the mountain is:1 4 7 3 2 ↑ peakThe left traversal counts:1 4 7The right traversal counts:7 3 2Adding them gives:3 + 3 = 6But the 7 belongs to both sections.Therefore:6 - 1 = 5Hence:left + right - 1Complexity AnalysisTime ComplexityThe overall complexity is:O(n)Although the implementation expands left and right whenever a peak is found, each increasing/decreasing section belongs to a particular mountain structure and the total traversal remains linear.Space ComplexityOnly a few integer variables are used:O(1)No auxiliary array, HashMap, HashSet, or other data structure is required.One-Pass OptimizationThe same problem can also be solved using a direct one-pass approach.Instead of explicitly expanding from every peak, maintain:the length of the current increasing sectionthe length of the current decreasing sectionWhen an increasing sequence changes into a decreasing sequence, a mountain has been formed.A compact implementation is:class Solution { public int longestMountain(int[] arr) { int n = arr.length; int ans = 0; int up = 0; int down = 0; for (int i = 1; i < n; i++) { // If the sequence starts increasing after a decrease, // begin tracking a new mountain. if (arr[i] > arr[i - 1]) { if (down > 0) { up = 0; down = 0; } up++; } // Continue the decreasing part of the mountain. else if (arr[i] < arr[i - 1] && up > 0) { down++; // A valid mountain requires both an increasing // and decreasing portion. ans = Math.max(ans, up + down + 1); } // Equal adjacent elements break a mountain completely. else { up = 0; down = 0; } } return ans; }}This approach directly satisfies the follow-up requirement:Time = O(n)Space = O(1)Common MistakesTreating a simple increasing sequence as a mountain1 2 3 4 5This is not a mountain because there is no decreasing portion.Treating a simple decreasing sequence as a mountain5 4 3 2 1This is also not a mountain because there is no increasing portion.Allowing equal elements1 3 3 2This is not a valid mountain because the increase must be strict.The conditions require:<>not:<=>=Forgetting the minimum lengthA mountain must contain at least three elements:increasing part + peak + decreasing partTherefore:[1, 2] → invalid[2, 1] → invalid[1, 2, 1] → validInterview TipThe key to this problem is not the code itself but recognizing the peak structure.Whenever a problem describes something like:increasing → peak → decreasinga useful first thought is:Can the middle element be treated as a peak and the structure be expanded from there?This transforms a complicated subarray condition into two simple directional scans.For interview optimization questions, it is also useful to recognize that the same structure can often be tracked using a few variables instead of repeatedly constructing subarrays.ConclusionThe Longest Mountain in Array problem demonstrates an important array technique: identifying a structural peak and analyzing the elements around it.The main ideas are:A mountain must have a valid peak.The left side must be strictly increasing.The right side must be strictly decreasing.Expanding from each peak provides an intuitive solution.The problem can also be optimized into a true one-pass O(n), O(1) solution.The most important pattern to remember is:Increasing → Peak → DecreasingOnce that pattern becomes familiar, similar problems involving peaks, valleys, increasing/decreasing runs, and subarray structures become significantly easier to recognize.

LeetCodeJavaArraysTwo PointersMedium

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Try the QuestionBefore reading the explanation, try solving the problem yourself:👉 https://leetcode.com/problems/find-peak-element/Attempting the problem first helps develop algorithmic intuition, especially for binary search problems.Problem StatementYou are given a 0-indexed integer array nums.Your task is to find the index of a peak element.What is a Peak Element?A peak element is an element that is strictly greater than its immediate neighbors.For an element nums[i] to be a peak:nums[i] > nums[i-1]nums[i] > nums[i+1]However, the array boundaries have a special rule.Boundary RuleYou can imagine that:nums[-1] = -∞nums[n] = -∞This means:The first element only needs to be greater than the second element.The last element only needs to be greater than the second last element.Constraints1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1nums[i] != nums[i + 1] for all valid iImportant implications:Adjacent elements are never equal.The array always has at least one peak.Understanding the Problem with ExamplesExample 1Inputnums = [1,2,3,1]Visualization1 2 3 1^Here:3 > 23 > 1So 3 is a peak element.Output2(index of value 3)Example 2Inputnums = [1,2,1,3,5,6,4]Visualization1 2 1 3 5 6 4^ ^Possible peaks:26Valid outputs:1 or 5Either peak index is acceptable.Key ObservationsImportant facts about peak elements:Every array must contain at least one peak.If numbers keep increasing, the last element will be a peak.If numbers keep decreasing, the first element will be a peak.If the array has ups and downs, peaks exist in the middle.This guarantees a solution exists.Approach 1 — Linear Scan (Brute Force)The simplest approach is to check each element and see whether it satisfies the peak condition.AlgorithmTraverse the array.Check if the current element is greater than neighbors.Return the index if found.Examplenums = [1,2,3,1]Check:1 < 22 < 33 > 2 and 3 > 1 → PeakImplementationpublic int findPeakElement(int[] nums) {for(int i = 0; i < nums.length; i++){boolean left = (i == 0) || nums[i] > nums[i-1];boolean right = (i == nums.length-1) || nums[i] > nums[i+1];if(left && right){return i;}}return -1;}Time ComplexityO(n)Space ComplexityO(1)Although simple, this solution does not satisfy the required O(log n) complexity.Approach 2 — Binary Search Using Peak ConditionsInstead of scanning the entire array, we can use binary search.Key IdeaIf we are at index mid, compare it with the neighbors.Three situations may occur.Case 1 — Peak Foundnums[mid-1] < nums[mid] > nums[mid+1]Then:mid is the peakCase 2 — Increasing Slopenums[mid] < nums[mid+1]Example:1 3 5 7^This means the peak must exist on the right side.Move search to the right.Case 3 — Decreasing Slopenums[mid] < nums[mid-1]Example:7 5 3 1^Peak exists on the left side.Move search to the left.Implementationint i = 1;int j = nums.length - 2;while(i <= j){int mid = i + (j - i)/2;if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]){return mid;}else if(nums[mid] < nums[mid+1]){i = mid + 1;}else{j = mid - 1;}}Time ComplexityO(log n)Space ComplexityO(1)Approach 3 — Optimized Binary Search (Most Elegant Solution)A simpler and more elegant version of binary search exists.Core IntuitionCompare:nums[mid]nums[mid + 1]Two possibilities exist.Case 1 — Increasing Slopenums[mid] < nums[mid+1]Example:1 2 3 4^The peak must exist on the right side.Move:left = mid + 1Case 2 — Decreasing Slopenums[mid] > nums[mid+1]Example:4 3 2 1^Peak exists on the left side including mid.Move:right = midThis gradually narrows down to the peak.Final Optimized Implementationclass Solution {public int findPeakElement(int[] nums) {int i = 0;int j = nums.length - 1;while(i < j){int mid = i + (j - i) / 2;if(nums[mid] < nums[mid + 1]){i = mid + 1;}else{j = mid;}}return i;}}Step-by-Step ExampleArray[1,2,1,3,5,6,4]Iteration 1mid = 3nums[mid] = 3nums[mid+1] = 5Increasing slope → move right.Iteration 2mid = 5nums[mid] = 6nums[mid+1] = 4Decreasing slope → move left.Eventually:peak index = 5Value:6Why This Binary Search WorksThe array behaves like a mountain landscape.Example visualization:/\/ \/ \__If you stand at mid:If the right side is higher, go right.If the left side is higher, go left.This guarantees that you will eventually reach a peak.Time ComplexityO(log n)Each iteration cuts the search space in half.Space ComplexityO(1)Only a few variables are used.Key Takeaways✔ A peak element is greater than its neighbors✔ The array always contains at least one peak✔ Binary search can be applied using slope comparison✔ The optimized solution only compares nums[mid] and nums[mid+1]✔ The final algorithm runs in O(log n) timeFinal ThoughtsThis problem is an excellent example of applying binary search beyond sorted arrays.Instead of searching for a value, binary search is used here to locate a structural property of the array (a peak).Understanding this pattern is extremely valuable because similar logic appears in many interview problems involving:Mountain arraysBitonic arraysOptimization search problemsMastering this approach will significantly improve your binary search problem-solving skills for technical interviews.

LeetCodeBinary SearchMediumJava