Search Blogs

Showing results for "Peaks and Valleys"

Found 3 results

LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation

IntroductionLeetCode 3751 introduces an interesting digit-based pattern problem where we calculate the total waviness of numbers inside a given range.This problem combines:Digit traversalPattern recognitionPeaks and valleys logicString manipulationBrute force iterationThe problem is straightforward once we clearly understand how peaks and valleys work.Problem StatementYou are given two integers:num1 and num2representing the inclusive range:[num1, num2]For every number:A digit is called a peak if it is strictly greater than both neighbors.A digit is called a valley if it is strictly smaller than both neighbors.The first and last digits can never be peaks or valleys.Return the total waviness across all numbers in the range.ExampleInputnum1 = 120num2 = 130Output3ExplanationNumbers contributing to waviness:120 → 2 is a peak → waviness = 1121 → 2 is a peak → waviness = 1130 → 3 is a peak → waviness = 1Total:1 + 1 + 1 = 3Understanding Peaks and ValleysPeak ConditionA digit is a peak if:digit > left neighborANDdigit > right neighborExample:484Here:8 > 48 > 4So 8 is a peak.Valley ConditionA digit is a valley if:digit < left neighborANDdigit < right neighborExample:202Here:0 < 20 < 2So 0 is a valley.Key ObservationWe only need to check:index 1 to length-2because:First digit has no left neighborLast digit has no right neighborIntuitionThe simplest way:Iterate through every number in the rangeConvert number into charactersCheck each middle digitCount peaks and valleysAdd to final answerSince constraints are small:num2 <= 10^5a brute force approach works efficiently.Java Solutionclass Solution { public int totalWaviness(int num1, int num2) { int ans = 0; if(num1 == num2) { int temp = num1; String c = Integer.toString(temp); char[] arr = c.toCharArray(); for(int i = 1; i < arr.length - 1; i++) { if((arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) || (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])) { ans++; } } return ans; } for(int i = num1; i <= num2; i++) { String c = Integer.toString(i); char[] carr = c.toCharArray(); for(int j = 1; j < carr.length - 1; j++) { if((carr[j] < carr[j - 1] && carr[j] < carr[j + 1]) || (carr[j] > carr[j - 1] && carr[j] > carr[j + 1])) { ans++; } } } return ans; }}Step-by-Step ExplanationStep 1: Iterate Through Rangefor(int i = num1; i <= num2; i++)Process every number.Step 2: Convert Number to Character ArrayString c = Integer.toString(i);char[] carr = c.toCharArray();This makes digit comparison easier.Step 3: Check Middle Digitsfor(int j = 1; j < carr.length - 1; j++)Skip first and last digits.Step 4: Check Peak or Valley(carr[j] < carr[j-1] && carr[j] < carr[j+1])OR(carr[j] > carr[j-1] && carr[j] > carr[j+1])If true:ans++;Dry RunInputnum1 = 198num2 = 202Number 198Digits:1 9 8Check 9:9 > 19 > 8Peak found.Waviness:1Number 1991 9 99 is not strictly greater than right neighbor.No waviness.Number 2012 0 10 is smaller than both neighbors.Valley found.Number 2022 0 2Again:0 < 20 < 2Valley found.Final Answer198 → 1201 → 1202 → 1Total = 3Time Complexity AnalysisLet:N = num2 - num1 + 1D = number of digitsTime ComplexityO(N × D)At most:D = 6which is very small.Efficient for constraints.Space ComplexityO(D)due to character array conversion.Why Brute Force Works HereConstraints are small:num2 <= 100000So checking every number directly is acceptable.For larger constraints:Digit DP would be needed.But here:Simplicity is better.Common Mistakes1. Including First or Last DigitThese digits cannot be peaks or valleys.2. Using Non-Strict ComparisonWrong:>=<=Correct:><because definition says:strictly greaterstrictly smaller3. Forgetting Both ConditionsNeed to check:PeakValleyEdge CasesSingle Digit NumbersWaviness:0because fewer than 3 digits.Repeated DigitsExample:111No peak or valley.Alternating DigitsExample:4848Produces multiple waviness counts.Interview ExplanationIn interviews explain:Since the constraints are small, we can directly iterate through every number, convert it into digits, and count peaks and valleys by checking neighboring digits.This demonstrates:Observation skillsConstraint analysisClean implementationConclusionLeetCode 3751 is a clean implementation problem focused on:Digit traversalPattern recognitionPeaks and valleysBrute force optimizationThe key insight is:A digit contributes to waviness only if it is strictly greater or strictly smaller than both immediate neighbors.Once this condition is understood, the implementation becomes very straightforward.

LeetCodeJavaStringPeaks and ValleysBrute Force SolutionDigit ProblemsMediumArray

