Strongest Magical Artifacts - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

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

• Q: What is the input to the problem?
  • A: The input is an array of integers artifacts, representing the strengths of magical artifacts, and an integer k, representing the number of strongest artifacts to return.
• Q: What is the output?
  • A: The output is a list of the strongest k magical artifacts based on their strength relative to the median of the artifacts.
• Q: How is "strongest" defined?
  • A: A magical artifact is stronger if the absolute difference between its strength and the median is greater. If two artifacts have the same difference, the artifact with the greater strength is considered stronger.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: First, determine the median of the artifacts. Then, use a two-pointer approach to select the strongest k artifacts by comparing the absolute differences of the artifact strengths from the median.

1. Sort the `artifacts` array to determine the median.
2. Calculate the median as the middle element of the sorted array.
3. Initialize two pointers: `left` at the start of the array and `right` at the end of the array.
4. Initialize an empty list `strongest` to store the `k` strongest artifacts.
5. While the list `strongest` contains fewer than `k` artifacts:
   1. Compare the absolute difference between `artifacts[left]` and the median with the absolute difference between `artifacts[right]` and the median.
   2. If the difference for `artifacts[right]` is greater or equal, append `artifacts[right]` to the `strongest` list and move the `right` pointer left.
   3. Otherwise, append `artifacts[left]` to the `strongest` list and move the `left` pointer right.
6. Return the `strongest` list as the result.

⚠️ Common Mistakes

• Incorrectly calculating the median, especially when the number of elements is even.
• Failing to properly compare the artifacts based on both the absolute difference and the original values.

I-mplement

def get_strongest_artifacts(artifacts, k):
    # Step 1: Sort the artifacts to find the median
    artifacts.sort()
    n = len(artifacts)
    median = artifacts[(n - 1) // 2]

    # Step 2: Use two pointers to find the k strongest artifacts
    left, right = 0, n - 1
    strongest = []

    while len(strongest) < k:
        if abs(artifacts[right] - median) >= abs(artifacts[left] - median):
            strongest.append(artifacts[right])
            right -= 1
        else:
            strongest.append(artifacts[left])
            left += 1

    return strongest

# Example usage
print(get_strongest_artifacts([1, 2, 3, 4, 5], 2))  # Output: [5, 1]
print(get_strongest_artifacts([1, 1, 3, 5, 5], 2))  # Output: [5, 5]
print(get_strongest_artifacts([6, 7, 11, 7, 6, 8], 5))  # Output: [11, 8, 6, 6, 7]