# Longest Repeating Character Replacement

**Problem Statement:**

In this problem, you are given a string `s` and an integer `k`. Your task is to find the length of the longest substring that contains the same character, where you can replace at most `k` characters in the string to form this substring.

### Problem Explanation:

Given a string `s`, we need to determine the length of the longest substring where all characters are the same, with the possibility of replacing at most `k` characters in the string.

---

## Approach:

The problem can be solved using the **sliding window** technique, where we maintain a window of characters that contains at most `k` different characters (the ones that we will replace). We will use the following approach:

### **findlength Function**:
This helper function calculates the maximum length of a substring that consists entirely of the character `c` after replacing at most `k` characters in the string `s`.

### Parameters:
- `string s`: The input string.
- `int k`: The maximum number of characters that can be replaced.
- `char c`: The character to form the longest substring of.

### **Solution Steps**:

1. **Initialization:**
   - Start with `i` as the right boundary of the sliding window.
   - `l` is the left boundary of the sliding window.
   - `cnt` counts the number of characters that need to be replaced to make the substring consist entirely of `c`.
   - `maxlength` stores the maximum length of the desired substring found so far.

2. **Sliding Window Technique:**
   - Iterate over the string with `i` as the right boundary.
   - If the character at the current position `s[i]` is not equal to `c`, increment `cnt`.
   - If `cnt` exceeds `k`, adjust the left boundary `l` until `cnt` is less than or equal to `k`.
   - Update `maxlength` with the length of the current valid window (`i - l + 1`).

3. **Return the result:**
   - Return the maximum length found for the character `c`.

---

## Test Cases

### Test Case 1: Standard Case

**Input:**  
`s = "ABAB"`, `k = 2`

**Output:**  
`4`

**Explanation:**  
By changing the first two 'A's or the first two 'B's, we can make the entire string consist of the same character. Thus, the maximum length of the substring is `4`.

---

### Test Case 2: Case with a Large k

**Input:**  
`s = "AABABBA"`, `k = 1`

**Output:**  
`4`

**Explanation:**  
By replacing the middle 'B' with an 'A', we can form the substring "AAAA" of length 4. The maximum length is `4`.

---

### Test Case 3: No Replacement Needed

**Input:**  
`s = "BBBB"`, `k = 2`

**Output:**  
`4`

**Explanation:**  
The entire string already consists of the same character, so no replacements are needed. The maximum length is `4`.

---

### Test Case 4: Large String with One Change

**Input:**  
`s = "AABACD"`, `k = 1`

**Output:**  
`3`

**Explanation:**  
By changing one 'C' to 'A', we can form the substring "AAA" of length 3. Thus, the maximum length is `3`.

---

### Test Case 5: Multiple Characters to Replace

**Input:**  
`s = "AABBAA", k = 2`

**Output:**  
`4`

**Explanation:**  
By changing the first two 'B's to 'A', we can form the substring "AAAA" of length 4. The maximum length is `4`.

---


Saurabh Patil

# Unique Paths Problem

**Problem Statement:**

Given a grid of size `m x n`, you need to find the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time. 

---

## Solution Explanation

### **calc Function**

The `calc` function recursively computes the number of unique paths from a given cell `(i, j)` in the grid to the bottom-right corner `(m-1, n-1)`.

#### Steps:
1. **Base Case (Reaching the Bottom-Right Corner):**
   - If the current cell `(i, j)` is the bottom-right corner `(m-1, n-1)`, return 1 because there's exactly one unique path (the path where you are already at the destination).
   
2. **Out of Bounds Case:**
   - If the current cell `(i, j)` is outside the grid boundaries (i.e., `i >= m` or `j >= n`), return 0 since there are no valid paths from this point.

3. **Memoization Check:**
   - Before proceeding with the recursive calculation, check if the number of paths from the current cell `(i, j)` has already been computed and stored in `dp[i][j]`. If `dp[i][j]` is not `-1`, return the cached value to avoid redundant calculations and improve efficiency.

4. **Recursive Calculation:**
   - Calculate the number of paths by recursively calling `calc` for the right and down cells:
     - Right: `calc(i, j+1)` (move right)
     - Down: `calc(i+1, j)` (move down)
   - The sum of these two values gives the total number of unique paths from the current cell `(i, j)`.
   - Store this result in `dp[i][j]` for future use.

---

### **uniquePaths Function**

The `uniquePaths` function initializes the memoization array and starts the recursive calculation from the top-left corner `(0, 0)`.

#### Steps:
1. **Initialization of DP Array:**
   - Create a 2D vector `dp` of size `(m+1) x (n+1)` initialized with `-1`. This 2D array will store the number of unique paths from each cell. The extra row and column are included to handle boundary conditions more gracefully.

2. **Initial Call to calc:**
   - Start the recursion from the top-left corner `(0, 0)` by calling the `calc` function.

3. **Special Case for 1x1 Grid:**
   - If the grid size is `1x1`, return the result directly (which is 1, as there is only one cell).