LeetCode 122 — Best Time to Buy and Sell Stock II | Every Approach Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/Understanding the ProblemYou are given an array prices where prices[i] is the stock price on day i. Unlike the classic version, here you can make as many transactions as you want — but you can only hold one share at a time. You may buy and sell on the same day.Goal: Return the maximum total profit achievable.Key Rules:You can buy and sell multiple times.You cannot hold more than one share at a time — you must sell before buying again.If no profit is possible, return 0.Constraints:1 ≤ prices.length ≤ 3 × 10⁴0 ≤ prices[i] ≤ 10⁴How This Differs From LeetCode 121 #In LeetCode 121, you were limited to exactly one buy-sell transaction. Here, the restriction is lifted — you can participate in as many transactions as you want. This fundamentally changes the strategy. Instead of hunting for the single best pair, you want to capture every profitable price movement in the array.The Core InsightLook at the price chart mentally. Every time the price goes up from one day to the next, that's money on the table. The question is — how do you collect all of it?The answer is surprisingly simple: add every single upward price difference to your profit. If prices go up three days in a row from 1 → 3 → 5 → 8, you collect (3-1) + (5-3) + (8-5) = 7, which is exactly the same as buying at 1 and selling at 8. You never miss a gain.This is the foundation of all approaches below.Approach 1 — Simple Greedy (Collect Every Upward Move)Intuition: Every time prices[i] > prices[i-1], add the difference to profit. You are essentially buying at every valley and selling at every peak, collecting each individual daily gain without explicitly tracking buy/sell days.Why it works: The total gain from buying at day 0 and selling at day N is mathematically equal to the sum of all positive daily differences in between. You never lose anything by collecting gains day by day.Example: prices = [1, 2, 3, 4, 5] Daily gains: (2-1) + (3-2) + (4-3) + (5-4) = 1+1+1+1 = 4 Same as buying at 1 and selling at 5 directly.class Solution {public int maxProfit(int[] prices) {int maxProfit = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}return maxProfit;}}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — no extra space used.This is the cleanest and most recommended solution for this problem.Approach 2 — Peak Valley ApproachIntuition: Instead of collecting every daily gain, explicitly find every valley (local minimum) to buy at and every peak (local maximum) to sell at. You buy when price stops falling and sell when price stops rising.How it works: Scan through the array. When you find a valley (prices[i] ≤ prices[i+1]), that is your buy point. Then keep going until you find a peak (prices[i] ≥ prices[i+1]) — that is your sell point. Add the peak minus valley to profit. Repeat.Example: prices = [7, 1, 5, 3, 6, 4]Valley at index 1 (price = 1), Peak at index 2 (price = 5) → profit += 4 Valley at index 3 (price = 3), Peak at index 4 (price = 6) → profit += 3 Total = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int maxProfit = 0;int valley, peak;while (i < prices.length - 1) {while (i < prices.length - 1 && prices[i] >= prices[i + 1]) {i++;}valley = prices[i];while (i < prices.length - 1 && prices[i] <= prices[i + 1]) {i++;}peak = prices[i];maxProfit += peak - valley;}return maxProfit;}}Time Complexity: O(N) — each element is visited at most twice. Space Complexity: O(1) — no extra space used.This approach is more explicit and easier to visualize on a graph, though the code is slightly more involved than Approach 1.Approach 3 — Two PointerIntuition: Use two pointers i (buy day) and j (sell day). Move j forward one step at a time. Whenever prices[j] > prices[i], you have a profitable window — add the profit and immediately move i to j (simulate selling and rebuying at the same price on the same day). Whenever prices[j] < prices[i], just move i to j since a cheaper buy day has been found.Why moving i to j after every profitable sale works: Selling at j and immediately rebuying at j costs nothing (profit of 0 for that rebuy). But it positions i at the latest price so you can catch the next upward movement. This correctly simulates collecting every upward segment.Example: prices = [7, 1, 5, 3, 6, 4]i=0, j=1 → 7 > 1, move i to 1. j=2. i=1, j=2 → 1 < 5, profit += 4, move i to 2. j=3. i=2, j=3 → 5 > 3, move i to 3. j=4. i=3, j=4 → 3 < 6, profit += 3, move i to 4. j=5. i=4, j=5 → 6 > 4, move i to 5. j=6. Loop ends. Total profit = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int j = 1;int maxProfit = 0;while (i < j && j < prices.length) {if (prices[i] > prices[j]) {i = j;} else {maxProfit += prices[j] - prices[i];i = j;}j++;}return maxProfit;}}Time Complexity: O(N) — j traverses the array exactly once. Space Complexity: O(1) — only three integer variables.This approach is functionally identical to Approach 1 — both collect every upward daily movement. The two pointer framing makes the buy/sell simulation more explicit.Approach 4 — Dynamic ProgrammingIntuition: At any point in time, you are in one of two states — either you hold a stock or you do not hold a stock. Define two DP values updated each day:hold = maximum profit if you are currently holding a stock at the end of this day.cash = maximum profit if you are not holding any stock at the end of this day.Transitions:To hold on day i: either you already held yesterday, or you buy today. hold = max(hold, cash - prices[i])To have cash on day i: either you already had cash yesterday, or you sell today. cash = max(cash, hold + prices[i])Initialization:hold = -prices[0] (you bought on day 0)cash = 0 (you did nothing on day 0)class Solution {public int maxProfit(int[] prices) {int hold = -prices[0];int cash = 0;for (int i = 1; i < prices.length; i++) {hold = Math.max(hold, cash - prices[i]);cash = Math.max(cash, hold + prices[i]);}return cash;}}Time Complexity: O(N) — single pass. Space Complexity: O(1) — only two variables maintained at each step.This approach is the most powerful because it extends naturally to harder variants of this problem — like LeetCode 309 (with cooldown) and LeetCode 714 (with transaction fee) — where greedy no longer works and you need explicit state tracking.Dry Run — All Approaches on Example 1Input: prices = [7, 1, 5, 3, 6, 4], Expected Output: 7Approach 1 (Simple Greedy): Day 1→2: 1 - 7 = -6, skip. Day 2→3: 5 - 1 = 4, add. profit = 4. Day 3→4: 3 - 5 = -2, skip. Day 4→5: 6 - 3 = 3, add. profit = 7. Day 5→6: 4 - 6 = -2, skip. Result = 7 ✅Approach 4 (DP): Start: hold = -7, cash = 0. Day 1 (price=1): hold = max(-7, 0-1) = -1. cash = max(0, -1+1) = 0. Day 2 (price=5): hold = max(-1, 0-5) = -1. cash = max(0, -1+5) = 4. Day 3 (price=3): hold = max(-1, 4-3) = 1. cash = max(4, 1+3) = 4. Day 4 (price=6): hold = max(1, 4-6) = 1. cash = max(4, 1+6) = 7. Day 5 (price=4): hold = max(1, 7-4) = 3. cash = max(7, 3+4) = 7. Result = 7 ✅Comparison of All ApproachesApproach 1 — Simple Greedy Code simplicity: Simplest possible. Best for interviews — clean and readable. Does not extend to constrained variants.Approach 2 — Peak Valley Code simplicity: Moderate. Best for visual/conceptual understanding. Slightly verbose but maps directly to a chart.Approach 3 — Two Pointer Code simplicity: Simple. Explicit simulation of buy/sell actions. Functionally identical to Approach 1.Approach 4 — Dynamic Programming Code simplicity: Moderate. Most powerful — extends to cooldown, fee, and k-transaction variants. Worth mastering for the full stock problem series.Common Mistakes to AvoidThinking you need to find exact buy/sell days: The problem only asks for maximum profit — you do not need to output which days you traded. This frees you to use the simple greedy sum approach.Trying to find the global minimum and maximum: Unlike LeetCode 121, the single best buy-sell pair is not always optimal here. You need to capture multiple smaller movements, not one big one.Holding more than one share: You cannot buy twice in a row without selling in between. In Approach 3, moving i = j after every transaction ensures you always sell before the next buy.Not handling a flat or decreasing array: If prices never go up, all approaches correctly return 0 — the greedy sum adds nothing, peak-valley finds no valid pairs, and DP's cash stays at 0.Complexity SummaryAll four approaches run in O(N) time and O(1) space. The difference between them is conceptual clarity and extensibility, not raw performance.The Full Stock Problem Series on LeetCodeThis problem is part of a six-problem series. Understanding them in order builds intuition progressively:LeetCode 121 — One transaction only. Two pointer / min tracking greedy. [ Blog is also avaliable on this - Read Now]LeetCode 123 — At most 2 transactions. DP with explicit state for two transactions. [ Blog is also avaliable on this - Read Now]LeetCode 188 — At most k transactions. Generalized DP.LeetCode 309 — Unlimited transactions with cooldown after selling. DP with three states.LeetCode 714 — Unlimited transactions with a fee per transaction. DP with adjusted transitions.Each problem adds one constraint on top of the previous. If you understand the DP state machine from Approach 4 deeply, every problem in this series becomes a small modification of the same framework.Key Takeaways✅ When transactions are unlimited, collect every upward daily price movement — that is the global optimum.✅ The sum of all positive daily differences equals the sum of all peak-valley differences. Both are provably optimal.✅ The two pointer approach explicitly simulates buy and sell events — moving i = j after a sale means selling and immediately rebuying at the same price to stay positioned for the next gain.✅ The DP approach with hold and cash states is the most versatile — it is the foundation for every harder variant in the stock series.✅ Always initialize maxProfit = 0 so that the no-profit case (prices only falling) is handled correctly without extra conditions.Happy Coding! Once you have this problem locked down, the rest of the stock series will feel like natural extensions rather than new problems entirely. 🚀

LeetCodeGreedyTwo PointersDynamic ProgrammingMediumJavaArrays

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