Wiggle Subsequence

🎯

Wiggle Subsequence

mediumGREEDYAmazonGoogle

Imagine tracking stock prices that fluctuate daily and wanting to find the longest sequence of ups and downs to maximize trading opportunities.

💡 This problem asks for the longest subsequence where the differences between consecutive numbers strictly alternate between positive and negative. Beginners often struggle because it looks like a dynamic programming problem but can be solved greedily by understanding the pattern of peaks and valleys.

📋

Problem Statement

Given an integer array nums, return the length of the longest wiggle subsequence. A wiggle sequence is one where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1,7,4,9,2,5]"

Output6

The entire sequence is a wiggle sequence: differences are +6, -3, +5, -7, +3 alternating signs.

Input"[1,17,5,10,13,15,10,5,16,8]"

Output7

One longest wiggle subsequence is [1,17,10,13,10,16,8].

Input"[1,2,3,4,5,6,7,8,9]"

Output2

Longest wiggle subsequence is any two consecutive numbers since all differences are positive.

• Single element array → output 1
• All elements equal → output 1
• Strictly increasing array → output 2
• Strictly decreasing array → output 2

⚠️

Common Mistakes

Not handling equal consecutive elements properly

Incorrectly counting or skipping wiggles, leading to wrong answer

✅ Ignore zero differences when updating counts or last difference

Confusing subsequence with substring

Trying to find contiguous wiggle sequences instead of subsequences, missing longer solutions

✅ Remember subsequences can skip elements, so do not require contiguous indices

Using brute force in interviews without pruning

Code runs too slowly and times out

✅ Explain brute force but quickly move to greedy approach

Incorrect initialization of counters or last difference

Off-by-one errors leading to wrong counts

✅ Initialize counts to 1 and last difference to 0 carefully

Not testing edge cases like single element or all equal elements

Code may crash or return wrong results

✅ Add explicit checks for these cases

🧠

Brute Force (Pure Recursion)

💡 This approach explores all subsequences to find the longest wiggle subsequence. It is extremely inefficient but helps understand the problem deeply by considering every possibility.

Intuition

Try every subsequence by recursively deciding whether to include or exclude each element, checking if the wiggle property holds.

Algorithm

1. Start from the first element and recursively explore subsequences.
2. At each step, decide to include the current element if it forms a wiggle with the previous included element.
3. Keep track of the last difference sign to ensure alternation.
4. Return the maximum length found among all valid subsequences.

💡 The recursion explores all subsequences, which is conceptually simple but computationally expensive.

</>

Code

def wiggleMaxLength(nums):
    def dfs(index, prev, diff):
        if index == len(nums):
            return 0
        taken = 0
        if diff == 0 or (nums[index] - prev) * diff < 0:
            taken = 1 + dfs(index + 1, nums[index], nums[index] - prev)
        not_taken = dfs(index + 1, prev, diff)
        return max(taken, not_taken)

    if not nums:
        return 0
    return 1 + dfs(1, nums[0], 0)

# Driver code
if __name__ == '__main__':
    print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6

Line Notes

def dfs(index, prev, diff):Defines recursive helper to explore subsequences from current index

if index == len(nums):Base case: reached end of array, no more elements to consider

if diff == 0 or (nums[index] - prev) * diff < 0:Check if current difference alternates sign or is first difference

taken = 1 + dfs(index + 1, nums[index], nums[index] - prev)Include current element and recurse

not_taken = dfs(index + 1, prev, diff)Exclude current element and recurse

return max(taken, not_taken)Choose the better option between taking or skipping current element

if not nums:Handle empty input edge case

return 1 + dfs(1, nums[0], 0)Start recursion with first element included and no previous difference

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        return nums.length == 0 ? 0 : 1 + dfs(nums, 1, nums[0], 0);
    }

    private int dfs(int[] nums, int index, int prev, int diff) {
        if (index == nums.length) return 0;
        int taken = 0;
        if (diff == 0 || (nums[index] - prev) * diff < 0) {
            taken = 1 + dfs(nums, index + 1, nums[index], nums[index] - prev);
        }
        int notTaken = dfs(nums, index + 1, prev, diff);
        return Math.max(taken, notTaken);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wiggleMaxLength(new int[]{1,7,4,9,2,5})); // Expected: 6
    }
}