4. **Return the Result:**
   - After the recursion, return the number of unique paths stored in `dp[0][0]`, which represents the top-left cell.

---

## Test Cases

### Test Case 1: Basic Case

**Input:**  
`m = 3, n = 2`

**Output:**  
`3`

**Explanation:**  
There are 3 unique paths from the top-left to the bottom-right corner in a `3x2` grid:
1. Move right, move right, move down.
2. Move right, move down, move right.
3. Move down, move right, move right.

---

### Test Case 2: Single Row Grid

**Input:**  
`m = 1, n = 5`

**Output:**  
`1`

**Explanation:**  
In a `1x5` grid, there is only one path: move right repeatedly.

---

### Test Case 3: Single Column Grid

**Input:**  
`m = 6, n = 1`

**Output:**  
`1`

**Explanation:**  
In a `6x1` grid, there is only one path: move down repeatedly.

---

### Test Case 4: Square Grid

**Input:**  
`m = 4, n = 4`

**Output:**  
`20`

**Explanation:**  
There are 20 unique paths from the top-left to the bottom-right corner in a `4x4` grid.

---

### Test Case 5: Large Grid

**Input:**  
`m = 10, n = 10`

**Output:**  
`48620`

**Explanation:**  
The number of unique paths for a `10x10` grid is 48620.

---

## Time Complexity:

- **Recursive Calls:** The time complexity is reduced due to memoization. The recursion explores each cell in the grid only once.
- **Overall Time Complexity:** `O(m * n)`, where `m` and `n` are the number of rows and columns in the grid.

## Space Complexity:

- **Space Complexity:** `O(m * n)` for storing the memoization array.


# Number of Good Nodes Problem

## Problem Statement:

In a binary tree, a node is considered "good" if the value of the node is greater than or equal to the maximum value encountered on the path from the root to that node. Your task is to find the number of good nodes in the binary tree.

### Definition:
- **Good Node**: A node is good if, along the path from the root to this node, no node has a value greater than the value of the current node.

---

## Approach

We will use a Depth-First Search (DFS) approach to traverse the tree and calculate the number of good nodes.

### **Recursive DFS Function:**
1. **Parameters:**
   - `node`: Current node in the tree.
   - `max_val`: The maximum value encountered along the path from the root to the current node.

2. **Base Case:**
   - If the current node is `null`, return `0` since no node exists.

3. **Processing Current Node:**
   - If the current node's value is greater than or equal to `max_val`, it is a good node.
   - Increase the count of good nodes by 1.

4. **Recursive Call:**
   - Perform DFS on both the left and right children, updating the `max_val` with the maximum value between `max_val` and the current node's value.

5. **Return the Total Count:**
   - Return the total number of good nodes by adding the results from the left and right subtrees, including the current node if it's good.

---

## Test Cases

### Test Case 1: Simple Tree

**Input:**

    8
   / \
  5   9
 / \   \
4   7   10
       /  \
      6   15


**Output:**  
`7`

**Explanation:**  
The good nodes are 8, 9, 10, 6, and 15, since their values are greater than or equal to the maximum encountered along the path from root.

---

## Time Complexity:
- **Time Complexity:** `O(N)` where `N` is the number of nodes in the tree, because we visit each node once.

## Space Complexity:
- **Space Complexity:** `O(H)` where `H` is the height of the tree. This is the space used by the recursive stack in the DFS traversal.


# Problem: Find the Number of Winning Players

## Problem Statement:

We are given a 2D array `pick` where:
- The first column represents the **ball number**.
- The second column represents the **color of the ball**.

The task is to return the count of balls that satisfy the following condition:
- For a particular ball number in the first column, it should be **less** than the count of balls with the same color as indicated by the second column.

---

## Approach:

### Step 1: Sorting the Array

- **Sort by Ball Number (First Column):**  
  First, sort the array based on the first column (ball number) in ascending order.

- **Sort by Ball Color (Second Column):**  
  Without altering the first column, sort the array again based on the second column (ball color) in ascending order.

### Step 2: Initial Setup

- **Base Condition for Ball Number 0:**
  - If ball number `0` is present in the array, it automatically satisfies the condition. In this case, increment the count by one.
  - Set `prev1` to `0` (representing the ball number) and `prev2` to the color of the ball in the last occurrence of ball number `0`.
  - Increment the pointer to point to the ball number next to `0`.

### Step 3: Iterative Process

- **Pointer Initialization:**
  - If the base condition is not met, point to the second row with a pointer `ti`, and assign the current count of balls with the same color as the `ti-th` ball number to `ccount`.
  - Set `prev1` and `prev2` to the first and second column values of the 0th row, respectively.

- **Loop through the Array:**
  - Iterate through the array using the `ti` pointer.

  - **Skipping Unnecessary Iterations:**
    - If `pick[i][0] - ccount > (pick.size() - i) - 1`, skip the rest of the loop. This condition checks if the current ball number is greater than the number of remaining rows in the array.

