Longest Harmonious Travel Sequence - codepath/compsci_guides GitHub Wiki

U-nderstand

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

• Q
  • What is the desired outcome?
    • To find the length of the longest harmonious sequence where the difference between the maximum and minimum ratings is exactly 1.
  • What input is provided?
    • An integer array ratings.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Count the frequency of each rating, then find the longest sequence where the difference between the maximum and minimum ratings is exactly 1.

1) Count the frequency of each rating using a dictionary.
2) Iterate through the dictionary:
   - For each rating, check if the next consecutive rating exists.
   - Calculate the length of the sequence formed by the current rating and the next one.
   - Update `max_length` if this sequence is longer than the current maximum.
3) Return `max_length`.

⚠️ Common Mistakes

• Not handling cases where the next consecutive rating does not exist.

I-mplement

def find_longest_harmonious_travel_sequence(durations):
    # Initialize a dictionary to store the frequency of each duration
    frequency = {}

    # Count the occurrences of each duration
    for duration in durations:
        if duration in frequency:
            frequency[duration] += 1
        else:
            frequency[duration] = 1

    max_length = 0

    # Find the longest harmonious sequence
    for duration in frequency:
        if duration + 1 in frequency:
            max_length = max(max_length, frequency[duration] + frequency[duration + 1])

    return max_length