Reverse Pairs

**[[JCSU Unit 1 Problem Set 2]] (Click for link to problem statements)**

## Problem Highlights

* 💡 **Difficulty:** Easy
* ⏰ **Time to complete**: 15 mins
* 🛠️ **Topics**: Array Manipulation, Reordering

## 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 is the goal of the problem?
    - The goal is to reorder a list of `2n` elements where the first half contains `xi` elements and the second half contains `yi` elements, such that the result alternates as `[y1, x1, y2, x2, ..., yn, xn]`.
- What are the constraints on input?
    - The input will always contain an even number of elements.

HAPPY CASE
Input: 
    pairs = [1, 2, 3, 4, 5, 6]
Output: 
    [2, 1, 4, 3, 6, 5]
Explanation:
    The pairs are reversed as `[2, 1], [4, 3], [6, 5]`.

EDGE CASE
Input: 
    pairs = []
Output: 
    []
Explanation:
    An empty list results in an empty output.

## 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 **array reordering problems**, we want to consider the following approaches:

- **Iterative Traversal:** Use two pointers or indices to traverse both halves of the array and construct the result by appending elements alternately.

## 3: P-lan

> **Plan** the solution with appropriate visualizations and pseudocode.

**General Idea:**  
Split the array into two halves. Iterate through both halves simultaneously, appending elements from the second half followed by the first half into a new list.

### Steps:

1. Determine the midpoint `n` of the list, which is `len(pairs) // 2`.
2. Initialize an empty list `result`.
3. Iterate through indices `i` from 0 to `n - 1`:
    - Append the `i-th` element from the second half of `pairs` to `result`.
    - Append the `i-th` element from the first half of `pairs` to `result`.
4. Return the `result`.

## 4: I-mplement

> **Implement** the code to solve the algorithm.

```python
def reverse_pairs(pairs):
    n = len(pairs) // 2  # Determine the number of pairs (half the list length)
    result = []
    for i in range(n):
        result.append(pairs[n + i])  # Add the 'yi' element from the second half
        result.append(pairs[i])     # Add the corresponding 'xi' element from the first half
    return result  # Return the reordered list with reversed pairs

5: R-eview

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

Example 1:

• Input: pairs = [1, 2, 3, 4, 5, 6]
• Expected Output: [2, 1, 4, 3, 6, 5]
• Observed Output: [2, 1, 4, 3, 6, 5]

Example 2:

• Input: pairs = ['Batman', 'Robin', 'The Joker', 'Harley Quinn']
• Expected Output: ['Robin', 'Batman', 'Harley Quinn', 'The Joker']
• Observed Output: ['Robin', 'Batman', 'Harley Quinn', 'The Joker']

6: E-valuate

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

Assume n is half the size of the input list.

• Time Complexity: O(n) because we traverse half the elements of the list.
• Space Complexity: O(n) because we construct a new result list.