Next Contestant to Beat - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Stacks, Monotonic Stack

1: U-nderstand

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

  • Q: What does the problem ask for?
    • A: The problem asks to find the next node with a higher score for each node in a linked list.
  • Q: What should be returned?
    • A: An array of integers where each value corresponds to the next greater node for each node in the linked list. If no greater node exists, the value should be 0.
HAPPY CASE
Input: contestant_scores1 = Node(2, Node(1, Node(5)))
Output: [5, 5, 0]
Explanation: The next greater nodes are:
- 2 -> 5
- 1 -> 5
- 5 -> None (0)

HAPPY CASE
Input: contestant_scores2 = Node(2, Node(7, Node(4, Node(3, Node(5)))))
Output: [7, 0, 5, 5, 0]
Explanation: The next greater nodes are:
- 2 -> 7
- 7 -> None (0)
- 4 -> 5
- 3 -> 5
- 5 -> None (0)

EDGE CASE
Input: contestant_scores = Node(5)
Output: [0]
Explanation: A single-node list has no next greater node.

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 Linked List problems involving Finding Next Greater Element, we want to consider the following approaches:

  • Stack: Use a stack to keep track of the indices of nodes as we traverse the list, allowing us to efficiently find the next greater element for each node.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list, storing each node's value in an array. We'll then use a stack to track the indices of nodes for which we're still looking for the next greater element. As we continue traversing the array, we'll update the next greater element for nodes stored in the stack.

1) Initialize an empty list `scores` to store the values of the nodes in the linked list.
2) Traverse the linked list, appending each node's value to `scores`.
3) Initialize an array `next_greater` of the same length as `scores`, filled with `0`s.
4) Initialize an empty stack to store indices of nodes.
5) Traverse the `scores` array:
    a) For each element, check the stack. If the current element is greater than the element at the index stored at the top of the stack, update the corresponding value in `next_greater`.
    b) Push the current index onto the stack.
6) Return the `next_greater` array.

⚠️ Common Mistakes

  • Forgetting to handle edge cases, such as a single-node list.
  • Incorrectly managing the stack, leading to incorrect next greater element calculations.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def next_highest_scoring_contestant(contestant_scores):
    scores = []
    current = contestant_scores
    while current:
        scores.append(current.value)
        current = current.next
    
    # Array to store the result
    next_greater = [0] * len(scores)
    stack = []
    
    for i in range(len(scores)):
        # While stack is not empty and the current score is greater than the score at the index stored at the top of the stack
        while stack and scores[i] > scores[stack[-1]]:
            idx = stack.pop()
            next_greater[idx] = scores[i]
        # Push the current index to the stack
        stack.append(i)
    
    return next_greater

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Example: Use the provided contestant_scores1 and contestant_scores2 linked lists to verify that the function correctly identifies the next highest scoring contestant for each node.

6: E-valuate

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

Assume N represents the number of nodes in the linked list.

  • Time Complexity: O(N) because each node is visited exactly once.
  • Space Complexity: O(N) because we store the values in an array and use a stack to track indices.