Counting Iron Man's Unique Suits - codepath/compsci_guides GitHub Wiki

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

Problem 3: Counting Iron Man's Unique Suits

Tony Stark, aka Iron Man, has designed many different suits over the years, but some of them are duplicates. Given a list of strings suits where each string is a suit in Stark's collection, count the total number of unique suits in the list.

  1. Implement the solution iteratively.
  2. Implement the solution recursively.
  3. Discuss: what are the similarities between the two solutions? What are the differences?
  4. Compare the time complexities of each solution. Are they the same? Different?

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Sets, Recursion, Iteration

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 count the number of unique suits in the list using both iterative and recursive approaches.
  • Q: Can we use sets or other data structures?
    • A: Yes, for the iterative approach, you can use a set to track unique suits.
HAPPY CASE
Input: ["Mark I", "Mark II", "Mark III"]
Output: 3
Explanation: All suits are unique, so the count is 3.

Input: ["Mark I", "Mark I", "Mark III"]
Output: 2
Explanation: "Mark I" is duplicated, so the count of unique suits is 2.

EDGE CASE
Input: []
Output: 0
Explanation: The list is empty, so the count should be 0.

Input: ["Mark I", "Mark I", "Mark I"]
Output: 1
Explanation: All suits are the same, so the count of unique suits is 1.

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

  • Set for Iteration: Use a set to keep track of unique items and count them.
  • Recursion with Sublist: Use recursion to compare each element with the rest of the list and count only the first occurrence.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • For the iterative solution, use a set to collect unique suits and return its length.
  • For the recursive solution, compare each suit with the rest of the list and count only those that are unique.

Iterative Approach:

1) Initialize an empty set `unique_suits`.
2) Loop through each item in the list `suits`.
3) Add each item to the set `unique_suits` (sets automatically handle duplicates).
4) Return the size of the set `unique_suits`.

Recursive Approach:

1) Base case: If the list `suits` is empty, return 0.
2) Recursive case: 
   a) Extract the first element `first` from `suits`.
   b) Call the recursive function on the rest of the list `suits[1:]`.
   c) If `first` is in the rest of the list, return the result of the recursive call.
   d) If `first` is not in the rest of the list, return 1 plus the result of the recursive call.

⚠️ Common Mistakes

  • Forgetting that sets automatically handle duplicates in the iterative approach.
  • Failing to correctly manage the sublist in the recursive approach, leading to incorrect counting.

4: I-mplement

Implement the code to solve the algorithm.

# Iterative Solution:

def count_suits_iterative(suits):
    unique_suits = set()
    for suit in suits:
        unique_suits.add(suit)
    return len(unique_suits)

# Recursive Solution:

def count_suits_recursive(suits):
    if not suits:
        return 0
    first = suits[0]
    rest_unique_count = count_suits_recursive(suits[1:])
    if first in suits[1:]:
        return rest_unique_count
    else:
        return 1 + rest_unique_count

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 count_suits_iterative function with the input ["Mark I", "Mark II", "Mark III"]. The set should contain three items, and the final count should be 3.
  • Trace through the count_suits_recursive function with the input ["Mark I", "Mark I", "Mark III"]. The function should return 2 after filtering out duplicates.

6: E-valuate

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

  • Time Complexity:
    • Iterative Solution: O(N) where N is the number of suits in the list. Adding elements to a set and checking membership are average O(1) operations.
    • Recursive Solution: O(N^2) where N is the number of suits in the list. Each recursive call may involve scanning a portion of the list to check for duplicates, leading to quadratic time complexity.
  • Space Complexity:
    • Iterative Solution: O(N) due to the space needed for the set storing unique suits.
    • Recursive Solution: O(N) due to the recursion stack and the list slicing in each recursive call.