# Problem: Counting Words With a Given Prefix

## Description:
You are given:
- An array of strings `words`.
- A string `pref`.

Your task is to **count how many strings in `words` start with the prefix `pref`**. 

A prefix of a string `s` is defined as any leading contiguous substring of `s`. For example:
- "pre" is a prefix of "prefix".
- "ex" is a prefix of "example".

Return the count of strings in `words` that have `pref` as their prefix.

---

## Examples:

### Example 1:
**Input:**  
`words = ["apple", "apply", "application", "banana"]`  
`pref = "app"`  

**Output:**  
`3`  

**Explanation:**  
The strings that start with the prefix "app" are:  
- "apple"
- "apply"
- "application"  

So, the result is `3`.

---

### Example 2:
**Input:**  
`words = ["cat", "car", "dog", "cart"]`  
`pref = "ca"`  

**Output:**  
`3`  

**Explanation:**  
The strings that start with the prefix "ca" are:  
- "cat"
- "car"
- "cart"  

So, the result is `3`.

---

### Example 3:
**Input:**  
`words = ["hello", "world", "hi", "house"]`  
`pref = "ho"`  

**Output:**  
`1`  

**Explanation:**  
The only string that starts with the prefix "ho" is:  
- "house"  

So, the result is `1`.

---


## Constraints:
1. $$1 \leq \text{words.length} \leq 100$$  
2. $$1 \leq \text{words[i].length}, \text{pref.length} \leq 100$$  
3. All strings in $$\text{words}$$ and $$\text{pref}$$ consist of lowercase English letters.


---

## Goal:
Write a function that takes the array `words` and the string `pref` as input and returns the count of strings in `words` that start with the prefix `pref`.


Saurabh Patil

# Generate Valid Parentheses Combinations  

**Problem Statement:**  
Given an integer `n`, generate all combinations of well-formed parentheses with `n` pairs.

---

## Approach  

We can use a recursive function to explore different possibilities for forming valid parentheses. The function keeps track of the number of opening and closing brackets, as well as the temporary string formed during the process.

### Recursive Function (`calculate`):  
- **Parameters:**  
  - `open_brackets`: Number of opening brackets used so far.  
  - `close_brackets`: Number of closing brackets used so far.  
  - `n`: Total number of pairs required.  
  - `s`: A list to store valid parentheses combinations.  
  - `t`: Temporary string to build the current combination.  

- **Base Case:**  
  - If `open_brackets` and `close_brackets` are both equal to `n`, append `t` to the list `s` and return.

- **Recursive Steps:**  
  1. If `open_brackets` is less than `n`, add an opening bracket `(` to `t` and recursively call the function with `open_brackets + 1`.  
  2. If `close_brackets` is less than `open_brackets`, add a closing bracket `)` to `t` and recursively call the function with `close_brackets + 1`.

---

## Main Function (`generateParenthesis`):  
1. Initialize an empty list `result`.  
2. Call the `calculate` function with initial parameters:  
   - `open_brackets = 0`, `close_brackets = 0`, `n`, `result`, and an empty string `t`.  
3. Return the list `result` containing all valid parentheses combinations.

---

## Example Walkthrough  

### Example Input:  
`n = 3`

### Execution:  
- The recursive function generates combinations step-by-step:  
  - `((()))`  
  - `(()())`  
  - `(())()`  
  - `()(())`  
  - `()()()`  

### Output:  
`["((()))", "(()())", "(())()", "()(())", "()()()"]`

---

## Test Cases  

### Test Case 1:  
**Input:**  
`n = 1`  

**Output:**  
`["()"]`  

---

### Test Case 2:  
**Input:**  
`n = 2`  

**Output:**  
`["(())", "()()"]`  

---

### Test Case 3:  
**Input:**  
`n = 3`  

**Output:**  
`["((()))", "(()())", "(())()", "()(())", "()()()"]`  

---

### Test Case 4: Edge Case  
**Input:**  
`n = 0`  

**Output:**  
`[]`  

---

## Complexity Analysis  

### Time Complexity:  
- The number of valid parentheses combinations is the **n-th Catalan number**, which grows exponentially.  
- Therefore, the time complexity is **O(4^n / √n)**.  

### Space Complexity:  
- The space complexity is **O(n)** due to the recursion stack.



# Leetcode Problem:  Map of Highest Peak
### Problem Description

You are given a matrix `isWater` of size `m x n` where:  
- `isWater[i][j] == 0`: This cell represents land.  
- `isWater[i][j] == 1`: This cell represents water.  