Line Notes

public int wiggleMaxLength(int[] nums)Entry point for solution, handles empty array

return nums.length == 0 ? 0 : 1 + dfs(...)Start recursion with first element included

private int dfs(int[] nums, int index, int prev, int diff)Recursive helper exploring subsequences

if (index == nums.length) return 0;Base case: no more elements to process

if (diff == 0 || (nums[index] - prev) * diff < 0)Check if current difference alternates sign

taken = 1 + dfs(...)Include current element and recurse

int notTaken = dfs(...)Exclude current element and recurse

return Math.max(taken, notTaken);Choose best option

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dfs(const vector<int>& nums, int index, int prev, int diff) {
        if (index == nums.size()) return 0;
        int taken = 0;
        if (diff == 0 || (nums[index] - prev) * diff < 0) {
            taken = 1 + dfs(nums, index + 1, nums[index], nums[index] - prev);
        }
        int notTaken = dfs(nums, index + 1, prev, diff);
        return max(taken, notTaken);
    }

    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        return 1 + dfs(nums, 1, nums[0], 0);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,7,4,9,2,5};
    cout << sol.wiggleMaxLength(nums) << endl; // Expected: 6
    return 0;
}

Line Notes

int dfs(const vector<int>& nums, int index, int prev, int diff)Recursive helper exploring subsequences

if (index == nums.size()) return 0;Base case: no more elements

if (diff == 0 || (nums[index] - prev) * diff < 0)Check if difference alternates sign

taken = 1 + dfs(...)Include current element and recurse

int notTaken = dfs(...)Exclude current element and recurse

return max(taken, notTaken);Choose the better option

if (nums.empty()) return 0;Handle empty input

return 1 + dfs(nums, 1, nums[0], 0);Start recursion with first element included

function wiggleMaxLength(nums) {
    function dfs(index, prev, diff) {
        if (index === nums.length) return 0;
        let taken = 0;
        if (diff === 0 || (nums[index] - prev) * diff < 0) {
            taken = 1 + dfs(index + 1, nums[index], nums[index] - prev);
        }
        let notTaken = dfs(index + 1, prev, diff);
        return Math.max(taken, notTaken);
    }
    if (nums.length === 0) return 0;
    return 1 + dfs(1, nums[0], 0);
}

// Test
console.log(wiggleMaxLength([1,7,4,9,2,5])); // Expected: 6

Line Notes

function dfs(index, prev, diff)Recursive helper to explore subsequences

if (index === nums.length) return 0;Base case: no more elements

if (diff === 0 || (nums[index] - prev) * diff < 0)Check if difference alternates sign

taken = 1 + dfs(...)Include current element and recurse

let notTaken = dfs(...)Exclude current element and recurse

return Math.max(taken, notTaken);Choose best option

if (nums.length === 0) return 0;Handle empty input

return 1 + dfs(1, nums[0], 0);Start recursion with first element included

⏱

Complexity

TimeO(2^n)

SpaceO(n)

Each element can be included or excluded, leading to exponential subsequences. Recursion stack depth is O(n).

💡 For n=20, this means over a million calls, which is impractical in interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Greedy Approach with Peak-Valley Counting

💡 This approach uses the insight that the longest wiggle subsequence corresponds to counting peaks and valleys in the array, allowing a linear time solution.

Intuition

Track the direction of differences and count changes in direction, which correspond to wiggles.

Algorithm

1. Initialize two counters: up and down to 1 (minimum wiggle length).
2. Iterate through the array from the second element.
3. If current element > previous, update up = down + 1.
4. If current element < previous, update down = up + 1.
5. Return the maximum of up and down.

💡 This method efficiently tracks wiggle lengths by updating counters based on the current difference sign.

</>

Code

def wiggleMaxLength(nums):
    if not nums:
        return 0
    up = down = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1
    return max(up, down)

# Driver code
if __name__ == '__main__':
    print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6

Line Notes

if not nums:Handle empty input edge case

up = down = 1Initialize counters for wiggle lengths starting at 1

