Sorting Crystals - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20 mins
  • 🛠️ Topics: Divide and Conquer, Sorting

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?
  • What should be returned if the crystals list is empty?
    • Return an empty list since there are no crystals to sort.
  • Are all crystal power levels unique?
    • The problem does not specify, so assume there could be duplicates.
  • How large can the crystals list be?
    • The problem does not specify, but assume it could be large, making O(n log n) time complexity necessary.
HAPPY CASE
Input: crystals = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: The crystals are sorted in ascending order based on their power levels.

Input: crystals = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: The crystals are sorted in ascending order with duplicates properly handled.

EDGE CASE
Input: crystals = []
Output: []
Explanation: The list is empty, so return an empty list.

Input: crystals = [10]
Output: [10]
Explanation: The list contains only one crystal, so it is already sorted.

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

  • Merge Sort: The problem can be solved using merge sort, which guarantees O(n log n) time complexity and is a stable sorting algorithm.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Implement merge sort to recursively divide the list of crystals into smaller sublists, sort them, and then merge them back together in sorted order.

Merge Sort Implementation

Pseudocode:

1) Define a helper function `merge` that merges two sorted sublists into a single sorted list.
2) Base Case: If the `crystals` list has 1 or 0 elements, return it as it is already sorted.
3) Recursive Case:
    a) Split the list into two halves.
    b) Recursively sort the left and right halves.
    c) Merge the sorted halves using the `merge` function.
4) Return the sorted list.

Merge Function

Pseudocode:

1) Initialize an empty list `sorted_list` to store the merged result.
2) Use two pointers `i` and `j` to iterate through the `left` and `right` sublists, respectively.
3) While both pointers are within the bounds of their respective lists:
    a) Compare the elements at `left[i]` and `right[j]`.
    b) Append the smaller element to `sorted_list` and increment the corresponding pointer.
4) Append any remaining elements from `left` or `right` to `sorted_list`.
5) Return the `sorted_list`.

4: I-mplement

Implement the code to solve the algorithm.

def sort_crystals(crystals):
    # Helper function to merge two sorted halves
    def merge(left, right):
        sorted_list = []
        i = j = 0
        
        # Merge the two halves while maintaining order
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted_list.append(left[i])
                i += 1
            else:
                sorted_list.append(right[j])
                j += 1
        
        # Collect any remaining elements
        sorted_list.extend(left[i:])
        sorted_list.extend(right[j:])
        
        return sorted_list
    
    # Base case: A list of one crystal is already sorted
    if len(crystals) <= 1:
        return crystals
    
    # Split the list into two halves
    mid = len(crystals) // 2
    left_half = sort_crystals(crystals[:mid])
    right_half = sort_crystals(crystals[mid:])
    
    # Merge the sorted halves
    return merge(left_half, right_half)

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 your code with the input [5, 2, 3, 1]:
    • The merge sort should correctly sort the list as [1, 2, 3, 5].

6: E-valuate

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

Assume N represents the length of the crystals array.

  • Time Complexity: O(N log N) because merge sort divides the list into halves recursively (log N) and then merges them (O(N)).
  • Space Complexity: O(N) due to the additional space needed to store the sorted list during the merge process.