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. You are given arrival and departure times of trains at a station. You need to find the minimum number of platforms required so that no train waits. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sort trains by arrival time and use a min-heap to track earliest departure times

B. Dynamic Programming to find the maximum number of overlapping intervals

C. Greedy approach by always assigning the next available platform without sorting

D. Brute force nested loops checking all pairs of trains for overlaps

Solution

1. Step 1: Understand the problem requires tracking overlapping intervals

   We need to find the maximum number of trains simultaneously at the station, which corresponds to the maximum overlap of intervals.

2. Step 2: Identify the optimal approach

   Sorting trains by arrival time and using a min-heap to track the earliest departure allows efficient detection of overlaps and platform reuse, guaranteeing an optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks platform usage [OK]

Hint: Min-heap tracks earliest departure for platform reuse [OK]

Common Mistakes:

• Assuming greedy without sorting works optimally
• Thinking DP is needed for interval overlaps
• Using brute force for large inputs

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. Examine the following BFS-based code for Jump Game II. Which line contains a subtle bug that can cause incorrect jump counts or infinite loops?

medium

A. Line checking if next_pos == n - 1 to return jumps

B. Line incrementing jumps before processing current level

C. Line calculating furthest_jump without bounding by n-1

D. Line adding next_pos to visited set

Solution

1. Step 1: Identify furthest_jump calculation

   furthest_jump = pos + nums[pos] can exceed array bounds, causing range() to go out of range or runtime error.

2. Step 2: Check impact

   Without min(pos + nums[pos], n - 1), code may attempt invalid indices, causing incorrect behavior or crashes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bounding furthest_jump by n-1 prevents out-of-range errors [OK]

Hint: Always bound jump indices within array length [OK]

Common Mistakes:

• Forgetting to limit furthest_jump to n-1
• Incrementing jumps incorrectly
• Missing visited set usage

4. What is the time complexity of the optimal min-heap based algorithm for finding the minimum number of platforms required for n trains?

medium

A. O(n²) due to nested loops checking all train pairs

B. O(n) because each train is processed once

C. O(n log n) due to sorting and heap operations for each train

D. O(n log k) where k is the maximum number of platforms needed

Solution

1. Step 1: Identify sorting cost

   Sorting n trains by arrival time costs O(n log n).

2. Step 2: Analyze heap operations

   Each train causes at most one push and one pop on the heap, each O(log n), so total O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + heap operations dominate complexity [OK]

Hint: Sorting + heap push/pop per train -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n) ignoring sorting and heap costs
• Confusing heap size k with n for complexity
• Mistaking nested loops for optimal approach complexity

5. What is the time complexity of the optimal greedy algorithm for partitioning labels using a fixed-size array for last occurrences, given a string of length n?

medium

A. O(n) because each character is processed a constant number of times

B. O(n log n) due to sorting characters by last occurrence

C. O(n^2) due to nested scanning for last occurrences

D. O(n * 26) because of fixed alphabet size iteration

Solution

1. Step 1: Analyze last occurrence computation

   We scan the string once to record last occurrence of each character in O(n).

2. Step 2: Analyze partitioning loop

   We iterate over the string once more, updating partition end in O(1) per character.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans over string length n -> O(n) time [OK]

Hint: Two passes over string -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing fixed alphabet size iteration as O(n*26)
• Thinking sorting is needed