for i in range(1, len(nums)):Iterate through array from second element

if nums[i] > nums[i - 1]:Current difference is positive, update up

up = down + 1Increase up count based on previous down count

elif nums[i] < nums[i - 1]:Current difference is negative, update down

down = up + 1Increase down count based on previous up count

return max(up, down)Return the maximum wiggle subsequence length

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wiggleMaxLength(new int[]{1,7,4,9,2,5})); // Expected: 6
    }
}

Line Notes

if (nums.length == 0) return 0;Handle empty input

int up = 1, down = 1;Initialize counters for wiggle lengths

for (int i = 1; i < nums.length; i++)Iterate through array from second element

if (nums[i] > nums[i - 1])Positive difference detected

up = down + 1;Update up count based on previous down

else if (nums[i] < nums[i - 1])Negative difference detected

down = up + 1;Update down count based on previous up

return Math.max(up, down);Return maximum wiggle length

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return max(up, down);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,7,4,9,2,5};
    cout << sol.wiggleMaxLength(nums) << endl; // Expected: 6
    return 0;
}

Line Notes

if (nums.empty()) return 0;Handle empty input

int up = 1, down = 1;Initialize counters for wiggle lengths

for (int i = 1; i < nums.size(); i++)Iterate from second element

if (nums[i] > nums[i - 1])Positive difference detected

up = down + 1;Update up count based on previous down

else if (nums[i] < nums[i - 1])Negative difference detected

down = up + 1;Update down count based on previous up

return max(up, down);Return maximum wiggle length

function wiggleMaxLength(nums) {
    if (nums.length === 0) return 0;
    let up = 1, down = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            up = down + 1;
        } else if (nums[i] < nums[i - 1]) {
            down = up + 1;
        }
    }
    return Math.max(up, down);
}

// Test
console.log(wiggleMaxLength([1,7,4,9,2,5])); // Expected: 6

Line Notes

if (nums.length === 0) return 0;Handle empty input

let up = 1, down = 1;Initialize counters for wiggle lengths

for (let i = 1; i < nums.length; i++)Iterate from second element

if (nums[i] > nums[i - 1])Positive difference detected

up = down + 1;Update up count based on previous down

else if (nums[i] < nums[i - 1])Negative difference detected

down = up + 1;Update down count based on previous up

return Math.max(up, down);Return maximum wiggle length

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space.

💡 For n=100000, this means 100000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its simplicity and efficiency.

🧠

Greedy with Explicit Direction Tracking

💡 This approach explicitly tracks the last difference sign and counts wiggles when the sign changes, making the logic very clear.

Intuition

Keep track of the last difference sign and increment count only when the current difference changes sign compared to the last.

Algorithm

1. Initialize count to 1 and last_diff to 0.
2. Iterate through the array from the second element.
3. Calculate current difference between current and previous element.
4. If current difference and last_diff have opposite signs, increment count and update last_diff.
5. Return count.

💡 This approach explicitly models the wiggle pattern by tracking sign changes, which is intuitive.

</>

Code

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
            count += 1
            last_diff = diff
    return count

# Driver code
if __name__ == '__main__':
    print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6

Line Notes

if not nums:Handle empty input

count = 1Start count at 1 for first element

last_diff = 0Initialize last difference sign as zero (no difference yet)

for i in range(1, len(nums)):Iterate from second element

diff = nums[i] - nums[i - 1]Calculate current difference

if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):Check if difference sign changed

count += 1Increment count on wiggle

last_diff = diffUpdate last difference sign

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;
        int count = 1;
        int lastDiff = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0)) {
                count++;
                lastDiff = diff;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wiggleMaxLength(new int[]{1,7,4,9,2,5})); // Expected: 6
    }
}

Line Notes

if (nums.length == 0) return 0;Handle empty input

int count = 1;Initialize count for first element

int lastDiff = 0;Initialize last difference sign

for (int i = 1; i < nums.length; i++)Iterate from second element

int diff = nums[i] - nums[i - 1];Calculate current difference

if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0))Check for sign change

count++;Increment count on wiggle