The input specifies where `water` and `land` cells are located, but it does **not specify the `heights` of the land cells**. Your task is to assign heights to the land cells following these `rules`:  
1. **Water cells must have a height of `0`.**  
2. **Any two adjacent cells** (north, south, east, west) **must differ in height by at most `1`.** This ensures a smooth gradient of heights between neighboring cells.  
3. Assign heights to land cells in a way that maximizes the **highest height** in the matrix.  

Your goal is to return a matrix `height` of size `m x n` where `height[i][j]` represents the height of cell `(i, j)` while following the rules.

---
### Examples

#### Example 1:
**Input**:  
`isWater = [[0,1], [0,0]]`  
![input](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746470/mapofhighestpeak_dig1_mp5rez.png)
**Output**:  
`height = [[1,0], [2,1]]`  
![output](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746470/mapofhighestpeak_dig2_rkfe8j.png)
**Explanation**:  
- The water cell at `(0,1)` has height `0` (rule #1).  
- Its adjacent land cells `(0,0)` and `(1,1)` have heights `1` and `1`, differing by exactly `1` (rule #2).  
- The bottom-left cell `(1,0)` has height `2`, which is the highest possible height while meeting the adjacency rule (rule #3).  

#### Example 2:
**Input**:  
`isWater = [[0,0,1], [1,0,0], [0,0,0]]`  


**Output**:  

`height = [[1,1,0], [0,1,1], [1,2,2]]`  


**Explanation**:  
- All water cells `(0,2)` and `(1,0)` have height `0`.  
- Land cells around the water are assigned increasing heights, forming a gradient that satisfies the adjacency rule.  
- The highest height in this matrix is `2`.  

---

### Approach to Solve the Problem
1.**Initialization**:  
Start by creating the `height` matrix where all cells are initially unassigned. Assign `0` to all water cells since water must have height `0`. 

2.  **Use BFS (Breadth-First Search)**:  
   Perform a multi-source BFS starting from all water cells (`height = 0`) simultaneously.  
    - Push all water cells into a queue.  
    - As you process each cell, assign heights to neighboring land cells if they are not already assigned.  
    - Ensure the height of a neighboring cell is exactly `1` more than the current cell’s height.
4. **Propagation of Heights**:  
   The BFS will propagate heights outward from water cells.
    - Cells farther from water will have higher heights.
    - This ensures that the maximum height is reached at the farthest land cells.
4. **Output the Matrix**:  
   Once BFS completes, the `height` matrix will be filled, and the maximum height will naturally be achieved.
---

### Key Observations
1. Water cells act as the starting point (height `0`) for spreading heights to the surrounding land.
2. The farther a land cell is from water, the greater its height, due to the adjacency constraint.
3. Using BFS ensures that each cell is processed in the shortest possible path from the water, which guarantees that heights are maximized correctly.

---

### Constraints
- Matrix size: `1 <= m, n <= 1000`.  
  This ensures the algorithm must be efficient to handle large matrices.  
- At least one water cell exists (`isWater` contains at least one `1`).  

---

### Why BFS?
- BFS is ideal for problems requiring shortest-path propagation, like this one, where heights depend on the shortest distance from water.  
- It processes all cells layer by layer, ensuring heights increase uniformly from water.

---

### Complexity
1. **Time Complexity**:  
   - BFS processes each cell exactly once, so the time complexity is **O(m * n)**.  
2. **Space Complexity**:  
   - The queue used in BFS requires space proportional to the number of cells, which is also **O(m * n)**.  

This ensures the solution is efficient and scalable for large inputs.


# Problem Summary: Minimum Cost to Make a Valid Path in a Grid

You are given a grid with `m x n` dimensions, where each cell contains an arrow pointing to one of four directions:

1. **Right** (1): Move to the cell on the right.
2. **Left** (2): Move to the cell on the left.
3. **Down** (3): Move to the cell below.
4. **Up** (4): Move to the cell above.

- You start at the top-left corner `(0, 0)` and aim to reach the bottom-right corner `(m-1, n-1)` by following the arrows.
- If necessary, you can modify the arrow in a cell at a cost of `1`.
- The goal is to calculate the **minimum cost** required to create at least one valid path from the start to the end of the grid.

### Examples:
1. **Input:** `[[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]`  
![image](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746479/Screenshot_2025-01-18_080833_lykixx.png)

   ### **Output:** `3`  
   **Explanation:** Modify arrows in 3 cells to create a valid path from `(0, 0)` to `(3, 3)`.  
2. **Input:** `[[1,1,3],[3,2,2],[1,1,4]]`  

   **Output:** `0`  
   **Explanation:** A valid path already exists without any modifications.
3. **Input:** `[[1,2],[4,3]]`  
   **Output:** `1`  
   **Explanation:** Modify one cell's arrow to create a valid path.

### Constraints:

- `1 <= m, n <= 100`
- Each cell contains a value from `1` to `4`.


# Problem Statement
Given an m x n matrix (a grid) of integers, modify the matrix in-place such that all elements in any row or column
that contains a zero are set to zero.

### Approach
The approach involves three steps:

1.  **Identify Rows and Columns with Zeros**: Traverse the entire matrix to find rows and columns that contain at
least one zero.
2. **Mark Rows and Columns for Zeroing**: Use separate arrays to mark which rows and columns need to be set to
zero based on the previous step.
3. **Set Elements to Zero**: Iterate through the marked rows and columns and set all their elements to zero.

### Solution Code (Conceptual)
```markdown
function setZeroes(matrix) {
    let m = matrix.length;
    if (m === 0) return;
    let n = matrix[0].length;

    // Arrays to mark which rows and columns need to be set to zero
    let zeroesRow = new Array(m).fill(false);
    let zeroesCol = new Array(n).fill(false);

    // Step 1: Identify rows and columns containing zeros
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                zeroesRow[i] = true;
                zeroesCol[j] = true;
            }
        }
    }

    // Step 2: Set the entire row or column to zero
    for (let i = 0; i < m; i++) {
        if (zeroesRow[i]) {
            matrix[i].fill(0);
        }
    }

    for (let j = 0; j < n; j++) {
        if (zeroesCol[j]) {
            // Ensure all elements in this column are set to zero
            for (let i = 0; i < m; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    return matrix;
}
```

### Solution Explanation
 1. **Identify Rows and Columns with Zeros**: We iterate through each element of the matrix. If we encounter a
zero, we mark its corresponding row and column in `zeroesRow` and `zeroesCol`, respectively.
2. **Mark Rows and Columns for Zeroing**: After identifying all rows and columns containing zeros, we set those
marked rows to all zeros using `fill(0)`. We then iterate through each marked column and set each element in that
column to zero.
3. **Edge Cases**: This approach handles cases where the matrix contains only one row or one column correctly by
ensuring both steps (row marking and column iteration) are performed, thus avoiding any missed elements due to
overwriting.



### Space Complexity
- The space complexity of this solution is `O(m + n)`, where `m` is the number of rows and `n` is the number of columns.
- This is because we use two additional arrays (`zeroesRow` and `zeroesCol`) to keep track of which rows and columns need to be zeroed out.

### Example Walkthrough
Consider a 3x3 matrix:
```
1 2 0
4 5 6
7 8 9
```

- **Step 1**: Identify zeros at position (0,2). Mark row 0 and column 2.
- **Step 2**: Set all elements in row 0 to zero. The matrix becomes:
```
0 0 0
4 5 6
7 8 9
```

- Then, set all elements in column 2 to zero. The final matrix is:
```
0 0 0
4 5 0
7 8 0
```


### Key Takeaways
- This approach efficiently modifies the matrix in place with a time complexity of O(m * n) and minimal additional space, making it suitable for large matrices while adhering to constraints.


# Problem: `Find Next Permutation`

##### **Difficulty:** `Medium`

### **Problem Description**
A **permutation** of an array of integers is an arrangement of its elements into a sequence or linear order.

For example, for `arr = [1,2,3]`, the following are all the permutations:

```
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
```

The **next permutation** of an array is the next lexicographically greater permutation of its integers. More formally, if all permutations are sorted in ascending lexicographical order, the next permutation is the one that follows it in that order.

If no such arrangement is possible (i.e., the array is in descending order), rearrange the array as the **smallest possible order** (sorted in ascending order).

### **Examples**

- The next permutation of `arr = [1,2,3]` is `[1,3,2]`.
- The next permutation of `arr = [2,3,1]` is `[3,1,2]`.
- The next permutation of `arr = [3,2,1]` is `[1,2,3]` (since no larger permutation exists).

### **Task**
Given an array of integers `nums`, find the **next permutation** of `nums`.

- The replacement must be **in-place** (i.e., modify `nums` directly).
- Use only **constant extra memory**.

---


### **Examples**

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

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

#### **Example 3**
**Input:**
```python
nums = [1,1,5]
```
**Output:**
```python
[1,5,1]
```

#### **Example 4** *(Edge Case: Single element array)*
**Input:**
```python
nums = [5]
```
**Output:**
```python
[5]  # No change
```

#### **Example 5** *(Edge Case: Already largest permutation)*
**Input:**
```python
nums = [9,8,7,6,5,4,3,2,1]
```
**Output:**
```python
[1,2,3,4,5,6,7,8,9]  # Reset to lowest order
```

---

### **Constraints**
- `1 <= nums.length <= 100`
- `0 <= nums[i] <= 100`
```



# Problem: `Maximum length of Strictly Increasing or Strictly Decreasing Subarray` 

### Problem Statement
You are given an array of integers `nums`. Your task is to find the length of the longest **strictly increasing** or **strictly decreasing** contiguous subarray.

### Constraints
- A subarray is a contiguous part of the array.
- A strictly increasing subarray means each element is greater than the previous one.
- A strictly decreasing subarray means each element is smaller than the previous one.
- The array may contain duplicate values, which break the strict order.

---

### Example 1

#### Input:
```plaintext
nums = [2, 5, 7, 6, 4]
```

#### Output:
```plaintext
3
```

#### Explanation:
- Strictly increasing subarrays: `[2]`, `[5]`, `[7]`, `[6]`, `[4]`, `[2,5]`, `[5,7]`, `[2,5,7]`
- Strictly decreasing subarrays: `[2]`, `[5]`, `[7]`, `[6]`, `[4]`, `[7,6]`, `[6,4]`, `[7,6,4]`
- Longest valid subarray: `[7,6,4]` (length = **3**)

---

### Example 2

#### Input:
```plaintext
nums = [8, 8, 8, 8]
```

#### Output:
```plaintext
1
```

#### Explanation:
- No valid increasing or decreasing sequence of length > 1.
- The longest valid subarray is just any single element (length = **1**).

---

### Example 3

#### Input:
```plaintext
nums = [9, 7, 5, 3, 1]
```

#### Output:
```plaintext
5
```

#### Explanation:
- Strictly decreasing subarrays: `[9]`, `[7]`, `[5]`, `[3]`, `[1]`, `[9,7]`, `[7,5]`, `[5,3]`, `[3,1]`, `[9,7,5]`, `[7,5,3]`, `[5,3,1]`, `[9,7,5,3]`, `[7,5,3,1]`, `[9,7,5,3,1]`
- Longest valid subarray: `[9,7,5,3,1]` (length = **5**)

---

### Additional Test Cases

#### Test Case 4
##### Input:
```plaintext
nums = [12, 14, 16, 13, 11, 9]
```
##### Output:
```plaintext
4
```
##### Explanation:
- Strictly increasing subarrays: `[12]`, `[14]`, `[16]`, `[13]`, `[11]`, `[9]`, `[12,14]`, `[14,16]`, `[12,14,16]`
- Strictly decreasing subarrays: `[12]`, `[14]`, `[16]`, `[13]`, `[11]`, `[9]`, `[16,13]`, `[13,11]`, `[11,9]`, `[16,13,11]`, `[13,11,9]`, `[16,13,11,9]`
- Longest valid subarray: `[16,13,11,9]` (length = **4**)

---

#### Test Case 5
##### Input:
```plaintext
nums = [1, 3, 5, 7, 9]
```
##### Output:
```plaintext
5
```
##### Explanation:
- Strictly increasing subarrays: `[1]`, `[3]`, `[5]`, `[7]`, `[9]`, `[1,3]`, `[3,5]`, `[5,7]`, `[7,9]`, `[1,3,5]`, `[3,5,7]`, `[5,7,9]`, `[1,3,5,7]`, `[3,5,7,9]`, `[1,3,5,7,9]`
- No decreasing subarrays exist.
- Longest valid subarray: `[1,3,5,7,9]` (length = **5**)


# Problem :   ` Maximum Ascending Order Subarray Sum`

Given an array of positive integers \`nums\`, find the maximum sum of an **ascending subarray**.

- A **subarray** is a contiguous sequence of numbers in the array.
- A subarray is **ascending** if each number is **strictly greater** than the previous one.
- A **single-element subarray** is also considered ascending.

Return the **maximum possible sum** among all ascending subarrays.

---

### Example 1
#### Input:
\`\`\`
nums = [5, 15, 25, 10, 20, 30]
\`\`\`
#### Output:
\`\`\`
60
\`\`\`
#### Explanation:
The subarray \`[10, 20, 30]\` has the maximum sum of \`50\`.

---

### Example 2
#### Input:
\`\`\`
nums = [3, 6, 9, 12]
\`\`\`
#### Output:
\`\`\`
30
\`\`\`
#### Explanation:
The entire array \`[3, 6, 9, 12]\` is ascending, with a sum of \`30\`.

---

### Example 3
#### Input:
\`\`\`
nums = [8, 7, 6, 5, 4]
\`\`\`
#### Output:
\`\`\`
8
\`\`\`
#### Explanation:
Each element is in descending order, so the maximum sum is the largest single element: \`8\`.

---

### Example 4
#### Input:
\`\`\`
nums = [2, 2, 2, 2]
\`\`\`
#### Output:
\`\`\`
2
\`\`\`
#### Explanation:
All elements are equal, so no two consecutive elements form an ascending sequence. The maximum sum is any single element: \`2\`.

---

### Constraints
- \`1 <= nums.length <= 100\`
- \`1 <= nums[i] <= 100\`

# Find the Punishment Number

### Description
Given a positive integer $ n $, return its **punishment number**.

The **punishment number** of $ n $ is the sum of squares of all numbers $ i $  (where $  $$1 \leq i \leq n $$ $) that satisfy:
- $ $$ i^2 $$ $ can be split into contiguous substrings,
- The sum of these substrings equals $ i $.

### Example 1

**Input:**
\`\`\`plaintext
n = 12
\`\`\`

**Output:**
\`\`\`plaintext
182
\`\`\`

**Explanation:**
Numbers satisfying the condition:
- $ $$1^2 = 1 $$$ ✅
- $$$ 9^2 = 81 \rightarrow 8 + 1 = 9 $$$ ✅
- $ $$10^2 = 100 \rightarrow 10 + 0 = 10 $$$ ✅

Total punishment number: $ 1 + 81 + 100  = 182 $

---

### Example 2

**Input:**
\`\`\`plaintext
n = 25
\`\`\`

**Output:**
\`\`\`plaintext
182
\`\`\`

**Explanation:**
Numbers satisfying the condition:

- $$$ 1^2 = 1$$ $ ✅
- $$$ 9^2 = 81 \rightarrow 8 + 1 = 9 $$$ ✅
- $$$ 10^2 = 100 \rightarrow 10 + 0 = 10$$ $ ✅

Total punishment number: $ 1 + 81 + 100 = 182 $

---

### Constraints
$$ 1 \leq n \leq 1000 $$


# Problem: Valid Parentheses
**Difficulty:** Easy  
**Topics:** Strings, Stack, Algorithms  
**Companies:** Relevant for interviews at top tech companies.

## Problem Description
You are given a string \`s\` containing only the characters '(', ')', '{', '}', '[', and ']'. Your task is to determine whether the input string is valid.

## Validity Criteria
A string is considered valid if:
- **Matching Brackets:** Open brackets are closed by the same type of brackets.
- **Correct Order:** Open brackets are closed in the correct order.
- **Balanced Brackets:** Every closing bracket has a corresponding open bracket of the same type.

## Input Format
A single string \`s\` consisting of the characters '(', ')', '{', '}', '[', and ']'.

## Constraints
- \`1 <= s.length <= 10⁴\`
- The string contains only the characters: '(', ')', '{', '}', '[', and ']'.

## Output Format
Return \`true\` if the input string is valid.  
Return \`false\` otherwise.

## Examples

### Example 1:
\`\`\`
Input:
s = "()"
Output:
true
\`\`\`

### Example 2:
\`\`\`
Input:
s = "()[]{}"
Output:
true
\`\`\`

### Example 3:
\`\`\`
Input:
s = "(]"
Output:
false
\`\`\`

### Example 4:
\`\`\`
Input:
s = "([])"
Output:
true
\`\`\`

## Hints
- Use a stack to keep track of open brackets.
- Traverse the string character by character:
  - Push open brackets onto the stack.
  - When encountering a closing bracket, check if the top of the stack matches its corresponding open bracket.
  - If the stack is empty at the end of traversal, the string is valid. Otherwise, it is invalid.


# Trapping Rain Water Problem  

## Problem Description  

Given an array `height` representing the height of blocks, calculate how much water can be trapped after rainfall. Water can only be trapped between blocks if there is a taller block on both the left and the right of the current block.  

---

### Objective  
Find the total amount of water that can be trapped between the blocks.  

---

## Key Insight  

For each block, the water it can trap is determined by:  
`min(leftMax, rightMax) - height[i]`  
Where:  
- `leftMax` is the maximum height of blocks to the **left** of the current block.  
- `rightMax` is the maximum height of blocks to the **right** of the current block.  

---

## Approach  

### 1. **Calculate Left Maximum Heights:**  
- Traverse the array of blocks from **left to right**.  
- Track the maximum height encountered so far for each block and store it in a new array `leftMax`.  

### 2. **Calculate Right Maximum Heights:**  
- Traverse the array of blocks from **right to left**.  
- Track the maximum height encountered so far for each block and store it in another array `rightMax`.  

### 3. **Calculate Water at Each Block:**  
- Traverse the array of blocks.  
- For each block:  
  - Compute the trapped water at index `i` as:  
    `water[i] = min(leftMax[i], rightMax[i]) - height[i]`  
  - Add this value to the total trapped water.  

### 4. **Return Total Water Trapped:**  
- After the traversal, return the sum of all trapped water.  

---

## Example  

### Input:  
`height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]`  

### Left Maximum Heights:  
`[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]`  

### Right Maximum Heights:  
`[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]`  

### Water Trapped at Each Block:  
`[0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]`  

### Total Trapped Water:  
`6`  

**Output:**  
`6`

---

## Test Cases  

#### Test Case 1  
**Input:**  
`height = [4, 2, 0, 3, 2, 5]`  

**Output:**  
`9`  

**Explanation:**  
Water trapped at each block: `[0, 2, 4, 1, 2, 0]`  
Total water trapped = `9`.  

---

#### Test Case 2  
**Input:**  
`height = [1, 0, 2]`  

**Output:**  
`1`  

**Explanation:**  
Water trapped at each block: `[0, 1, 0]`  
Total water trapped = `1`.  

---

#### Test Case 3  
**Input:**  
`height = [0, 1, 0, 1, 0]`  

**Output:**  
`0`  

**Explanation:**  
No water is trapped because no block has taller blocks on both sides.  

---

#### Test Case 4  
**Input:**  
`height = [3, 0, 0, 2, 0, 4]`  

**Output:**  
`10`  

**Explanation:**  
Water trapped at each block: `[0, 3, 3, 1, 3, 0]`  
Total water trapped = `10`.  

---

### Constraints  
1. `1 <= height.length <= 10^5`  
2. `0 <= height[i] <= 10^4`  

---

### Complexity  

#### Time Complexity:  
- **O(n):** Single pass for calculating `leftMax`, `rightMax`, and total water trapped.  

#### Space Complexity:  
- **O(n):** Space used for `leftMax` and `rightMax` arrays.  

For an optimized version, we can reduce space complexity to **O(1)** using two-pointer technique.


# Longest Substring Without Repeating Characters

### Problem Statement  
Given a string `s`, find the length of the longest substring without repeating characters.

---

### Approach

To solve this problem, we can use the **sliding window technique** along with a **dictionary** to keep track of the most recent index of each character.

---

### Steps

#### 1. **Initialize Variables**  
- **`last_position`** (dictionary): Stores the last seen index of each character.  
- **`max_length`** (integer): Tracks the length of the longest substring without repeating characters. Initialize it to `0`.  
- **`prev`** (integer): Marks the starting index of the current substring window. Initialize it to `0`.

---

#### 2. **Iterate Through the String**  
Use a for loop to iterate over the string with an index `i` and the current character `s[i]`.

1. **Check for Repeating Characters:**  
   - If `s[i]` is found in `last_position` and `last_position[s[i]] >= prev`:  
     - Update `prev` to `last_position[s[i]] + 1` to move the starting index of the window after the last occurrence of the character.

2. **Update the Window and Variables:**  
   - Update `last_position[s[i]]` to the current index `i`.  
   - Calculate the current substring length: `i - prev + 1`.  
   - Update `max_length` if the current substring length is greater.

---

#### 3. **Return the Result**  
After the loop, `max_length` contains the length of the longest substring without repeating characters.

---

### Example Input and Output

#### Example 1  
**Input:**  
`s = "abcabcbb"`

**Output:**  
`3`  

**Explanation:**  
The longest substring without repeating characters is `"abc"`, with a length of `3`.

---

#### Example 2  
**Input:**  
`s = "bbbbb"`

**Output:**  
`1`  

**Explanation:**  
The longest substring without repeating characters is `"b"`, with a length of `1`.

---

#### Example 3  
**Input:**  
`s = "pwwkew"`

**Output:**  
`3`  

**Explanation:**  
The longest substring without repeating characters is `"wke"`, with a length of `3`.

---

### Test Cases

#### Test Case 1  
**Input:**  
`s = "abcde"`

**Output:**  
`5`  

**Explanation:**  
All characters are unique, so the longest substring is the entire string.

#### Test Case 2  
**Input:**  
`s = ""`

**Output:**  
`0`  

**Explanation:**  
The string is empty, so the longest substring length is `0`.

#### Test Case 3  
**Input:**  
`s = "abba"`

**Output:**  
`2`  

**Explanation:**  
The longest substrings without repeating characters are `"ab"` or `"ba"`, both with a length of `2`.

---

### Constraints
1. `0 <= s.length <= 10^5`
2. `s` consists of English letters, digits, symbols, and spaces.


# Character Replacement to Match Strings  

**Problem Statement:**  
Given two strings `s` and `t` of the same length, determine whether it is possible to replace characters in `s` such that it becomes identical to `t`. Each character in `s` can be replaced with at most one unique character from `t`, and no two characters in `s` can map to the same character in `t`.

---

## Approach  

To solve this problem, we use two dictionaries (`dic1` and `dic2`) to map characters from `s` to `t` and `t` to `s` respectively. These mappings help ensure one-to-one correspondence between characters.

### Steps:  
1. **Initialize Variables:**  
   - Two dictionaries, `dic1` and `dic2`, to track mappings.  
   - A `flag` variable set to `1`, indicating success.  

2. **Iterate Through Both Strings Simultaneously:**  
   - For each character pair `(s[i], t[i])`:  
     - If `s[i]` is already in `dic1` and maps to a different character than `t[i]`, or if `t[i]` is in `dic2` and maps to a different character than `s[i]`, set `flag = 0` and break.  
     - Otherwise, add the mapping `s[i] -> t[i]` in `dic1` and `t[i] -> s[i]` in `dic2`.  

3. **Final Check:**  
   - If `flag` is still `1` after processing all characters, return `True`.  
   - Otherwise, return `False`.  

---

## Code Implementation  

```python
def canTransform(s, t):
    if len(s) != len(t):
        return False
    
    dic1 = {}
    dic2 = {}
    flag = 1
    
    for i in range(len(s)):
        if (s[i] in dic1 and dic1[s[i]] != t[i]) or (t[i] in dic2 and dic2[t[i]] != s[i]):
            flag = 0
            break
        dic1[s[i]] = t[i]
        dic2[t[i]] = s[i]
    
    return flag == 1
---

**Input:**  
`s = "abc", t = "def"`

**Execution:**  
- `dic1`: `{'a': 'd', 'b': 'e', 'c': 'f'}`  
- `dic2`: `{'d': 'a', 'e': 'b', 'f': 'c'}`  

**Output:**  
`True`

---

**Input:**  
`s = "foo", t = "bar"`

**Execution:**  
- Mapping `o -> a` is inconsistent.  

**Output:**  
`False`

---

**Input:**  
`s = "add", t = "egg"`

**Execution:**  
- `dic1`: `{'a': 'e', 'd': 'g'}`  
- `dic2`: `{'e': 'a', 'g': 'd'}`  

**Output:**  
`True`

---
**Input:**  
`s = "abc", t = "de"`

**Execution:**  
- Since the lengths are different, no transformation is possible.  

**Output:**  
`False`

---

**Input:**  
`s = "", t = ""`

**Execution:**  
- Both strings are empty, so they are trivially the same.  

**Output:**  
`True`



# Problem: Add Two Numbers Represented by Linked Lists

**Difficulty:** Medium  
**Topics:** Linked Lists, Mathematical Computation, Algorithm Design  
**Objective:** Add two non-negative integers represented by linked lists and return the result as a linked list.

---

## Problem Description

You are given two non-negative integers represented by two linked lists, where each node contains a single digit. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

### Example:

**Input:**  
`l1 = [2, 4, 3]`, `l2 = [5, 6, 4]`

**Output:**  
`[7, 0, 8]`

**Explanation:**  
342 + 465 = 807. The sum is returned as a linked list, where the digits are reversed.

---

## Code Explanation

### Step-by-Step Breakdown

The code defines a C++ class called `Solution` with a member function `addTwoNumbers`. The function adds two numbers represented by linked lists and returns the result as a new linked list.

### 1. **Initialization:**  
   - A dummy head node (`dummyHead`) is created to simplify list construction.  
   - A pointer (`l3`) is initialized to point to `dummyHead`.

### 2. **Addition Loop:**  
   - The loop continues as long as either of the linked lists has more digits or there's a carry left.  
   - For each iteration, the digits from `l1` and `l2` are extracted (or treated as 0 if the list is shorter).  
   - The sum is computed, and the carry is updated.

### 3. **Creating the Result List:**  
   - A new node with the current digit is created and appended to the result list.  
   - The pointer `l3` is moved forward, and `l1` and `l2` are also advanced to the next nodes.

### 4. **Final Result:**  
   - The result starts from the node following the dummy head.  
   - The dummy head is deleted, and the final result is returned.

---

## Test Cases

### Test Case 1: Standard Addition

**Input:**  
`l1 = [2, 4, 3]`, `l2 = [5, 6, 4]`

**Output:**  
`[7, 0, 8]`

**Explanation:**  
342 + 465 = 807, which is returned as a linked list: `[7, 0, 8]`.

---

### Test Case 2: Addition with Carry Over

**Input:**  
`l1 = [9, 9, 9]`, `l2 = [1, 1, 1]`

**Output:**  
`[0, 1, 1, 1]`

**Explanation:**  
999 + 111 = 1110, which is returned as a linked list: `[0, 1, 1, 1]`.

---

### Test Case 3: Unequal Length Lists

**Input:**  
`l1 = [1, 2]`, `l2 = [9, 9, 9]`

**Output:**  
`[0, 2, 0, 1]`

**Explanation:**  
12 + 999 = 1011, which is returned as a linked list: `[0, 2, 0, 1]`.

---

### Test Case 4: One List is Empty

**Input:**  
`l1 = []`, `l2 = [5, 6, 4]`

**Output:**  
`[5, 6, 4]`

**Explanation:**  
If one list is empty, the other list is returned as the result.

---

### Test Case 5: Both Lists are Empty

**Input:**  
`l1 = []`, `l2 = []`

**Output:**  
`[]`

**Explanation:**  
If both lists are empty, the result is an empty list.

---



# Number Container System

Design a system that stores numbers in "containers" (indexed slots) and supports two main operations:

1.**change(index, number)**:  
   Set the container at the specified index to the given number. If a container already has a number, replace it with the new number.

2. **find(number)**:  
   Return the smallest index that currently contains the specified number. If no container holds that number, return `-1`.

---

## How It Works
- **Initialization:**  
When the system is created, all containers are empty.
- **Updating a Container:**  
  When you call `change(index, number)`, the system stores `number` at that index. If the container already held a number, it is replaced.
- **Searching for a Number:**  
  When you call `find(number)`, the system searches for all containers containing that number and returns the smallest index among them. If none is found, it returns `-1`.


---

## Example Test Cases

### Example 1

**Input:**

`["NumberContainers", "change", "change", "find", "change", "find"] [[], [2, 10], [5, 10], [10], [2, 20], [10]]`

**Expected Output:**

`[null, null, null, 2, null, 5]`


**Step-by-Step Explanation:**

1. **Initialization:**  
   - Create a new NumberContainers instance.
   
2. **Operation: `change(2, 10)`**  
   - Set the container at index **2** to **10**.
   
3. **Operation: `change(5, 10)`**  
   - Set the container at index **5** to **10**.
   
4. **Operation: `find(10)`**  
   - Check all containers for the number **10**.
   - Containers **2** and **5** contain **10**.
   - The smallest index among these is **2**.
   - **Output:** `2`
   
5. **Operation: `change(2, 20)`**  
   - Update the container at index **2** to **20**.
   - Now, container **2** no longer holds **10**.
   
6. **Operation: `find(10)`**  
   - Check all containers for the number **10**.
   - Only container **5** now holds **10**.
   - **Output:** `5`

---

## Alternative Example 2

**Input:**

["NumberContainers", "change", "find", "change", "change", "find", "change", "find", "find"] [[], [3, 15], [15], [7, 15], [3, 20], [15], [7, 30], [15], [20]]


**Expected Output:**

[null, null, 3, null, null, 7, null, -1, 3]


**Step-by-Step Explanation:**

1. **Initialization:**  
   - Create a new NumberContainers instance.
   
2. **Operation: `change(3, 15)`**  
   - Set the container at index **3** to **15**.
   
3. **Operation: `find(15)`**  
   - Check all containers for the number **15**.
   - Container **3** contains **15**.
   - **Output:** `3`
   
4. **Operation: `change(7, 15)`**  
   - Set the container at index **7** to **15**.
   - Now, containers **3** and **7** both have **15**.
   
5. **Operation: `change(3, 20)`**  
   - Update the container at index **3** to **20**.
   - Container **3** no longer holds **15**; only container **7** holds **15**.
   
6. **Operation: `find(15)`**  
   - Check all containers for the number **15**.
   - Only container **7** contains **15**.
   - **Output:** `7`
   
7. **Operation: `change(7, 30)`**  
   - Update the container at index **7** to **30**.
   - Container **7** no longer holds **15**.
   
8. **Operation: `find(15)`**  
   - Check all containers for the number **15**.
   - No container holds **15**.
   - **Output:** `-1`
   
9. **Operation: `find(20)`**  
   - Check all containers for the number **20**.
   - Container **3** holds **20**.
   - **Output:** `3`

---

## Constraints

- `1 <= index, number <= 10^9`
- There will be at most `10^5` calls combined to the `change` and `find` operations.

---


Select a card whose code you want to track