### Step 4: Updating the Count

- **Check Matching Condition:**
  - If the current ball number (`pick[i][0]`) and ball color (`pick[i][1]`) match `prev1` and `prev2`, respectively, increment the current count (`ccount`).

- **Final Condition:**
  - If `ccount == pick[i][1] + 1`, increment the final count.

### Step 5: Reset Counters

- If the current ball number or color does not match `prev1` or `prev2`, update `prev1` to the current ball number, `prev2` to the current ball color, and reset `ccount` to `1`.

### Step 6: Final Step

- After iterating through the entire array, return the final count of balls that satisfy the condition.

---

## Example Walkthrough

### Example 1:

**Input:**

```plaintext
pick = [
  [0, 3],
  [1, 3],
  [2, 4],
  [3, 2],
  [4, 2]
]

```Output:

1```

# Sliding Puzzle Problem

## Problem Description
You are given a 2x3 sliding puzzle grid. The goal is to move the tiles to match the target state `"123450"` (where `0` represents the blank space). You can only move tiles adjacent to the blank space into the blank space. The task is to find the minimum number of moves to reach the target state or return `-1` if it is impossible.

---

## Code Explanation

### 1. Initialization
```java
String target = "123450";
String start = "";
```

- The `target` string represents the goal configuration of the puzzle.
- The `start` string is constructed by concatenating the given 2D array `board` into a single string. This makes it easier to manipulate states in the BFS algorithm.

---

### 2. Create Adjacency List for Moves
```java
int[][] dirs = new int[][] { 
    { 1, 3 }, 
    { 0, 2, 4 }, 
    { 1, 5 }, 
    { 0, 4 }, 
    { 1, 3, 5 }, 
    { 2, 4 } 
};
```

- Each index of the string (representing the board) corresponds to a possible position of the blank (`0`).
- `dirs[i]` contains the indices that the blank space (`0`) can swap with for the corresponding position `i`.

---

### 3. BFS Setup
```java
Queue<String> queue = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int res = 0;
```

- A `queue` is used for BFS to explore all possible states level by level.
- A `HashSet visited` is used to track states that have already been processed to avoid redundant calculations.
- `res` keeps track of the number of moves taken so far.

---

### 4. BFS Loop
```java
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        String cur = queue.poll();
        if (cur.equals(target)) {
            return res;
        }