lastDiff = diff;Update last difference

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int count = 1;
        int lastDiff = 0;
        for (int i = 1; i < nums.size(); i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0)) {
                count++;
                lastDiff = diff;
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,7,4,9,2,5};
    cout << sol.wiggleMaxLength(nums) << endl; // Expected: 6
    return 0;
}

Line Notes

if (nums.empty()) return 0;Handle empty input

int count = 1;Initialize count for first element

int lastDiff = 0;Initialize last difference sign

for (int i = 1; i < nums.size(); i++)Iterate from second element

int diff = nums[i] - nums[i - 1];Calculate current difference

if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0))Check for sign change

count++;Increment count on wiggle

lastDiff = diff;Update last difference

function wiggleMaxLength(nums) {
    if (nums.length === 0) return 0;
    let count = 1;
    let lastDiff = 0;
    for (let i = 1; i < nums.length; i++) {
        let diff = nums[i] - nums[i - 1];
        if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0)) {
            count++;
            lastDiff = diff;
        }
    }
    return count;
}

// Test
console.log(wiggleMaxLength([1,7,4,9,2,5])); // Expected: 6

Line Notes

if (nums.length === 0) return 0;Handle empty input

let count = 1;Initialize count for first element

let lastDiff = 0;Initialize last difference sign

for (let i = 1; i < nums.length; i++)Iterate from second element

let diff = nums[i] - nums[i - 1];Calculate current difference

if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0))Check for sign change

count++;Increment count on wiggle

lastDiff = diff;Update last difference

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through array with constant space to track last difference and count.

💡 This approach is efficient and easy to implement, suitable for large inputs.

Interview Verdict: Accepted

This approach is optimal and clearly shows understanding of the wiggle pattern.

📊

All Approaches - One-Glance Tradeoffs

💡 The greedy approaches (2 and 3) are optimal and should be coded in interviews. Brute force is only for conceptual understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy Peak-Valley Counting	O(n)	O(1)	No	No (length only)	Code this for optimal solution
3. Greedy with Explicit Direction Tracking	O(n)	O(1)	No	No (length only)	Alternative optimal approach, easy to explain

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the greedy solutions, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and ask about input constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient.Step 4: Present the greedy peak-valley counting approach.Step 5: Code the greedy solution and test with examples.Step 6: Discuss edge cases and possible follow-ups.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to recognize the wiggle pattern, optimize from brute force to greedy, and write clean, efficient code.

Common Follow-ups

• Can you reconstruct the actual longest wiggle subsequence? → Yes, by tracking elements during iteration.
• What if equal consecutive elements are allowed? → Adjust conditions to handle zero differences.
• Can you solve this with DP? → Yes, but greedy is more optimal here.
• What if the input is very large? → Greedy approach handles large inputs efficiently.

💡 These follow-ups test deeper understanding and ability to adapt your solution to variations.

🔍

Pattern Recognition

When to Use

1) Asked for longest subsequence with alternating up/down differences; 2) Differences strictly alternate signs; 3) Subsequence (not substring) allowed; 4) Input size large enough to require O(n) solution.

Signature Phrases

'differences between successive numbers strictly alternate''longest wiggle subsequence'

NOT This Pattern When

Problems asking for contiguous alternating sequences or maximum sum subsequences are different patterns.

Similar Problems

Longest Increasing Subsequence - also about subsequences but monotonicLongest Alternating Subsequence - similar alternating patternZigzag Conversion - pattern recognition in sequences

Practice

1. You are given a string and need to partition it into as many parts as possible so that each letter appears in at most one part. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm using last occurrence indices to determine partition boundaries

B. Backtracking to try all possible partitions and select the best

C. Sliding window technique to find maximum substring without repeating characters

D. Dynamic Programming with memoization to find all valid partitions

Solution

1. Step 1: Understand problem constraints

   The problem requires partitions where no character appears in more than one part, so we must know the last occurrence of each character.

2. Step 2: Identify approach that uses last occurrence

   The greedy approach that tracks last occurrence indices and extends partitions accordingly guarantees optimal partitions without overlap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy with last occurrence indices ensures minimal partitions covering all characters [OK]

Hint: Use last occurrence map to greedily partition [OK]

Common Mistakes:

