Wiggle Subsequence

▶

Steps

setup

Initialize count and last_diff

Start by setting count to 1 because the first element alone forms a wiggle subsequence. Initialize last_diff to 0 since no differences have been computed yet.

💡 This initialization sets the baseline for counting wiggles and prepares to track the direction of differences.

Line:

count = 1
last_diff = 0

💡 The algorithm always counts at least one element as a wiggle subsequence.

setup

Set pointer i to 1 and calculate first difference

Begin iterating from the second element (index 1) to compare differences with previous elements. Compute diff = nums[1] - nums[0] = 7 - 1 = 6, a positive difference indicating an upward wiggle.

💡 Starting from the second element allows us to compute the first difference and detect the initial wiggle direction.

Line:

for i in range(1, len(nums)):
diff = nums[i] - nums[i - 1]

💡 The first difference sets the initial direction for wiggle detection.

compare

Check if diff and last_diff have opposite signs and update count

Since last_diff is 0 and diff is 6 (positive), the condition (diff > 0 and last_diff <= 0) is true. This means we found a wiggle. Increment count from 1 to 2 and update last_diff to 6.

💡 Detecting a change in direction or the first positive difference triggers an increment in count and updates the wiggle direction.

Line:

if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
    count += 1
    last_diff = diff

💡 The algorithm counts the first positive difference as a valid wiggle and builds the wiggle subsequence length incrementally.

traverse

Move pointer i to 2 and calculate difference

Advance pointer i to index 2 to compare nums[2] and nums[1]. Compute diff = 4 - 7 = -3, a negative difference indicating a downward wiggle.

💡 Each step moves forward to check the next pair for wiggle changes and calculates the difference.

Line:

for i in range(1, len(nums)):
diff = nums[i] - nums[i - 1]

💡 The difference changes sign from positive to negative, a key wiggle pattern.

compare

Check wiggle condition and update count

last_diff is 6 (positive), diff is -3 (negative). Condition (diff < 0 and last_diff >= 0) is true, so this is a valid wiggle. Increase count from 2 to 3 and update last_diff to -3.

💡 Opposite signs between last_diff and diff indicate a wiggle direction change, triggering count increment.

Line:

if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
    count += 1
    last_diff = diff

💡 The algorithm detects a downward wiggle after an upward one and extends the wiggle subsequence.

traverse

Move pointer i to 3 and calculate difference

Advance pointer i to index 3 to compare nums[3] and nums[2]. Compute diff = 9 - 4 = 5, a positive difference indicating an upward wiggle.

💡 The iteration continues to check all pairs for wiggle changes and calculates the difference.

Line:

for i in range(1, len(nums)):
diff = nums[i] - nums[i - 1]

💡 The difference changes sign from negative to positive, indicating a wiggle.

compare

Check wiggle condition and update count

last_diff is -3 (negative), diff is 5 (positive). Condition (diff > 0 and last_diff <= 0) is true, so this is a valid wiggle. Increase count from 3 to 4 and update last_diff to 5.

💡 Opposite signs between last_diff and diff indicate a wiggle direction change, triggering count increment.

Line:

if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
    count += 1
    last_diff = diff

💡 The algorithm detects an upward wiggle after a downward one and extends the wiggle subsequence.

traverse

Move pointer i to 4 and calculate difference

Advance pointer i to index 4 to compare nums[4] and nums[3]. Compute diff = 2 - 9 = -7, a negative difference indicating a downward wiggle.

💡 The iteration continues to check all pairs for wiggle changes and calculates the difference.

Line:

for i in range(1, len(nums)):
diff = nums[i] - nums[i - 1]

💡 The difference changes sign from positive to negative, indicating a wiggle.

compare

Check wiggle condition and update count

last_diff is 5 (positive), diff is -7 (negative). Condition (diff < 0 and last_diff >= 0) is true, so this is a valid wiggle. Increase count from 4 to 5 and update last_diff to -7.

💡 Opposite signs between last_diff and diff indicate a wiggle direction change, triggering count increment.

Line:

if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
    count += 1
    last_diff = diff

💡 The algorithm detects a downward wiggle after an upward one and extends the wiggle subsequence.

traverse

Move pointer i to 5 and calculate difference

Advance pointer i to index 5 to compare nums[5] and nums[4]. Compute diff = 5 - 2 = 3, a positive difference indicating an upward wiggle.

💡 The iteration continues to check all pairs for wiggle changes and calculates the difference.

Line:

for i in range(1, len(nums)):
diff = nums[i] - nums[i - 1]

💡 The difference changes sign from negative to positive, indicating a wiggle.

compare

Check wiggle condition and update count

last_diff is -7 (negative), diff is 3 (positive). Condition (diff > 0 and last_diff <= 0) is true, so this is a valid wiggle. Increase count from 5 to 6 and update last_diff to 3.

💡 Opposite signs between last_diff and diff indicate a wiggle direction change, triggering count increment.

💡 The algorithm detects an upward wiggle after a downward one and extends the wiggle subsequence to include the last element.

reconstruct

End of iteration, return count

All elements have been processed. The final count is 6, representing the length of the longest wiggle subsequence.

💡 Returning the count gives the final answer to the problem.

Line:

return count

💡 The algorithm completes with the correct wiggle subsequence length.

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1  # STEP 1: Initialize count
    last_diff = 0  # STEP 1: Initialize last_diff
    for i in range(1, len(nums)):  # STEP 2,4,6,8,10: Iterate and calculate difference
        diff = nums[i] - nums[i - 1]  # STEP 2,4,6,8,10: Calculate difference
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):  # STEP 3,5,7,9,11: Check wiggle condition
            count += 1  # STEP 3,5,7,9,11: Increment count
            last_diff = diff  # STEP 3,5,7,9,11: Update last_diff
    return count  # STEP 12: Return final count

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

