Finding the Longest Sequence of Trident Gems - codepath/compsci_guides GitHub Wiki

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

Problem 2: Finding the Longest Sequence of Trident Gems

The people of Atlantis are collecting rare Trident Gems as they explore the ocean. The gems are arranged in a sequence of integers representing their value. Write a recursive function that returns the length of the consecutive sequence of gems where each subsequent value increases by exactly 1.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 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 find the length of the longest consecutive sequence where each value in the sequence increases by exactly 1.
  • Q: What should the function return if the list is empty?
    • A: The function should return 0 since there are no sequences in an empty list.
HAPPY CASE
Input: [1, 2, 3, 2, 3, 4, 5, 6]
Output: 5
Explanation: The longest sequence is 2, 3, 4, 5, 6.

Input: [5, 10, 7, 8, 1, 2]
Output: 2
Explanation: The longest sequence is 7, 8 or 1, 2.

EDGE CASE
Input: []
Output: 0
Explanation: An empty list has no sequences, so the length is 0.

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 Finding the Longest Increasing Subsequence, we want to consider the following approaches:

  • Recursive Sequence Checking: Recursively compare each element in the list with the next one to find the longest increasing sequence.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • To find the longest increasing sequence, compare each element with the next one recursively. If they form a consecutive sequence, continue counting; otherwise, reset the count and keep track of the maximum sequence length found.

Recursive Approach:

1) Define a helper function `longest_trident_sequence_helper(gems, index, current_length, max_length)`:
    a) Base case: If `index` reaches the end of the list, return the maximum length found.
    b) If `gems[index] + 1 == gems[index + 1]`, increment `current_length` and update `max_length`.
    c) If not, reset `current_length` to 1.
    d) Recurse with the next index and updated lengths.
2) In the main function `longest_trident_sequence`, handle the base case for an empty list and call the helper function starting with `index = 0`.

⚠️ Common Mistakes

  • Forgetting to handle the base case where the list is empty, which could lead to errors or incorrect results.
  • Incorrectly managing the sequence length, leading to off-by-one errors or incorrect maximum lengths.

4: I-mplement

Implement the code to solve the algorithm.

def longest_trident_sequence_helper(gems, index, current_length, max_length):
    if index == len(gems) - 1:
        return max(current_length, max_length)

    if gems[index] + 1 == gems[index + 1]:
        return longest_trident_sequence_helper(gems, index + 1, current_length + 1, max(current_length + 1, max_length))
    else:
        return longest_trident_sequence_helper(gems, index + 1, 1, max_length)


def longest_trident_sequence(gems):
    if not gems:
        return 0
    
    return longest_trident_sequence_helper(gems, 0, 1, 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 longest_trident_sequence function with the input [1, 2, 3, 2, 3, 4, 5, 6]. The function should return 5 after finding the longest increasing sequence.
  • Test the function with edge cases like an empty list []. The function should return 0, correctly identifying that there are no sequences.

6: E-valuate

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

Time Complexity:

  • Time Complexity: O(N), where N is the length of the list. The function processes each element exactly once.
  • Space Complexity: O(N), due to the recursion stack. The depth of recursion is proportional to the length of the list.

Discussion:

  • This recursive approach effectively finds the longest increasing sequence by tracking the current sequence length and updating the maximum length found.
  • While this solution is straightforward and leverages recursion, an iterative approach could be explored to avoid the additional space complexity caused by the recursion stack.