• Assuming DP is needed for optimal partitions
• Using sliding window for unique substrings instead
• Trying backtracking which is inefficient here

2. Given the following Python code implementing the max heap approach to reorganize a string, what is the output when the input is "aab"?

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(max_heap)
    prev_count, prev_char = 0, ''
    result = []

    while max_heap:
        count, ch = heapq.heappop(max_heap)
        result.append(ch)
        if prev_count < 0:
            heapq.heappush(max_heap, (prev_count, prev_char))
        prev_count, prev_char = count + 1, ch

    res_str = ''.join(result)
    if len(res_str) != len(s):
        return ""
    return res_str

print(reorganizeString("aab"))

easy

A. "baa"

B. "aab"

C. "aba"

D. "" (empty string)

Solution

1. Step 1: Trace first iteration

   Heap contains [(' -2', 'a'), ('-1', 'b')]. Pop (-2, 'a'), append 'a', prev_count= -1, prev_char='a'.

2. Step 2: Trace second iteration

   Pop (-1, 'b'), append 'b', push back (-1, 'a') since prev_count < 0, update prev_count=0, prev_char='b'. Next pop (-1, 'a'), append 'a'. Result is "aba".

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output "aba" has no two adjacent same chars and uses all letters [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Returning input unchanged
• Appending characters without heap pushback
• Off-by-one in count update

3. You have a list of tasks represented by characters, each task takes 1 unit of time to execute. The CPU must wait for at least n units of time before executing the same task again. Which approach guarantees the minimum total time to finish all tasks?

easy

A. Dynamic Programming that tries all permutations of task orders to find the minimal schedule

B. Greedy algorithm using a max-heap to always schedule the most frequent available task next

C. Simple round-robin scheduling without considering cooldown intervals

D. Sorting tasks by frequency and inserting idle slots greedily without priority queue

Solution

1. Step 1: Understand the cooldown constraint

   The CPU must wait n units before repeating the same task, so scheduling must consider task frequencies and cooldowns.

2. Step 2: Why max-heap greedy works best

   Using a max-heap prioritizes tasks with the highest remaining frequency, ensuring minimal idle time by always picking the most urgent task available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max-heap approach matches known optimal solution [OK]

Hint: Max-heap greedily schedules highest frequency tasks first [OK]

Common Mistakes:

• Assuming DP or brute force is needed
• Ignoring cooldown leads to incorrect minimal time
• Greedy without priority queue misses optimal order

4. The following code attempts to find the largest monotone increasing digits number less than or equal to n. Identify the bug that causes incorrect results on some inputs.

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    return int(''.join(map(str, digits)))

medium

A. The code does not set digits after the marker to 9, missing the largest monotone number

B. The code decrements digits[i - 1] without checking if it causes new violations earlier

C. The code converts digits back to integer before fixing all digits, causing runtime errors

D. The code ignores the case when all digits are equal, returning incorrect output

Solution

1. Step 1: Analyze the loop effect

   The loop decrements digits[i - 1] when a violation is found and updates marker, but does not fix digits after marker.

2. Step 2: Identify missing step to set trailing digits to 9

   Without setting digits from marker to end to 9, the number may not be the largest monotone number ≤ n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing trailing digit fix leads to smaller-than-necessary result [OK]

Hint: Always set trailing digits to 9 after decrement to maximize number [OK]

Common Mistakes:

• Forgetting to set trailing digits to 9
• Assuming one decrement fixes all violations
• Ignoring edge cases with equal digits

5. What is the time complexity of the optimal greedy algorithm using a stack to remove k digits from a number string of length n to get the smallest number?

medium

A. O(n) because each digit is pushed and popped at most once

B. O(n^2) because nested loops are needed to find digits to remove

C. O(n log n) due to sorting digits internally

D. O(n * k) because each digit can cause up to k pops

Solution

1. Step 1: Identify operations per digit

   Each digit is pushed onto the stack once and can be popped at most once when a smaller digit arrives.

2. Step 2: Analyze total operations

   Since each push and pop happens at most once per digit, total operations are proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations are linear in n, no nested loops [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Confusing with sorting complexity
• Thinking nested loops are needed