Search Blogs

Showing results for "Peaks and Valleys"

Found 2 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