```

- The BFS explores all possible states level by level.
- The `size` variable ensures that each level of moves is processed in one iteration.
- If the current state `cur` matches the target, the function returns `res` (the number of moves).

---

### 5. Generate Next States
```java
int zero = cur.indexOf('0');
for (int dir : dirs[zero]) {
    String next = swap(cur, zero, dir);
    if (visited.contains(next)) {
        continue;
    }
    visited.add(next);
    queue.offer(next);
}
```

- Find the index of the blank space (`0`) in the current state (`cur`).
- Use the adjacency list `dirs` to determine possible swaps.
- For each valid swap, generate the new state `next` and:
  - Skip if it is already visited.
  - Otherwise, mark it as visited and add it to the BFS queue.

---

### 6. Swap Helper Function
```java
private String swap(String str, int i, int j) {
    StringBuilder sb = new StringBuilder(str);
    sb.setCharAt(i, str.charAt(j));
    sb.setCharAt(j, str.charAt(i));
    return sb.toString();
}
```

- This function swaps the characters at indices `i` and `j` in the string to create a new board state.

---

### 7. Return the Result
```java
return -1;
```

- If the queue is empty and no solution is found, return `-1` to indicate that it is impossible to reach the target state.

---

## Key Concepts

1. **String Representation**: The board is converted into a string to simplify state manipulation.
2. **Breadth-First Search (BFS)**: This ensures the minimum number of moves is found because BFS explores all states at the current depth before moving deeper.
3. **Visited Set**: Tracks already-explored states to prevent infinite loops.

---

## Test Cases

### Example 1
Input:
```java
int[][] board = {
    {1, 2, 3},
    {4, 0, 5}
};
```
Output:
```java
1
```
Explanation: Swap `0` and `5` to achieve the target state.

### Example 2
Input:
```java
int[][] board = {
    {1, 2, 3},
    {5, 4, 0}
};
```
Output:
```java
-1
```
Explanation: It is impossible to reach the target state from this configuration.

### Example 3
Input:
```java
int[][] board = {
    {4, 1, 2},
    {5, 0, 3}
};
```
Output:
```java
5
```
Explanation: Requires 5 moves to achieve the target state.

### Example 4
Input:
```java
int[][] board = {
    {1, 2, 3},
    {0, 4, 5}
};
```
Output:
```java
2
```
Explanation: Swap `0` with `4` and then with `5` to reach the target.

---

## Edge Cases

1. **Already Solved:**
   Input:
   ```java
   int[][] board = {
       {1, 2, 3},
       {4, 5, 0}
   };
   ```
   Output:
   ```java
   0
   ```
   Explanation: The board is already in the target state.

2. **Unsolvable Puzzle:**
   Input:
   ```java
   int[][] board = {
       {3, 2, 1},
       {4, 5, 0}
   };
   ```
   Output:
   ```java
   -1
   ```
   Explanation: The puzzle configuration cannot be solved.


# Special Pairs Problem

## Problem Description
You are given an array `nums` consisting of integers. A pair of consecutive integers `(nums[i], nums[i+1])` is called a **special pair** if both integers belong to the same "team":

- **Team Even (🟢)**: Both integers are even.
- **Team Odd (🔴)**: Both integers are odd.

The task is to process several queries. Each query is of the form `[left, right]`, and you need to determine whether there are no special pairs between indices `left` and `right` in the array. If there are no special pairs, return `true` for the query; otherwise, return `false`.

---

## Approach

### Step 1: Build the Prefix Array
We create a prefix array `prefix` that counts the cumulative number of special pairs as we traverse the array:

- If two consecutive numbers have the same "team" (both 🟢 or both 🔴), we increase the count.
- Otherwise, the count remains unchanged.

For example, for `nums = [4, 3, 1, 6]`:

- At index `0`: No pairs yet → `prefix[0] = 0`.
- At index `1`: `(4, 3)` isn’t special → `prefix[1] = 0`.
- At index `2`: `(3, 1)` is special → `prefix[2] = 1`.
- At index `3`: `(1, 6)` isn’t special → `prefix[3] = 1`.

Final prefix array: `[0, 0, 1, 1]`.

### Step 2: Process Queries
For each query `[left, right]`:

- Calculate the number of special pairs in the range using the prefix array:
  ```java
  specialCount = prefix[right] - (left > 0 ? prefix[left - 1] : 0);
  ```
- If `specialCount == 0`, return `true`; otherwise, return `false`.

---

## Complexity
- **Building the prefix array**: `O(n)`, where `n` is the size of `nums`.
- **Processing queries**: `O(q)`, where `q` is the number of queries.

Total: `O(n + q)`.

---

## Test Cases

### Example 1
Input:
```java
nums = [4, 3, 1, 6];
queries = [[0, 1], [1, 2], [0, 3]];
```
Output:
```java
[true, false, false]
```
Explanation:
- Query `[0, 1]`: No special pairs → `true`.
- Query `[1, 2]`: `(3, 1)` is special → `false`.
- Query `[0, 3]`: `(3, 1)` is special → `false`.

### Example 2
Input:
```java
nums = [2, 4, 6, 8];
queries = [[0, 3], [1, 2]];
```
Output:
```java
[false, false]
```
Explanation:
- Query `[0, 3]`: All pairs are special → `false`.
- Query `[1, 2]`: `(4, 6)` is special → `false`.

### Example 3
Input:
```java
nums = [1, 3, 5, 7];
queries = [[0, 2], [1, 3]];
```
Output:
```java
[false, false]
```
Explanation:
- Query `[0, 2]`: All pairs are special → `false`.
- Query `[1, 3]`: All pairs are special → `false`.

# Find Longest Special Substring That Occurs Thrice

## Problem Description
You are given a string `s`, and your task is to find the maximum length `x` of a **special substring** that appears at least three times in `s`.

A **special substring** is defined as a substring containing only one unique character (e.g., `"aaa"`, `"bbbb"`).

If no such substring exists, return `-1`.

---

## Approach

### 1. Binary Search
The problem exhibits a monotonic property:
- If a special substring of length `x` exists at least three times, then all substrings of length `< x` are also valid.
- Conversely, if `x` is invalid, all `x > x` are also invalid.

Using binary search, we efficiently search for the largest possible `x`:
- Start with `l = 1` (minimum substring length) and `r = n` (length of the string `s`).
- Use a helper function to validate if a given `x` is possible.

### 2. Sliding Window Validation
To validate if a given `x` is valid:
- Use a sliding window of size `x` to traverse the string.
- Ensure each window contains only identical characters.
- Track occurrences of these substrings using a hashmap.
- Return `true` if any substring occurs at least three times.

### 3. Iterative Binary Search
- Perform binary search to find the largest valid `x`.
- If `l` is valid after the search, return `l`.
- Otherwise, return `-1`.

---

## Complexity

- **Time Complexity**: 
  - Binary Search: `O(log n)` iterations for a string of length `n`.
  - Validation for each `x`: `O(n)` using sliding window.
  - Total: `O(n log n)`.

- **Space Complexity**: 
  - `O(n)` for the hashmap used during validation.

---

## Test Cases

### Example 1
**Input:**
```text
s = "aaabbbaaa"
```
**Output:**
```text
3
```
**Explanation:**
- The substring `"aaa"` occurs 3 times in the string.

---

### Example 2
**Input:**
```text
s = "abc"
```
**Output:**
```text
-1
```
**Explanation:**
- No special substring occurs at least three times.

---

### Example 3
**Input:**
```text
s = "aaaaaa"
```
**Output:**
```text
6
```
**Explanation:**
- The substring `"aaaaaa"` is the entire string and appears 3 times (as a whole).

---

### Example 4
**Input:**
```text
s = "abbbbbbbc"
```
**Output:**
```text
5
```
**Explanation:**
- The substring `"bbbbb"` appears at least 3 times in the string.

---

### Example 5
**Input:**
```text
s = "aabbcc"
```
**Output:**
```text
-1
```
**Explanation:**
- No substring satisfies the condition of occurring 3 times.

---

### Edge Cases

1. **Single Character String:**
   **Input:**
   ```text
   s = "a"
   ```
   **Output:**
   ```text
   -1
   ```
   **Explanation:**
   A single character cannot occur 3 times as a substring.

2. **String with No Repeats:**
   **Input:**
   ```text
   s = "abcdef"
   ```
   **Output:**
   ```text
   -1
   ```
   **Explanation:**
   No character repeats consecutively.

3. **Already Valid Entire String:**
   **Input:**
   ```text
   s = "ccc"
   ```
   **Output:**
   ```text
   3
   ```
   **Explanation:**
   The entire string forms a valid substring of length 3, occurring exactly 3 times.

---


# 📚 Maximum Average Pass Ratio (LeetCode Problem 1792)

A school has multiple classes of students, and each class will have a **final exam**. Your task is to distribute a given number of extra brilliant students across these classes to **maximize the average pass ratio**. Here's how it works:

---

## Problem Description

You are given:

 ## 1. **`classes`**:
 A 2D array where each entry is of the form `classes[i] = [passi, totali]`:

   - `passi`: The number of students in the class who are guaranteed to pass.
   - `totali`: The total number of students in the class.

## 2. **`extraStudents`**: 
An integer representing the number of extra students you can assign to any class. These students are guaranteed to pass in the class they're assigned to.

---

### Definitions:
- **Pass Ratio of a Class**:  
  The ratio of passing students to total students:  
$$
\text{Pass Ratio} = \frac{\text{passi}}{\text{totali}}
$$
- **Average Pass Ratio Across All Classes**:  
  The sum of pass ratios of all classes divided by the total number of classes.
$$
\text{Average Pass Ratio} = \frac{\sum \left( \frac{\text{passi}}{\text{totali}} \right)}{n}
$$
- where 𝑛 is the total number of classes.
---

### Goal: ***Distribute the `extraStudents` in a way that **maximizes the average pass ratio** across all classes.***

---
## 🧪 Test Cases:

### Example 1:
**Input:** ``` classes = [[1, 2], [3, 5], [2, 2]];```
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;```extraStudents = 2;```

**Output:** ``` 0.78333;``` 

### **Example 2**:  

**Input:**  
```classes = [[2, 4], [3, 9], [4, 5], [2, 10]]```  
```extraStudents = 4```  

**Output:**  
```0.53485```  

## ✅ Constraints:

$$
1 \leq \text{classes.length} \leq 10^5
$$

$$
\text{classes}[i].\text{length} == 2
$$

$$
1 \leq \text{passi} \leq \text{totali} \leq 10^5
$$

$$
1 \leq \text{extraStudents} \leq 10^5
$$


#  Continuous Subarrays

####  **Difficulty:** Medium  
#### **Topics:** Arrays, Sliding Window  
---
## Problem Description:
You are given a **0-indexed** integer array `nums`. A subarray of `nums` is called **continuous** if it satisfies the following condition:

- Let `i, i + 1, ..., j` be the indices of the subarray. Then, for each pair of indices `i1` and `i2` such that `i <= i1, i2 <= j`, the absolute difference between the elements at those indices is at most 2:  
  `0 <= |nums[i1] - nums[i2]| <= 2`.

Your task is to **return the total number of continuous subarrays** present in `nums`.

### Key Notes:
- A **subarray** is a contiguous, non-empty sequence of elements within the array. 
- Continuous subarrays can have varying sizes ranging from 1 to the length of the array.
- The result is the sum of all valid continuous subarrays for all possible subarray sizes.

---

## Examples

### Example 1:
**Input:**  
 `nums = [5, 4, 2, 4]`  
**Output:**  
`8`  

**Explanation:**  
Continuous subarrays are:  
1. Subarrays of size 1:  
   - `[5]`, `[4]`, `[2]`, `[4]` (4 subarrays).  
2. Subarrays of size 2:  
   - `[5, 4]`, `[4, 2]`, `[2, 4]` (3 subarrays).  
   - These satisfy the condition since the absolute difference between any two elements in the subarray is at most 2.  
3. Subarray of size 3:  
   - `[4, 2, 4]` (1 subarray).  

There are no valid subarrays of size 4.  

**Total continuous subarrays = 4 + 3 + 1 = 8**.  

---

### Example 2:
**Input:**  
`nums = [1, 2, 3]`  

**Output:**  
`6`  

**Explanation:**  
Continuous subarrays are:  
1. Subarrays of size 1:  
   - `[1]`, `[2]`, `[3]` (3 subarrays).  
2. Subarrays of size 2:  
   - `[1, 2]`, `[2, 3]` (2 subarrays).  
3. Subarray of size 3:  
   - `[1, 2, 3]` (1 subarray).  

**Total continuous subarrays = 3 + 2 + 1 = 6**.  

---

## Constraints:
- `1 <= nums.length <= 10^5`  
  - The array can be very large, so an efficient solution is necessary.
- `1 <= nums[i] <= 10^9`  
  - The values in the array can be extremely large, so the algorithm must account for this.

---

## Approach to Solve:

### 1. Brute Force:
   - Iterate over all possible subarrays of `nums`.
   - For each subarray, check if the condition `0 <= |nums[i1] - nums[i2]| <= 2` is satisfied for all pairs within the subarray.  
   - This approach is computationally expensive with time complexity `O(n^3)` or `O(n^2)` (with optimizations).  
   - Not feasible for large arrays.

### 2. **Sliding Window or Two Pointers Technique:**  

1. **Sliding Window Approach**:  
   The code uses a sliding window technique to efficiently scan through the array and identify valid continuous subarrays. The window expands as long as the subarray remains "continuous" and shrinks when it becomes invalid.

### 2. **Tracking Frequency of Elements**:  
   A  `HashMap` is used to track the frequency of elements in the current window. This helps verify whether the window is valid (i.e., the difference condition is satisfied).

### 3. **Validation of Subarrays**:  
   For each new element added to the window:
 - The code checks if the current subarray (from `p1` to `i`) is valid.  
 - Validity is determined by ensuring that all numbers within the window differ by at most 2.

### 4. **Counting Valid Subarrays**:  
   For each valid subarray ending at index `i`, the code calculates the total number of subarrays that can be formed starting between `p1` (start of the window) and `i`:
   - The number of such subarrays is `(i - p1 + 1)`.

### 5. **Shrinking the Window**:  
   If the subarray becomes invalid, the start of the window (`p1`) is moved forward until the subarray becomes valid again.

### 6. **Summing Up**:  
   The total count of valid subarrays is accumulated as the window slides through the entire array.

---



This problem requires careful handling of large inputs while ensuring efficiency. An efficient implementation with the sliding window approach is most suitable.


#  Construct the Lexicographically Largest Valid Sequence

### Difficulty: `Medium`

### Problem Statement

Given an integer `n`, find a sequence that satisfies all of the following:

- The integer `1` occurs **once** in the sequence.
- Each integer between `2` and `n` occurs **twice** in the sequence.
- For every integer `i` between `2` and `n`, the **distance** between the two occurrences of `i` is exactly `i`.
- The **distance** between two numbers in the sequence, `a[i]` and `a[j]`, is defined as `|j - i|`.

Return the **lexicographically largest sequence**. It is **guaranteed** that a solution always exists.

A sequence `a` is **lexicographically larger** than a sequence `b` (of the same length) if in the first position where `a` and `b` differ, `a` has a number greater than the corresponding number in `b`.

For example, `[0,1,9,0]` is lexicographically larger than `[0,1,5,6]` because the first position they differ is at the third number, and `9` is greater than `5`.

---

### Example 1

**Input:**
```plaintext
n = 3
```

**Output:**
```plaintext
[3,1,2,3,2]
```

**Explanation:**
- `[2,3,2,1,3]` is also a valid sequence, but `[3,1,2,3,2]` is lexicographically larger.

---

### Example 2

**Input:**
```plaintext
n = 5
```

**Output:**
```plaintext
[5,3,1,4,3,5,2,4,2]
```

---

### Example 3

**Input:**
```plaintext
n = 4
```

**Output:**
```plaintext
[4,2,3,2,1,3,4]
```

---

### Constraints
-  `1 <= n <= 20 `


# Construct Smallest Number From DI String

### Problem Statement
You are given a string `pattern` consisting of the characters:
- `'I'` (Increasing): The next digit must be greater than the current one.
- `'D'` (Decreasing): The next digit must be smaller than the current one.

Your task is to generate the **smallest lexicographical** number using digits `1-9` (without repetition) that follows this pattern.

### Example 1
**Input:**  
`pattern = "IDID"`  

**Output:**  
`13254`  

**Explanation:**  
- `1 < 3` (I)  
- `3 > 2` (D)  
- `2 < 5` (I)  
- `5 > 4` (D)  

Other possible numbers are `"14253"` and `"15234"`, but `"13254"` is the smallest.

---

### Example 2
**Input:**  
`pattern = "DDD"`  

**Output:**  
`4321`  

**Explanation:**  
- `4 > 3` (D)  
- `3 > 2` (D)  
- `2 > 1` (D)  

Other possible numbers like `"9876"` or `"7654"` are larger.

---

### Constraints
- `1 <= pattern.length <= 8`
- `pattern` consists only of `'I'` and `'D'`.


# Find Elements in a Contaminated Binary Tree

### Problem Statement
You are given a contaminated binary tree where all `TreeNode.val` have been changed to `-1`. The tree follows these rules:

- The root node has a value of `0`.
- If a node has a value `x`, then:
  - Its left child (if exists) will have a value `2 * x + 1`.
  - Its right child (if exists) will have a value `2 * x + 2`.

### Task
Implement the `FindElements` class:

- `FindElements(TreeNode* root)`: Initializes the object with a contaminated binary tree and recovers it.
- `bool find(int target)`: Returns `true` if the `target` value exists in the recovered binary tree, otherwise returns `false`.

---


#### **Test Case 1: Single Node Tree**
##### **Input**
```json
["FindElements","find","find"]
[[[-1]],[0],[1]]
```
![tree1](https://res.cloudinary.com/dluehhlfs/image/upload/v1740103911/recovertree2_nyyys8.png)
##### **Output**
```json
[null,true,false]
```
##### **Explanation**
```plaintext
FindElements findElements = new FindElements([-1]);
findElements.find(0); // returns True (root is always 0)
findElements.find(1); // returns False (no left or right child exists)
```

#### **Test Case 2: Complete Binary Tree of Height 3**
##### **Input**
```json
["FindElements","find","find","find","find","find"]
[[[-1,-1,-1,-1,-1,-1,-1]],[3],[5],[6],[7],[8]]
```
![tree1](https://res.cloudinary.com/dluehhlfs/image/upload/v1740104268/recovertree1_thqsyt.png)

##### **Output**
```json
[null,true,true,true,false,false]
```
##### **Explanation**
```plaintext
FindElements findElements = new FindElements([-1,-1,-1,-1,-1,-1,-1]);
findElements.find(3); // returns True
findElements.find(5); // returns True
findElements.find(6); // returns True
findElements.find(7); // returns False (no node with value 7 exists)
findElements.find(8); // returns False (no node with value 8 exists)
```

---

### **Constraints**
- $$TreeNode.val = -1$$
- The height of the binary tree is $$\leq 20$$.
- The total number of nodes is in the range $$[1, 10^4]$$.
- $$find()$$ will be called at most $$10^4$$ times.
- $$0 \leq target \leq 10^6$$. 

---

### **Approach**
1. **Recover the tree using DFS or BFS**:
   - Start from the root and assign it `0`.
   - For each node `x`, assign its left child `2 * x + 1` and right child `2 * x + 2`.
   - Store these values in a `set` or `unordered_set` for quick lookup.
2. **Find operation in O(1)**:
   - Use a hash set to store valid node values for `O(1)` lookup in the `find()` function.

---

# Count the Misaligned Pairs

**Difficulty:** Medium

---

## Problem Statement

Given a **0-indexed** integer array `nums`, we define a pair of indices `(i, j)` as a **misaligned pair** if:

1. $ i < j $
2. The difference between the indices is **not equal** to the difference between the corresponding values. In other words, the pair is misaligned if:
$$
j - i ≠ \text{nums}[j] - \text{nums}[i]
$$
Your task is to determine the total number of misaligned (or "bad") pairs in the array.

---

## Examples

### Example 1

- **Input:** `nums = [3, 3, 3]`
- **Output:** `3`
- **Explanation:**
  - For the pair $(0, 1)$: $1-0 ≠ 3 - 3$ (i.e. $1 ≠ 0$)
  - For the pair $(0, 2)$: $2 ≠ 3 - 3$ (i.e. $2 ≠ 0$)
  - For the pair $(1, 2)$: $1 ≠ 3 - 3$ (i.e. $1 ≠ 0$)
  
Thus, there are **3** bad pairs in total.

---

### Example 2

- **Input:** `nums = [5, 6, 7, 8]`
- **Output:** `0`
- **Explanation:**
  This array forms an arithmetic progression with a common difference of 1. For every valid pair $(i, j)$:
$$
j - i = \text{nums}[j] - \text{nums}[i]
$$
  Hence, there are no bad pairs.
  
$$
j - i ≠ \text{nums}[j] - \text{nums}[i]
$$
  
  Therefore, no pairs are misaligned.

---

## Constraints

$$
1 \leq \text{nums.length} \leq 10^5
$$

$$
1 \leq \text{nums[i]} \leq 10^9
$$

---

## Additional Details
- The goal is to count the number of pairs that do not follow the natural alignment between the index difference and the value difference. This problem challenges you to design an efficient solution that can handle large input sizes without explicitly checking every possible pair.



# Recover From Preorder Traversal

### Problem Statement
You are given a string representing the preorder depth-first search (DFS) traversal of a binary tree. In this traversal, each node is output as a series of dashes followed by its integer value. The number of dashes indicates the node's depth in the tree:
- The root node (depth 0) is printed without any dashes.
- For any node at depth **D**, its children are printed with **D+1** leading dashes.
- **Note:** If a node has only one child, it is guaranteed to be the left child.

Your task is to reconstruct the original binary tree from this traversal string and return the tree's root.

---

### Task
Implement a function that, given the preorder traversal string, recovers the binary tree and returns its root.

---

### Test Cases

#### **Example 1**
**Input:**  
traversal = "10-20--30--40-50--60--70"
![graph](https://res.cloudinary.com/dluehhlfs/image/upload/v1740188914/recoverfrompreorder3_ih7dkn.png)
**Output:**  
[10, 20, 50, 30, 40, 60, 70]


**Explanation:**  
- The root is **10**.
- **20** is the left child of **10**.
- **30** and **40** are the left and right children of **20**, respectively.
- **50** is the right child of **10**.
- **60** and **70** are the left and right children of **50**, respectively.

---


#### **Example 2**
**Input:**  
traversal = "8-9--10---11-12--13---14"
[8, 9, 12, 10, null, 13, null, 11, null, 14]
![graph](https://res.cloudinary.com/dluehhlfs/image/upload/v1740188252/recoverfrompreorder_z9ioix.png)
**Explanation:**  
- The root is **8**.
- **9** is the left child of **8**.
- **10** is the left child of **9**.
- **11** is the left child of **10**.
- **12** is the right child of **8**.
- **13** is the left child of **12**.
- **14** is the left child of **13**.

---

#### **Example 3**
**Input:**  
traversal = "100-200--300---400---500-600--700"
![graph](https://res.cloudinary.com/dluehhlfs/image/upload/v1740188252/recoverfrompreorder2_hb7ck6.png)
**Output:**
[100, 200, 600, 300, null, 700, null, 400, 500]

**Explanation:**  
- The root is **100**.
- **200** is the left child of **100**.
- **300** is the left child of **200**.
- **400** and **500** are the left and right children of **300**, respectively.
- **600** is the right child of **100**.
- **700** is the left child of **600**.

---

### Constraints
- The number of nodes in the original tree is in the range **[1, 1000]**.
- **1 <= Node.val <= 10⁹**

---

### Approach
1. **Parse the Traversal String:**  
   - Read the string sequentially.
   - Count the number of consecutive dashes to determine the depth of the current node.
   - Parse the following digits to form the node's value.
2. **Construct the Tree:**  
   - Use a stack to maintain nodes along the current path.
   - For each node encountered, compare its depth with the depth of the node on the top of the stack.
   - If the current node’s depth is greater, it is the left child of the previous node; otherwise, backtrack in the stack to find the correct parent and attach it as a right child.
3. **Return the Root:**  
   - After processing the entire string, the first element in the stack (or stored separately) will be the root of the reconstructed binary tree.

---


# Construct Binary Tree from Preorder and Postorder Traversal

### Problem Statement
You are given two arrays representing the `preorder` and `postorder` traversals of a binary tree with unique values. Your task is to reconstruct the binary tree from these traversals and return its root.

- **Preorder Traversal:** *Visit the root first, then the left subtree, and finally the right subtree.*
- **Postorder Traversal:** *Visit the left subtree first, then the right subtree, and finally the root.*

If multiple valid trees exist, you can return any one of them.

---

### Task
Implement a function that reconstructs the binary tree given:
- `preorder`: an array of integers representing the preorder traversal.
- `postorder`: an array of integers representing the postorder traversal.

---

### Test Cases

#### **Test Case 1**
**Input:**
```json
  "preorder": [1, 2, 4, 5, 3, 6, 7],
  "postorder": [4, 5, 2, 6, 7, 3, 1]

