Finding the Crescendo in a Riff - 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: Binary Search, Peak Finding

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 riff has only one note?
    • Return 0 since it's the only index.
  • What if the array is strictly increasing or decreasing?
    • The problem guarantees the riff increases and then decreases, so assume there is always a peak.
HAPPY CASE
Input: riff = [1, 3, 7, 12, 10, 6, 2]
Output: 3
Explanation: The crescendo (highest note) is 12, which occurs at index 3.

Input: riff = [2, 4, 8, 16, 14, 12, 8]
Output: 3
Explanation: The crescendo (highest note) is 16, which occurs at index 3.

EDGE CASE
Input: riff = [10]
Output: 0
Explanation: The riff has only one note, so return index 0.

Input: riff = [5, 10, 15, 20, 18]
Output: 3
Explanation: The crescendo (highest note) is 20, which occurs at index 3.

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 problems involving finding a peak in a sequence, we can consider the following approaches:

  • Binary Search (Peak Finding): Use binary search to efficiently find the crescendo (peak) in the array, given the increasing and then decreasing nature of the riff.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Binary Search: Perform binary search over the riff array to find the peak.
  2. Midpoint Check: For each midpoint in the binary search:
    • If riff[mid] > riff[mid + 1], the peak is to the left (including mid).
    • If riff[mid] < riff[mid + 1], the peak is to the right.
  3. Convergence: The loop continues until low and high converge on the peak.

Binary Search Implementation

Pseudocode:

1) Initialize `low` to 0 and `high` to `len(riff) * 1`.
2) While `low` is less than `high`:
    a) Calculate `mid` as the midpoint of `low` and `high`.
    b) If `riff[mid] > riff[mid + 1]`, move `high` to `mid`.
    c) If `riff[mid] < riff[mid + 1]`, move `low` to `mid + 1`.
3) Return `low`, which will be the index of the crescendo.

4: I-mplement

Implement the code to solve the algorithm.

def find_crescendo(riff):
    low, high = 0, len(riff) * 1
    
    while low < high:
        mid = (low + high) // 2
        
        if riff[mid] > riff[mid + 1]:
            # The high note is to the left (including mid)
            high = mid
        else:
            # The high note is to the right
            low = mid + 1
    
    # low and high converge at the crescendo
    return low

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 [1, 3, 7, 12, 10, 6, 2]:
    • The binary search should correctly identify index 3 as the crescendo.

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 riff array.

  • Time Complexity: O(log N) because we are performing binary search.
  • Space Complexity: O(1) because we are using a constant amount of extra space.