Counting Pirates Action Minutes - 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 calculate a 1-indexed array answer of size k where each element represents the number of pirates whose Pirate Action Minutes (PAM) equals j.
    • What input is provided?
      • A 2D integer array logs where each element is [pirateID, time], and an integer k representing the maximum number of unique minutes to consider.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to track the unique minutes in which each pirate performed actions. Then, count how many pirates have each possible number of unique action minutes and store these counts in a result array.

1) Initialize a dictionary `pirate_minutes` where each key is a pirate's ID and the value is a set of unique minutes the pirate performed actions.
2) Iterate through the `logs` array:
   - For each log, add the time to the set corresponding to the pirate's ID.
3) Initialize a list `pam_count` of size `k` with all elements set to 0.
4) Iterate over the `pirate_minutes` dictionary:
   - For each pirate, determine the number of unique minutes they have.
   - Increment the corresponding index in the `pam_count` list.
5) Return the `pam_count` list as the result.

⚠️ Common Mistakes

  • Forgetting that a minute can only be counted once for each pirate, even if multiple actions occur during it.
  • Not correctly mapping the number of unique minutes to the indices in the pam_count list.

I-mplement

def counting_pirates_action_minutes(logs, k):
    # Dictionary to track unique minutes for each pirate
    pirate_minutes = {}

    for log in logs:
        pirate_id, time = log
        if pirate_id not in pirate_minutes:
            pirate_minutes[pirate_id] = set()
        pirate_minutes[pirate_id].add(time)

    # List to count the number of pirates with a given number of unique minutes
    pam_count = [0] * k
    for minutes in pirate_minutes.values():
        if len(minutes) <= k:
            pam_count[len(minutes) - 1] += 1

    return pam_count

# Example usage
logs1 = [0, 5], [1, 2], [0, 2], [0, 5], [1, 3](/codepath/compsci_guides/wiki/0,-5],-[1,-2],-[0,-2],-[0,-5],-[1,-3)
k1 = 5
logs2 = [1, 1], [2, 2], [2, 3](/codepath/compsci_guides/wiki/1,-1],-[2,-2],-[2,-3)
k2 = 4

print(counting_pirates_action_minutes(logs1, k1))  # Output: [0, 2, 0, 0, 0]
print(counting_pirates_action_minutes(logs2, k2))  # Output: [1, 1, 0, 0]