📊

Wiggle Subsequence - Watch the Algorithm Execute, Step by Step

Watching each comparison and decision helps you understand how the greedy approach efficiently detects wiggle patterns without checking all subsequences.

setup

1

0

7

1

4

2

9

3

2

4

5

5

Result: 1

compare

1

0

i

7

1

4

2

9

3

2

4

5

5

Result: 1

insert

1

0

i

7

1

4

2

9

3

2

4

5

5

Result: 2

compare

1

0

7

1

i

4

2

9

3

2

4

5

5

Result: 2

insert

1

0

7

1

i

4

2

9

3

2

4

5

5

Result: 3

compare

1

0

7

1

4

2

i

9

3

2

4

5

5

Result: 3

insert

1

0

7

1

4

2

i

9

3

2

4

5

5

Result: 4

compare

1

0

7

1

4

2

9

3

i

2

4

5

5

Result: 4

insert

1

0

7

1

4

2

9

3

i

2

4

5

5

Result: 5

compare

1

0

7

1

4

2

9

3

2

4

i

5

5

Result: 5

insert

1

0

7

1

4

2

9

3

2

4

i

5

5

Result: 6

record

1

0

7

1

4

2

9

3

2

4

5

5

Result: 6

Key Takeaways

✓ The algorithm counts a wiggle subsequence by tracking the sign changes of consecutive differences.

This insight is hard to see from code alone because it requires understanding how sign changes relate to wiggle patterns.

✓ Only differences that change direction relative to the last difference increment the count.

Visualizing each difference and decision clarifies why some differences are ignored.

✓ The initial difference sets the direction and starts the count beyond the first element.

Seeing the first positive difference trigger a count increment helps understand the algorithm's base case.

Practice

1. 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

2. What is the time complexity of the peak-valley approach for the Best Time to Buy and Sell Stock II problem, and why might some candidates incorrectly think it is higher?

medium

A. O(1) since only constant extra space is used

B. O(n^2) because of nested while loops

C. O(n log n) due to sorting or searching steps

D. O(n) because each element is visited at most twice in the loops

Solution

1. Step 1: Identify loop behavior

   Though there are nested while loops, the index i only moves forward and never revisits elements.

2. Step 2: Conclude time complexity

   Each element is processed at most twice, so total time is linear O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Index i increments monotonically through array [OK]

Hint: Index i only moves forward, no repeated visits [OK]

Common Mistakes:

• Assuming nested loops multiply to O(n^2)
• Confusing space complexity with time complexity
• Thinking sorting is involved

3. What is the time complexity of the optimal min-heap based algorithm to find the minimum cost to connect n sticks, and why?

medium

A. O(n log n) because each of the n-1 merges involves two heap pops and one push, each O(log n)

B. O(n log k) where k is the maximum stick length, due to heapifying by stick size

C. O(n) because heap operations are constant time on average

D. O(n^2) because each merge requires scanning all sticks

Solution

1. Step 1: Identify number of operations

   There are n sticks, so n-1 merges are needed.

2. Step 2: Analyze heap operations per merge

   Each merge requires two pops and one push on a min-heap, each operation O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   (n-1) merges x 3 heap ops x O(log n) -> O(n log n) [OK]

Hint: Heap operations cost O(log n) each, repeated n times [OK]

Common Mistakes:

• Assuming heap operations are O(1) average
• Confusing n with maximum stick length k
• Thinking merges scan all sticks leading to O(n^2)

4. Suppose the problem is modified so that digits can be removed multiple times (i.e., digits can be reused after removal) to form the smallest number after k removals. Which of the following algorithmic changes correctly adapts the solution?

hard

A. Use dynamic programming to consider all sequences with repeated digits allowed

B. Sort digits and pick the smallest k digits to remove, ignoring order

C. Use the same greedy stack approach but allow re-inserting popped digits later

D. Use a priority queue to always remove the largest digit available at each step

Solution

1. Step 1: Understand reuse of digits breaks greedy assumptions

   Allowing reuse means the problem is no longer about removing fixed digits but about sequences with repetition, invalidating the greedy stack approach.

2. Step 2: Why dynamic programming is needed

   DP can explore all subsequences with repeated digits and track minimal results, handling reuse correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails with reuse; DP handles repeated digit choices [OK]

Hint: Reuse breaks greedy; DP needed for repeated choices [OK]

Common Mistakes:

• Trying to reuse greedy stack with re-insertion
• Sorting digits ignores order and reuse constraints
• Using priority queue removes largest digit but ignores reuse

5. Suppose the problem is changed so that some people can be assigned to either city multiple times (reusable assignments), or the number of people sent to each city is not fixed. Which approach correctly adapts the solution?

hard

A. Use a dynamic programming approach to handle variable counts and reuse assignments

B. Use the same greedy sorting by cost difference and assign exactly n people to each city

C. Sort by absolute cost to city A and assign all to city A to minimize cost

D. Assign people greedily without sorting, picking the cheaper city for each person

Solution

1. Step 1: Understand problem change

   Allowing reuse or variable counts breaks the fixed half assignment constraint, invalidating the greedy approach.

2. Step 2: Why DP is needed

   Dynamic programming can explore all valid assignments with reuse or variable counts, ensuring minimal total cost under new constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails when constraints are relaxed; DP handles complex state space [OK]

Hint: Relaxed constraints require DP, not greedy [OK]

Common Mistakes:

• Applying greedy unchanged despite constraint changes
• Ignoring reuse possibility in assignment
• Assuming sorting by absolute cost suffices