Balanced Art Collection - 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 balanced subsequence where the difference between the maximum and minimum value is exactly 1.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Count the frequency of each number, then find the longest subsequence where the difference between the maximum and minimum value is exactly 1.

1) Count the frequency of each number in `art_pieces`.
2) Initialize `max_length` to 0.
3) Iterate through each unique number in the array:
   - If `num + 1` exists, calculate the length of the balanced subsequence involving `num` and `num + 1`.
   - Update `max_length` if the current balanced subsequence is longer.
4) Return `max_length`.

⚠️ Common Mistakes

• Not checking if num + 1 exists before calculating the balanced subsequence.

I-mplement

def find_balanced_subsequence(art_pieces):
    # Step 1: Create a frequency dictionary for the elements in art_pieces
    num_count = {}
    
    for piece in art_pieces:
        if piece in num_count:
            num_count[piece] += 1
        else:
            num_count[piece] = 1
    
    max_length = 0
    
    # Step 2: Iterate through each unique number in the frequency dictionary
    for num in num_count:
        # Check if the next consecutive number exists in the dictionary
        if num + 1 in num_count:
            # Calculate the length of the balanced subsequence involving 'num' and 'num + 1'
            current_length = num_count[num] + num_count[num + 1]
            # Update max_length if the current subsequence is longer
            max_length = max(max_length, current_length)
    
    return max_length