Checking the Knight's Path - codepath/compsci_guides GitHub Wiki

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

Problem 6: Checking the Knight's Path

A knight is traveling along a path marked by stones, and each stone has a number on it. The knight must check if the numbers on the stones form a strictly increasing sequence. Write a recursive function to determine if the sequence is strictly increasing.

Problem Highlights

💡 Difficulty: Easy
⏰ Time to complete: 10-15 mins
🛠️ Topics: Recursion, Sequence Checking

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?

Q: What is the main task in this problem?
- A: The task is to determine if the sequence of numbers in the path list is strictly increasing using recursion.
Q: What should the function return if the list is empty or has only one element?
- A: The function should return True, as an empty list or a list with one element is trivially strictly increasing.

HAPPY CASE
Input: [1, 2, 3, 4, 5]
Output: True
Explanation: The sequence 1 -> 2 -> 3 -> 4 -> 5 is strictly increasing.

Input: [3, 5, 2, 8]
Output: False
Explanation: The sequence is not strictly increasing because 5 -> 2 decreases.

EDGE CASE
Input: []
Output: True
Explanation: An empty list is considered strictly increasing.

Input: [7]
Output: True
Explanation: A single-element list is strictly increasing.

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 Sequence Checking, we want to consider the following approaches:

Recursive Sequence Checking: Recursively compare each element in the list with the next one to ensure the sequence is strictly increasing.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

To check if the sequence is strictly increasing, compare each element with the next one recursively. If any element is greater than or equal to the next, return False.

Recursive Approach:

1) Base case: If the list `path` is empty or has one element, return `True`.
2) If the current element `path[0]` is greater than or equal to the next element `path[1]`, return `False`.
3) Recursive case: Call the function on the rest of the list `path[1:]` and return the result.

⚠️ Common Mistakes

Not correctly handling the base cases, leading to incorrect results.
Incorrectly managing list slicing, which could lead to errors or off-by-one mistakes.

4: I-mplement

Implement the code to solve the algorithm.

def is_increasing_path(path):
    # Base case: if the path is empty or has one stone, it's strictly increasing
    if len(path) <= 1:
        return True
    
    # If the current element is greater than or equal to the next, return False
    if path[0] >= path[1]:
        return False
    
    # Recursive case: check the rest of the path
    return is_increasing_path(path[1:])

5: R-eview

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

Trace through the is_increasing_path function with the input [1, 2, 3, 4, 5]. The function should return True after confirming each element is less than the next.
Test the function with edge cases like an empty list [] or a single-element list [7]. The function should return True for both cases.

6: E-valuate

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

Time Complexity: O(N) where N is the number of elements in the list. The function processes each element at most once.
Space Complexity: O(N) due to the recursion stack. The depth of recursion is proportional to the length of the list.