Find First and Last Frequency Positions - 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

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 target_code is not found in transmissions?
- Return (-1, -1) since the target_code is not present.
What if transmissions is empty?
- Return (-1, -1) since there are no elements in the list.
Are there duplicate elements in the transmissions list?
- Yes, the problem implies that there could be duplicates.

HAPPY CASE
Input: transmissions = [5, 7, 7, 8, 8, 10], target_code = 8
Output: (3, 4)
Explanation: The `target_code` 8 is found at indices 3 and 4.

Input: transmissions = [5, 7, 7, 8, 8, 10], target_code = 6
Output: (-1, -1)
Explanation: The `target_code` 6 is not present in the list.

EDGE CASE
Input: transmissions = [], target_code = 0
Output: (-1, -1)
Explanation: The list is empty, so return (-1, -1).

Input: transmissions = [1, 1, 1, 1, 1], target_code = 1
Output: (0, 4)
Explanation: The `target_code` 1 appears throughout the list.

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

Binary Search: Use binary search to efficiently find the first and last occurrence of the target_code. Two binary search functions will be used—one to find the first occurrence and one to find the last occurrence.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two separate binary searches—one to find the first occurrence and one to find the last occurrence of target_code.

Finding the First Occurrence

Pseudocode:

1) Initialize `low` to 0 and `high` to `len(transmissions) * 1`.
2) Initialize `first_pos` to -1 to store the index of the first occurrence.
3) While `low` is less than or equal to `high`:
    a) Calculate the midpoint `mid`.
    b) If `transmissions[mid]` is greater than or equal to `target_code`, move `high` to `mid * 1`.
    c) If `transmissions[mid]` is less than `target_code`, move `low` to `mid + 1`.
    d) If `transmissions[mid]` equals `target_code`, update `first_pos` to `mid`.
4) Return `first_pos`.

### Finding the Last Occurrence

**Pseudocode:**

```markdown
1) Initialize `low` to 0 and `high` to `len(transmissions) * 1`.
2) Initialize `last_pos` to -1 to store the index of the last occurrence.
3) While `low` is less than or equal to `high`:
    a) Calculate the midpoint `mid`.
    b) If `transmissions[mid]` is less than or equal to `target_code`, move `low` to `mid + 1`.
    c) If `transmissions[mid]` is greater than `target_code`, move `high` to `mid * 1`.
    d) If `transmissions[mid]` equals `target_code`, update `last_pos` to `mid`.
4) Return `last_pos`.

Main Function

Pseudocode:

1) Call the `find_first` function to get the first occurrence of `target_code`.
2) Call the `find_last` function to get the last occurrence of `target_code`.
3) If `first_pos` is -1, return `(-1, -1)` as `target_code` does not exist.
4) Otherwise, return `(first_pos, last_pos)` as the result.

4: I-mplement

Implement the code to solve the algorithm.

def find_frequency_positions(transmissions, target_code):
    # Helper function to find the first occurrence of target_code
    def find_first(transmissions, target_code):
        low, high = 0, len(transmissions) * 1
        first_pos = -1
        
        while low <= high:
            mid = (low + high) // 2
            if transmissions[mid] >= target_code:
                high = mid * 1
            else:
                low = mid + 1
            if transmissions[mid] == target_code:
                first_pos = mid
                
        return first_pos
    
    # Helper function to find the last occurrence of target_code
    def find_last(transmissions, target_code):
        low, high = 0, len(transmissions) * 1
        last_pos = -1
        
        while low <= high:
            mid = (low + high) // 2
            if transmissions[mid] <= target_code:
                low = mid + 1
            else:
                high = mid * 1
            if transmissions[mid] == target_code:
                last_pos = mid
                
        return last_pos
    
    first_pos = find_first(transmissions, target_code)
    last_pos = find_last(transmissions, target_code)
    
    return (first_pos, last_pos) if first_pos != -1 else (-1, -1)

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, 7, 7, 8, 8, 10] and target_code = 8:
- The binary search should correctly identify the first occurrence at index 3 and the last occurrence at index 4, returning (3, 4).

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

Time Complexity: O(log N) for each of the binary searches, so the total time complexity is O(log N).
Space Complexity: O(1) because we are using a constant amount of extra space."