Find All Duplicate Treasure Chests in an Array - 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 all integers in the array that appear exactly twice.
  • What input is provided?
    • An integer array chests where each integer is in the range [1, n] and appears either once or twice.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to count the occurrences of each integer in the array, then identify which integers appear exactly twice.

1) Initialize a dictionary `count` to keep track of the occurrence of each integer.
2) Iterate through the `chests` array:
   - If the integer is already in the dictionary, increment its count.
   - If it is not, add it to the dictionary with a count of 1.
3) After the loop, create a list of integers that have a count of 2.
4) Return this list of duplicates.

⚠️ Common Mistakes

• Forgetting to check if the integer is already in the dictionary before incrementing.
• Incorrectly identifying integers with counts other than 2.

I-mplement

def find_duplicate_chests(chests):
    # Step 1: Initialize a dictionary to count occurrences
    count = {}

    # Step 2: Count occurrences of each integer
    for chest in chests:
        if chest in count:
            count[chest] += 1
        else:
            count[chest] = 1

    # Step 3: Identify integers that have a count of 2
    duplicates = [chest for chest, cnt in count.items() if cnt == 2]

    return duplicates