Caterpie’s Evolution Sequence - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 20 mins
  • 🛠️ Topics: Dynamic Programming

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the goal of the problem?
    • The goal is to count how many strictly increasing subarrays (sequences) exist in the array.
  • What is considered a strictly increasing sequence?
    • A subarray is considered strictly increasing if each element in the subarray is greater than the previous one.
  • Can single-element subarrays be counted?
    • Yes, single-element subarrays are strictly increasing by default.
HAPPY CASE
Input: 
    steps = [1, 3, 5, 4, 4, 6]
Output: 
    10
Explanation:
    The strictly increasing subarrays are: 
    [1], [3], [5], [4], [4], [6], [1, 3], [3, 5], [4, 6], [1, 3, 5].

EDGE CASE
Input: 
    steps = [1, 2, 3, 4, 5]
Output: 
    15
Explanation:
    Every subarray is strictly increasing. There are 15 possible subarrays in total.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For counting increasing sequences, we want to consider the following approaches:

  • Dynamic Programming (DP): We can use a DP array to keep track of the number of strictly increasing subarrays that end at each index.
  • Sliding Window: This might help to identify sequences efficiently, but DP is more straightforward for this problem.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to track the number of strictly increasing subarrays ending at each index. Each element starts as a sequence of length 1, and for each subsequent element, if it's larger than the previous one, extend the previous subarray.

Steps:

  1. Initialization:

    • Create a dp array where dp[i] represents the number of strictly increasing subarrays ending at index i. Initialize each element of dp as 1 because each element is an increasing subarray of length 1 by itself.
    • Initialize total to n (the length of the array) to count the single-element subarrays.

  2. Update DP Array:

    • Loop through the array starting from the second element.
    • If the current element is greater than the previous one, set dp[i] = dp[i - 1] + 1 to extend the previous subarray.
    • Add dp[i] - 1 to total to count all the strictly increasing subarrays ending at i.

  3. Return the Result:

    • The total will store the number of strictly increasing subarrays.

4: I-mplement

Implement the code to solve the algorithm.

def count_increasing_sequences(steps):
    n = len(steps)
    dp = [1] * n  # Every element is an increasing sequence of length 1
    total = n  # Start with each element as its own subarray
    
    for i in range(1, n):
        if steps[i] > steps[i - 1]:
            dp[i] = dp[i - 1] + 1  # Extend previous increasing sequence
        total += dp[i] - 1  # Add all subarrays ending at i
    return total

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: steps = [1, 3, 5, 4, 4, 6]
  • Expected Output: 10

Example 2:

  • Input: steps = [1, 2, 3, 4, 5]
  • Expected Output: 15

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the length of the input array.

  • Time Complexity: O(n) because we iterate through the array once.
  • Space Complexity: O(n) to store the DP array.