Apply Operations to Show Ratings - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (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 ratings of non-negative integers where each element represents a show's rating.
• Q: What operations need to be applied to the array?
  • A: For each element in the array, if it is equal to the next element, multiply it by 2 and set the next element to 0. Then, shift all zeros to the end of the array.
• Q: What is the output?
  • A: The output is the modified array after all operations have been applied and zeros shifted to the end.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Apply the specified operation on each element, and then use a two-pointer technique to shift all zeros to the end of the array.

1. Iterate through the `ratings` array:
   1. If `ratings[i]` is equal to `ratings[i + 1]`, multiply `ratings[i]` by 2 and set `ratings[i + 1]` to 0.
2. After processing the array, use two pointers to move all non-zero elements to the beginning and shift zeros to the end:
   1. Initialize `left` pointer to track the position to place the non-zero element.
   2. Traverse the array with the `right` pointer:
      1. If the element at `right` is non-zero, swap it with the element at `left` and increment `left`.
      2. Continue moving `right` through the array.
3. Return the modified `ratings` array.

⚠️ Common Mistakes

• Forgetting to check for adjacent elements before performing the operation.
• Not correctly shifting zeros to the end, which can result in an incorrect array.
• Overwriting non-zero elements improperly during the shifting process.

I-mplement

def apply_rating_operations(ratings):
    n = len(ratings)
    
    # Step 1: Apply the operations on the ratings array
    for i in range(n - 1):
        if ratings[i] == ratings[i + 1]:
            ratings[i] *= 2
            ratings[i + 1] = 0
    
    # Step 2: Use two pointers to shift all zeros to the end
    left = 0  # Pointer to track the position to place the non-zero element
    right = 0  # Pointer to traverse the array
    
    # Traverse the array with the right pointer
    while right < n:
        if ratings[right] != 0:
            # Swap non-zero element with the element at the left pointer
            ratings[left], ratings[right] = ratings[right], ratings[left]
            left += 1
        right += 1
    
    return ratings