```
![binary tree](https://res.cloudinary.com/dluehhlfs/image/upload/v1740277550/constructprepost2_nrh9uv.png)
**Output:**
```
[1,2,3,4,5,6,7]
```

Test Case 2

Input:
```
  "preorder": [10, 20, 40, 50, 30, 60],
  "postorder": [40, 50, 20, 60, 30, 10]
```
![binary tree](https://res.cloudinary.com/dluehhlfs/image/upload/v1740277550/constructprepost1_gxdhaw.png)
**OUTPUT:**
```
[10,20,30,40,50,60]
```

### Constraints
- The number of nodes is between **1** and **30**.
- All values in `preorder` are unique.
- `postorder` is a permutation of `preorder` and represents the postorder traversal of the same tree.

### Approach

1. **Identify the Root:**
   - The first element in `preorder` is the root of the tree.
   - The last element in `postorder` is also the root.
2. **Divide and Conquer:**
   - Use the next element in `preorder` (after the root) to determine the boundary of the left subtree in `postorder`.
   - Recursively construct the left subtree using the corresponding segments from both arrays.
   - Similarly, construct the right subtree with the remaining segments.
3. **Construct the Tree:**
   - Combine the results from the recursive calls to form the entire binary tree.
   - Return the root of the constructed tree.


Select a card whose code you want to track