# Dijkstra’s Algorithm `(Shortest Path)`

Dijkstra’s algorithm is a classic method for finding the shortest path from a starting node to every other node in a **weighted graph** (with non-negative edge weights).

## How It Works

1. **Initialization**  
   - **Distance Map:** Create an object `dist` where every node’s distance is set to infinity (`∞`), except the start node which is set to 0.  
   - **Priority Queue:** Use a priority queue (or min-heap) to store nodes ordered by their current shortest distance.  
   - **Previous Map:** Optionally, maintain a `previous` map to keep track of the best preceding node for each node (useful for reconstructing the shortest path).
2. **Main Loop**  
   While the priority queue is not empty:
   - **Extract Minimum:** Remove the node `u` with the smallest distance from the queue.
   - **Relaxation:** For each neighbour `v` of `u`:
     - Compute an alternative distance:  
       `alt = dist[u] + weight(u, v)`
     - If `alt` is less than `dist[v]`:
       - Update `dist[v]` to `alt`.
       - Set `previous[v]` to `u`.
       - Add or update `v` in the priority queue with the new distance.
3. **Result Extraction**  
   - After processing, the `dist` object contains the shortest distances from the start node to every other node.
   - To **reconstruct the shortest path** from the start node to a target node, backtrack using the `previous` map.


## Example Graph

Consider the following graph:
![dijkstra](https://res.cloudinary.com/dluehhlfs/image/upload/v1739005736/dijkistra_trdfci.png)

- **Edges:**
  - A → B (weight = 1)
  - A → C (weight = 4)
  - B → C (weight = 2)
  - B → D (weight = 5)
  - C → D (weight = 1)

**Goal:** Find the shortest path from node `A` to node `D`.

### Step-by-Step Execution

1. **Initialization:**  
   - `dist = { A: 0, B: ∞, C: ∞, D: ∞ }`  
   - `previous = {}`  
   - Priority Queue: `[(A, 0)]`
2. **Processing Node A:**  
   - Dequeue **A** (distance = 0).  
   - For neighbour **B**:  
     - `alt = 0 + 1 = 1` → Update `dist[B] = 1`, `previous[B] = A`.  
   - For neighbour **C**:  
     - `alt = 0 + 4 = 4` → Update `dist[C] = 4`, `previous[C] = A`.  
   - Queue becomes: `[(B, 1), (C, 4)]`.
3. **Processing Node B:**  
   - Dequeue **B** (distance = 1).  
   - For neighbour **C**:  
     - `alt = 1 + 2 = 3` → Update `dist[C] = 3`, `previous[C] = B`.  
   - For neighbour **D**:  
     - `alt = 1 + 5 = 6` → Update `dist[D] = 6`, `previous[D] = B`.  
   - Queue becomes: `[(C, 3), (C, 4), (D, 6)]`  
     *(Duplicates in the queue are handled appropriately in a proper priority queue implementation.)*
4. **Processing Node C:**  
   - Dequeue **C** (distance = 3).  
   - For neighbour **D**:  
     - `alt = 3 + 1 = 4` → Update `dist[D] = 4`, `previous[D] = C`.  
   - Queue becomes: `[(D, 4), (D, 6)]`.
5. **Processing Node D:**  
   - Dequeue **D** (distance = 4).  
   - **D** has no neighbours needing updates.  
   - The queue is now empty.
6. **Reconstructing the Shortest Path from A to D:**  
   - Start at **D**: `previous[D] = C`  
   - Then **C**: `previous[C] = B`  
   - Then **B**: `previous[B] = A`  
   - **Path:** A → B → C → D with a total distance of **4**.



Saurabh Patil

# Bellman-Ford Algorithm

The **Bellman-Ford Algorithm** is a graph algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph. It is particularly useful when the graph contains negative weight edges.

## Algorithm Steps

1. **Initialize distances**:  
   - Set the distance to the source vertex as `0` and all other vertices as `∞` (infinity).
2. **Relax edges (V - 1) times**:  
   - Iterate over all edges and update the distance to each vertex if a shorter path is found.
3. **Check for negative-weight cycles**:  
   - Run one more iteration over all edges.  
   - If any distance can still be reduced, the graph contains a negative-weight cycle.

## Complexity Analysis

### Time Complexity:
- The algorithm runs **(V - 1) iterations**, where each iteration processes **E edges**.
- This results in a time complexity of **O(VE)**, making it slower than Dijkstra's algorithm for dense graphs.

### Space Complexity:
- The algorithm requires an array to store distances, leading to a space complexity of **O(V)**.

## Applications

### Detecting Negative-Weight Cycles  
The Bellman-Ford algorithm can detect **negative-weight cycles**, which are cycles in a graph where the sum of edge weights is negative. If such a cycle exists, the algorithm reports it, preventing incorrect shortest path calculations.

### Shortest Path Calculation  
Bellman-Ford is useful for **finding the shortest path** in graphs that contain negative-weight edges, unlike Dijkstra’s algorithm, which fails with negative weights.

### Routing Protocols  
The algorithm is used in **network routing protocols** such as **RIP (Routing Information Protocol)** to find the shortest paths in a network.

## Example Graph

Consider the following weighted directed graph:
     &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  ![graph diagram](https://res.cloudinary.com/dluehhlfs/image/upload/v1739028568/bellmanford_qsl13l.png)



 &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp; A `--(4)-->` B
 &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp; A `--(1)-->` C
 &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp; B `--(-2)-->` C
 &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp;  &nbsp; &nbsp; C `--(2)-->` D

If `A` is the source vertex, the Bellman-Ford algorithm computes the shortest paths from `A` to all other vertices, considering both positive and negative edge weights.

OUTPUT:
Shortest distances from source 0:
To vertex 0 is 0
To vertex 1 is 6
To vertex 2 is 7
To vertex 3 is 2
To vertex 4 is 4

# Floyd‑Warshall Algorithm

The **Floyd‑Warshall algorithm** is a dynamic programming approach used to find the shortest paths between `all pairs` of vertices in a weighted graph. It works for graphs with both positive and negative edge weights (provided there are no negative weight cycles) and has a time complexity of $$   \ (O(V^3) $$

---

## How It Works

The algorithm maintains a 2D array `dist` where:

- $ `dist[i][j]` $ represents the shortest distance from vertex $i$ to vertex $j$.

Initially, `dist[i][j]` is set to the weight of the edge from $i$ to $j$ if such an edge exists; otherwise, it is set to infinity (often denoted by $$ \infty$$) . The diagonal elements are zero since the distance from any vertex to itself is zero.

For each vertex $k$ (considered as an intermediate vertex), the algorithm updates the distance between every pair of vertices $i$ and $j$ using the recurrence relation:

$$
\text{dist}[i][j] = \min \Big( \text{dist}[i][j],\; \text{dist}[i][k] + \text{dist}[k][j] \Big)
$$

---

### Example

Consider a graph with 4 vertices (0, 1, 2, 3) and the following initial distance matrix:

**Initial dist:**

$$
\begin{bmatrix}
0 & 5 & \infty & 10 \\
\infty & 0 & 3 & \infty \\
\infty & \infty & 0 & 1 \\
\infty & \infty & \infty & 0 \\
\end{bmatrix}
$$

There is an edge from **0** to **1** with weight **5**.  
There is an edge from **0** to **3** with weight **10**.  
There is an edge from **1** to **2** with weight **3**.  
There is an edge from **2** to **3** with weight **1**.

---

#### Step-by-Step Updates

**For $k = 0$:**  
Consider paths going through vertex **0**.  
No update occurs because vertex **0** is the source for its outgoing edges.

---

**For $k = 1$:**  
Consider paths via vertex **1**.

- **Update:**  
  Update ($$ \text{dist}[0][2] $$) using the path $$  0 \rightarrow 1 \rightarrow 2\  $$:  
  $$\text{dist}[0][2] = \min(\infty,\, 5 + 3) = 8.$$
- **Updated Matrix:**

$$
\begin{bmatrix}
0 & 5 & 8 & 10 \\
\infty & 0 & 3 & \infty \\
\infty & \infty & 0 & 1 \\
\infty & \infty & \infty & 0 \\
\end{bmatrix}
$$

---

**For $k = 2$:**  
Consider paths via vertex **2**.
- **Update:**  
Update $ \text{dist}[0][3] $ using the path $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$:  
  $$\text{dist}[0][3] = \min(10,\, 8 + 1) = 9.$$
- **Updated Matrix:**

$$
\begin{bmatrix}
0 & 5 & 8 & 9 \\
\infty & 0 & 3 & \infty \\
\infty & \infty & 0 & 1 \\
\infty & \infty & \infty & 0 \\
\end{bmatrix}
$$

---

**For $k = 3$:**  
Consider paths via vertex **3**.  
No further improvements are possible.

---

#### Final Result

The final shortest path distance matrix is:

$$
\text{dist} =
\begin{bmatrix}
0 & 5 & 8 & 9 \\
\infty & 0 & 3 & \infty \\
\infty & \infty & 0 & 1 \\
\infty & \infty & \infty & 0 \\
\end{bmatrix}
$$

This matrix tells us, for example, that the shortest distance from vertex **0** to vertex **3** is **9**.

---

#### Summary

The Floyd‑Warshall algorithm efficiently computes the shortest paths between every pair of vertices by iteratively considering each vertex as an intermediate point. It is particularly useful for dense graphs or when multiple shortest path queries are needed.


# Prim’s Algorithm (Minimum Spanning Tree)

Prim’s algorithm is a `greedy` method for finding a **Minimum Spanning Tree (MST)** in a weighted, undirected graph. An `MST` is a subset of the graph’s edges that connects all vertices together without any cycles and with the minimum possible total edge weight.

---

## How It Works

1. **Initialization:**  
   - Start from an arbitrary vertex and mark it as part of the MST.
   - Maintain two sets of vertices: one included in the MST and the other not yet included.
2. **Selection of Edge:**  
   - At each step, look for the smallest weighted edge that connects a vertex in the MST to a vertex outside the MST.
   - Add both the edge and the connected vertex to the MST.
3. **Repeat:**  
   - Continue this process until all vertices are included in the MST.

The algorithm always picks the next minimum edge that expands the growing tree, ensuring that the total weight remains as low as possible.

---

## Example
![prims graph](https://res.cloudinary.com/dluehhlfs/image/upload/v1739115323/primsalgo_pbqdjw.png)
Consider a graph with 5 vertices labeled **A**, **B**, **C**, **D**, and **E** with the following weighted edges:

- **Edge (A, B)** with weight **2**
- **Edge (A, C)** with weight **3**
- **Edge (B, C)** with weight **1**
- **Edge (B, D)** with weight **4**
- **Edge (C, D)** with weight **5**
- **Edge (C, E)** with weight **6**
- **Edge (D, E)** with weight **7**

**Step-by-Step Process:**
1. **Start at Vertex A:**  
   - **MST Set:** {A}  
   - Outgoing edges from A:  
     - (A, B): weight 2  
     - (A, C): weight 3  
   - **Choose:** (A, B) because 2 is the minimum.  
   - **MST now contains:** A, B and edge (A, B).
2. **Expand the MST (Now contains A, B):**  
   - Look at edges from A and B to vertices not yet in the MST:  
     - From A: (A, C) with weight 3  
     - From B: (B, C) with weight 1 and (B, D) with weight 4  
   - **Choose:** (B, C) with weight 1.  
   - **MST now contains:** A, B, C and edges (A, B), (B, C).
3. **Continue Expanding (MST now: A, B, C):**  
   - Consider edges from the current MST to outside vertices:  
     - From B: (B, D) with weight 4  
     - From C: (C, D) with weight 5 and (C, E) with weight 6  
   - **Choose:** (B, D) with weight 4.  
   - **MST now contains:** A, B, C, D and edges (A, B), (B, C), (B, D).
4. **Final Expansion (MST now: A, B, C, D):**  
   - The only vertex left is **E**.  
   - Consider edges connecting to E:  
     - From C: (C, E) with weight 6  
     - From D: (D, E) with weight 7  
   - **Choose:** (C, E) with weight 6.  
   - **MST now contains:** A, B, C, D, E and edges (A, B), (B, C), (B, D), (C, E).

**Final MST:**  
- **Edges:** (A, B): 2, (B, C): 1, (B, D): 4, (C, E): 6  
- **Total Weight:** $2 + 1 + 4 + 6 = 13$

---

## Summary

Prim’s Algorithm builds a minimum spanning tree by starting from an arbitrary vertex and, at each step, adding the least expensive edge that connects a vertex in the tree to a vertex outside it. This process continues until all vertices are included in the tree, ensuring the total edge weight is minimized.



# Kruskal’s Algorithm (Minimum Spanning Tree)

Kruskal’s Algorithm is a **greedy algorithm** used to construct a Minimum Spanning Tree (MST) from a weighted, undirected graph. The goal of the MST is to connect all vertices with the minimum total edge weight, without forming any cycles.

---

## How It Works

1. **Sort All Edges:**  
   Begin by sorting all the edges in the graph in **non-decreasing order** by their weights.
2. **Initialize MST:**  
   Start with an empty set that will eventually become your MST. Each vertex is initially in its own separate tree.
3. **Edge Selection:**  
   Iterate over the sorted edges and, for each edge, check if including it in the MST would create a cycle.  
   - **Cycle Detection:**  
     This is typically done using a **`Union-Find `(Disjoint Set Union)** data structure.  
     - If the two endpoints of the edge belong to different sets, the edge can be safely added to the MST, and the sets are merged.  
     - If the endpoints are in the same set, adding the edge would form a cycle, so it is skipped.
4. **Repeat Until Completion:**  
   Continue adding edges until the MST contains exactly $V - 1$ edges, where $V$ is the number of vertices in the graph.

---

## Example

Consider a graph with 5 vertices labeled **A**, **B**, **C**, **D**, and **E** and the following weighted edges:
![kruskals algorithm graph image](https://res.cloudinary.com/dluehhlfs/image/upload/v1739193282/kruskals_ldot6h.png)
- **Edge `(A, B)`** with weight **2**
- **Edge `(A, C)`** with weight **3**
- **Edge `(B, C)`** with weight **1**
- **Edge `(B, D)`** with weight **4**
- **Edge `(C, D)`** with weight **5**
- **Edge `(C, E)`** with weight **6**
- **Edge `(D, E)`** with weight **7**

**Step-by-Step Process:**

1. **Sort the Edges:**  
   Sorted by weight (lowest to highest):  
   \[
   \{ 
 &nbsp; `(B, C)`: 1\,
  &nbsp; `(A, B)`: 2\,
   &nbsp; `(A, C)`: 3\,
 &nbsp; `(B, D)`: 4\,
  &nbsp; `(C, D)`: 5\,
 &nbsp; `(C, E)`: 6\,
 &nbsp; `(D, E)`: 7
 \}
   \]
2. **Initialize MST:**  
   Start with an empty MST. Each vertex $A, B, C, D, E$ is in its own component.
3. **Process Each Edge:**
   - **Edge `(B, C)` (weight 1):**  
     Vertices **B** and **C** are in different components. Include this edge.
   - **Edge `(A, B)` (weight 2):**  
     Vertices **A** and **B** are in different components. Include this edge.
   - **Edge `(A, C)` (weight 3):**  
     Now **A**, **B**, and **C** are already connected. Including (A, C) would form a cycle, so skip it.
   - **Edge `(B, D)` (weight 4):**  
     Vertex **D** is not yet connected to the MST containing **A, B, C**. Include this edge.
   - **Edge `(C, D)` (weight 5):**  
     Both **C** and **D** are already connected. Skip to avoid cycle.
   - **Edge `(C, E)` (weight 6):**  
     Vertex **E** is not connected. Include this edge.
   - **Edge `(D, E)` (weight 7):**  
     Both **D** and **E** are now connected in the MST; skip it.
4. **MST Formed:**  
   The MST consists of the edges:  
   - `(B, C)`: 1  
   - `(A, B)`: 2  
   - `(B, D)`: 4  
   - `(C, E)`: 6  
   **Total Weight:** $1 + 2 + 4 + 6 = 13$

---

## Summary

Kruskal’s Algorithm constructs the Minimum Spanning Tree by:
- Sorting all edges by weight.
- Iteratively adding the smallest edge that does not form a cycle.
- Using a Union-Find structure to efficiently check for cycles.

This greedy approach guarantees that the final tree spans all vertices with the minimum possible total weight.
## Complexity

- **Time Complexity:**  
$$
O(E \log E) \quad (\text{approximately } O(E \log V))
$$  
(Sorting the edges dominates; union-find operations are nearly constant time.)

- **Space Complexity:**  
$$
O(V + E)
$$  
(Space is used to store the edge list and the union-find structure.)



# Job Sequencing Problem

## Problem Description  

In this problem, we are given a set of `n` jobs. Each job has the following parameters:  
1. **ID**: Unique identifier for the job.  
2. **Deadline**: The time by which the job must be completed.  
3. **Profit**: The profit associated with completing the job.  

### **Goal**  
Determine the optimal sequence of jobs that maximizes the profit while ensuring that no two jobs are executed simultaneously and each job is completed within its deadline.

---

## Steps to Solve the Problem  

### 1. **Sort Jobs by Profit (Descending Order):**  
Sort the jobs in descending order based on their profits. This ensures that the most profitable jobs are considered first.

---

### 2. **Find the Maximum Deadline:**  
Find the maximum deadline among all jobs. This determines the number of time slots available.

---

### 3. **Initialize Variables:**  
- **`slots`**: An array of size `maxDeadline` initialized with `-1`. This array tracks which job is assigned to each time slot.  
- **`maxProfit`**: Initialize to `0` to track the maximum profit achieved.  
- **`count`**: Initialize to `0` to count the number of jobs included in the optimal sequence.

---

### 4. **Iterate Over Jobs:**  
For each job in the sorted list:  
- Check if there is an available time slot before the job's deadline.  
- If an available slot is found:  
  - Assign the job to that slot.  
  - Increment the job count.  
  - Add the job's profit to `maxProfit`.

---

### 5. **Return Results:**  
After iterating through all jobs, return:  
- **`count`**: Total number of jobs included in the sequence.  
- **`maxProfit`**: Maximum profit achieved.

---

## Example  

### Input:  
`jobs = [ {id: 1, deadline: 2, profit: 100}, {id: 2, deadline: 1, profit: 19}, {id: 3, deadline: 2, profit: 27}, {id: 4, deadline: 1, profit: 25}, {id: 5, deadline: 3, profit: 15} ]`

### Steps:  
1. **Sort Jobs by Profit:**  
   Sorted jobs:  
   `[ {id: 1, profit: 100}, {id: 4, profit: 25}, {id: 3, profit: 27}, {id: 2, profit: 19}, {id: 5, profit: 15} ]`
2. **Maximum Deadline:**  
   Maximum deadline = `3`  
3. **Assign Jobs to Slots:**  
   - Job 1: Assigned to slot 2.  
   - Job 3: Assigned to slot 1.  
   - Job 5: Assigned to slot 3.  

### Output:  
**`count = 3`** (Jobs 1, 3, and 5)  
**`maxProfit = 142`**

---

## Test Cases  

#### Test Case 1  
**Input:**  
`jobs = [ {id: 1, deadline: 2, profit: 50}, {id: 2, deadline: 1, profit: 40}, {id: 3, deadline: 2, profit: 60}, {id: 4, deadline: 1, profit: 20} ]`

**Output:**  
`count = 2` (Jobs 3 and 1)  
`maxProfit = 110`

---

#### Test Case 2  
**Input:**  
`jobs = [ {id: 1, deadline: 1, profit: 10}, {id: 2, deadline: 2, profit: 20}, {id: 3, deadline: 3, profit: 30} ]`

**Output:**  
`count = 3` (Jobs 3, 2, and 1)  
`maxProfit = 60`

---

#### Test Case 3  
**Input:**  
`jobs = [ {id: 1, deadline: 3, profit: 20}, {id: 2, deadline: 3, profit: 15}, {id: 3, deadline: 1, profit: 10} ]`

**Output:**  
`count = 2` (Jobs 1 and 3)  
`maxProfit = 30`

---

### Constraints  
1. `1 <= n <= 1000`  
2. `1 <= profit[i], deadline[i] <= 10^4`  

---

### Complexity  

#### Time Complexity:  
- Sorting: **O(n log n)**  
- Assigning Jobs to Slots: **O(n * d)** (where `d` is the maximum deadline)  

#### Space Complexity:  
- **O(d)** for the slots array.


# Constructing Pascal's Triangle

### Problem Description
Pascal's Triangle is a triangular array of numbers where:
1. The first and last elements of each row are `1`.
2. Each intermediate element is the sum of the two numbers directly above it.

Given an integer `numRows`, construct Pascal's Triangle as a 2D array with exactly `numRows` rows. Each row should only contain the elements that belong to the triangle (no trailing zeros).

---

### Objective  
To construct a 2-dimensional array that represents Pascal's Triangle.

---

### Steps

#### 1. **Initialize the 2D Array**  
- Create a 2-dimensional array `pascalTriangle` of size `numRows x numRows` initialized with 0s.

#### 2. **Declare and Initialize Variables**  
- Declare a variable `cols` and initialize it to 0. This variable will keep track of the number of columns in the current row.

#### 3. **Construct Pascal's Triangle**  
- Use a **for loop** to iterate through each row (variable `i` from 0 to `numRows - 1`):
  - Increment `cols` by 1 for each new row.
  - Use a **nested for loop** to iterate through each column in the current row (variable `j` from 0 to `cols - 1`):
    - If `j` is 0 or `j` is `cols - 1`, assign the value `1` to `pascalTriangle[i][j]`. This handles the edges of the triangle.
    - Otherwise, set `pascalTriangle[i][j]` to the sum of the two numbers directly above it in the triangle (`pascalTriangle[i-1][j-1]` and `pascalTriangle[i-1][j]`).

#### 4. **Remove Extra Zeros**  
- After constructing the triangle, remove all trailing zeros from each row to ensure the triangle has the correct shape.

---

### Example Input and Output

#### Example 1
**Input:**  
`numRows = 5`

**Output:**  
```json
[
  [1],
  [1, 1],
  [1, 2, 1],
  [1, 3, 3, 1],
  [1, 4, 6, 4, 1]
]

# Maximum Profit from Stock Trading

**Objective:**  
To determine the maximum profit that can be achieved from buying and selling stock on given days, where the price of the stock is provided as an array.

---

### Steps:

#### 1. **Initialize Variables:**

- **maxProfit:** This variable will store the maximum profit encountered so far.
- **minSoFar:** This variable represents the minimum stock price encountered up to the current day. Initialize it to the stock price on the first day.

---

#### 2. **Iterate Through the Array:**

- Use a **for loop** to iterate through the array of stock prices.
  - For each day, calculate the potential profit by subtracting `minSoFar` from the current stock price.
  - If this potential profit is greater than the current `maxProfit`, update `maxProfit` with the new potential profit.
  
  Additionally, update `minSoFar` to be the minimum of its current value and the current stock price. This ensures that you always have the lowest price encountered up to the current day.

---

#### 3. **Return the Result:**

- After iterating through the entire array, the final value of `maxProfit` will hold the maximum profit achievable by buying and selling the stock.

---

### Test Cases:

#### Test Case 1:  
**Input:**  
`prices = [7, 1, 5, 3, 6, 4]`

**Output:**  
Maximum Profit = **5**  
Explanation:  
- Buy on day 2 (price = 1), sell on day 5 (price = 6), profit = 6 - 1 = 5.

---

#### Test Case 2:  
**Input:**  
`prices = [7, 6, 4, 3, 1]`

**Output:**  
Maximum Profit = **0**  
Explanation:  
- No transaction is made as prices are decreasing. No profit can be achieved.

---

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

**Output:**  
Maximum Profit = **4**  
Explanation:  
- Buy on day 1 (price = 1), sell on day 5 (price = 5), profit = 5 - 1 = 4.

---

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

**Output:**  
Maximum Profit = **4**  
Explanation:  
- Buy on day 2 (price = 2), sell on day 3 (price = 6), profit = 6 - 2 = 4.

---

### Code Example:

```python
def maxProfit(prices):
    maxProfit = 0
    minSoFar = prices[0]
    
    for price in prices:
        maxProfit = max(maxProfit, price - minSoFar)
        minSoFar = min(minSoFar, price)
    
    return maxProfit


# N-Queens problem
In this problem, we are solving the N-Queens problem where the goal is to place N queens on an N×N chessboard so that no two queens can attack each other. The steps to solve this problem are as follows:

### Define Utility Function isSafe1:

This function checks if placing a queen at a given position (row, col) is safe.
It verifies three directions for conflicts with other queens:
Upper diagonal on the left side.
Left side.
Lower diagonal on the left side.
If any of these directions have a queen, it returns false. Otherwise, it returns true.
Define Recursive Function solve:

This function attempts to place queens column by column.
If the current column (col) is equal to the board size (n), it indicates all queens are placed successfully, and the current board configuration is added to the answer list (ans).
For each row in the current column, it checks if placing a queen is safe using the isSafe1 function.
If safe, it places a queen at board[row][col], recursively calls solve for the next column, and then removes the queen to backtrack.

## Main Function solveNQueens:

This function initializes the board and calls the solve function.
It creates an empty board with all positions set to '.', indicating no queens are placed.
It calls the solve function starting from the first column.
Finally, it returns the list of all valid board configurations.
Detailed Steps:

## Utility Function isSafe1:

### Check Upper Diagonal:
Move upwards diagonally (row--, col--) and check for any queen.
Check Left Side:
Move left horizontally (col--) and check for any queen.
Check Lower Diagonal:
Move downwards diagonally (row++, col--) and check for any queen.
Return true if no conflicts are found in the above directions.
Recursive Function solve:

### Base Condition:
If col equals n, all queens are placed correctly. Add the current board configuration to ans and return.
Recursive Case:
For each row in the current column, check if placing a queen is safe using isSafe1.
If safe, place the queen, call solve recursively for the next column, and backtrack by removing the queen.
Main Function solveNQueens:

## Initialize the board with '.'.
Call solve starting from the first column (0).
Return the list of all valid configurations.

# 3264. Final Array State After K Multiplication Operations I

**Difficulty**: Easy  
**Topics**: Arrays  

---

## Problem Description

You are given an integer array `nums`, an integer `k`, and an integer `multiplier`.

You need to perform `k` operations on `nums`. In each operation:
1. Find the minimum value `x` in `nums`. If there are multiple occurrences of the minimum value, select the one that appears first.
2. Replace the selected minimum value `x` with `x * multiplier`.

Return an integer array denoting the final state of `nums` after performing all `k` operations.

---

## Examples

### Example 1

**Input**:  
`nums = [2,1,3,5,6], k = 5, multiplier = 2`  

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

**Explanation**:

| Operation | Result                |
|:-----------:|:-----------------------:|
| After 1   | `[2, 2, 3, 5, 6]`    |
| After 2   | `[4, 2, 3, 5, 6]`    |
| After 3   | `[4, 4, 3, 5, 6]`    |
| After 4   | `[4, 4, 6, 5, 6]`    |
| After 5   | `[8, 4, 6, 5, 6]`    |

---

### Example 2

**Input**:  
`nums = [1,2], k = 3, multiplier = 4`  

**Output**:  
`[16,8]`  

**Explanation**:

| Operation | Result        |
|:---:|:---:|
| After 1   | `[4, 2]`      |
| After 2   | `[4, 8]`      |
| After 3   | `[16, 8]`     |

---

## Constraints

$$
1 \leq \text{nums.length} \leq 100
$$

$$
1 \leq \text{nums}[i] \leq 100
$$

$$
1 \leq k \leq 10
$$

$$
1 \leq \text{multiplier} \leq 5
$$


# Problelm: Construct String With Repeat Limit

### Difficulty  ```Medium```  

### Description

You are given:
- A string `s` consisting of lowercase English letters.
- An integer `repeatLimit`.

Your task is to construct a new string `repeatLimitedString` using the characters of `s`, **such that no letter appears more than `repeatLimit` times consecutively**.

The goal is to return the **lexicographically largest string** possible.

---

### Definitions:
- **Lexicographically larger**: 
   - Compare strings by characters one by one from left to right.
   - A string `a` is larger than string `b` if:
     - At the first differing position, `a` has a character later in the alphabet.
     - If all characters match up to the shorter string, the longer string is larger.
---
### Examples
#### Example 1:
**Input**:  
```  
s = "cczazcc"
repeatLimit = 3
```
Output:
```
"bbabaa"
```
#### Explanation:

- **Steps**:  
  1. **Sort the characters** in `s` in descending order to maximize the lexicographical order:  
Sorted characters: z, z, c, c, c, c, a
  2. Start constructing the output string while ensuring no letter appears more than `repeatLimit` times consecutively.  
  3. Add the letters in the following way:  
     - Add `'z'` → appears **2 times**.  
     - Add `'c'` → appears **3 times**.  
     - Add `'a'` → appears **1 time**.  
     - Add remaining `'c'` → **1 time** (to avoid breaking the `repeatLimit` rule).  
  4. Final string:  
            "zzcccac"

  ## **Validation**:  
     - `'z'` appears at most **2 times** consecutively.  
     - `'c'` appears at most **3 times** consecutively.  
     - `'a'` appears only **1 time**.  

The string `"zzcccac"` satisfies all conditions and is **lexicographically largest**.




#### Example 2:
**Input**:  
```  
s = "aaabbccc"       repeatLimit = 2
```
Output:
```
"ccbbaacc"
```

#  Count Vowel Strings in Ranges
###  Problem Description:
You are given:
1. **An array of strings `words`**: These are lowercase English words.
2. **A list of queries `queries`**: Each query is a range `[li, ri]`.

**Task**:  
For each query `[li, ri]`, count how many words in the range (from index `li` to `ri`, inclusive) **start and end with a vowel**.

#### What are vowels?
The vowels are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`.

#### Output:
Return an array `ans` where:
- `ans[i]` is the answer to the `i-th` query.

---

### Example 1:

**Input**:  `words = ["aba", "bcb", "ece", "aa", "e"],  `&nbsp;` `&nbsp;` `&nbsp;` `&nbsp;` `&nbsp;`    queries = [[0, 2], [1, 4], [1, 1]]`  
**Output**: `[2, 3, 0]`

### Explanation:

Words starting and ending with vowels:  
`"aba"`, `"ece"`, `"aa"`, `"e"`.

#### Query Results:



   -  **For   `[0, 2]`**:  
          The range contains `"aba"` and `"ece"`, so the result is `2`.
   -  **For   `[1, 4]`**:  
          The range contains `"ece"`, `"aa"`, `"e"`, so the result is `3`.
   -  **For   `[1, 1]`**:  
          No word in this range satisfies the condition, so the result is `0`.


### Example 2:

**Input**:  `words = ["a","e","i"],  `&nbsp;` `&nbsp;` `&nbsp;` `&nbsp;` `&nbsp;` `&nbsp;`     
       `&nbsp;`   `&nbsp;` `&nbsp;` `&nbsp;` `&nbsp;` queries = [[0,2],[0,1],[2,2]]`

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

### Explanation:

All words start and end with vowels.

#### Query Results:

   - **For `[0, 2]`**:  
          All words in this range (`"a"`, `"e"`, `"i"`) satisfy the condition, so the result is `3`.
   - **For `[0, 1]`**:  
  The range contains `"a"` and `"e"`, so the result is `2`.
- **For `[2, 2]`**:  
  The range contains `"i"`, so the result is `1`.

### Constraints:

- **Number of words (`words.length`)**: Up to $$10^5$$.
- **Length of a single word (`words[i].length`)**: Up to $$40$$.
- **Total characters in all words combined**: Up to $$3 \times 10^5$$.
- **Number of queries (`queries.length`)**: Up to $$10^5$$.
- **Query range**: Always valid, i.e., $$0 \leq l_i \leq r_i < \text{words.length}$$.


# Problem: Minimum Number of Operations to Move All Balls to Each Box

You have **n boxes** represented as a binary string `boxes`, where:
- `'0'` means the box is empty.
- `'1'` means the box contains one ball.

You can move a ball from one box to an adjacent box in **one operation**. A box is adjacent if the difference in their indices is **1**.

You need to calculate an array `answer` of size `n` where:
- `answer[i]` is the **minimum number of operations** required to move all balls to the **ith box**, considering the initial positions of the balls.

---

### Examples

#### Example 1:
**Input:**  
`boxes = "110"`  
**Output:**  
`[1, 1, 3]`  


![Boxes](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746458/ball_box2_tcmoq6.png)
#### The number of operations required to move `all balls` to the `0th` index box from the initial state  = `1`.
![Boxes](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746458/ball_box3_lqqc2v.png)
#### The number of operations required to move `all balls` to the `1st` index box from the initial state  = `1`.
![Boxes](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746458/ball_box4_iyvew5.png)

#### The number of operations required to move `all balls` to the `3rd` index box from the initial state  = `2`.

![Boxes](https://res.cloudinary.com/dluehhlfs/image/upload/v1737746458/ball_box5_lpptli.png)

#### The `total number` of operations required to move `all balls` to each index box from the `initial state` is given by the array:
## `ans = [1, 1, 3]`
**Explanation:**  
1. For the first box: Move one ball from the second box → `1 operation`.  
2. For the second box: Move one ball from the first box → `1 operation`.  
3. For the third box:  
   - Move one ball from the first box → `2 operations`.  
   - Move one ball from the second box → `1 operation`.  
   Total = `3 operations`.

#### Example 2:
**Input:**  
`boxes = "001011"`  
**Output:**  
`[11, 8, 5, 4, 3, 4]`  

---

### Constraints
$$ 
n = \text{boxes.length} 
$$
$$ 
1 \leq n \leq 2000 
$$
$$ 
\text{boxes}[i] \in \{ 0 , 1 \} 
$$


# Problem: String Matching in an Array

You are given an array of strings `words`. Your task is to find all the strings in the array that are a substring of another string in the same array. Return these strings in any order.

### Key Points:
- A **substring** is a part of another string. For example, "as" is a substring of "mass".
- We are looking for strings in the array that can be found as substrings within other strings in the array.

### Examples:

#### Example 1:
**Input**:  
`words = ["mass", "as", "hero", "superhero"]`  
**Output**:  
`["as", "hero"]`  
**Explanation**:  
- "as" is a substring of "mass".  
- "hero" is a substring of "superhero".  
- The order of the output does not matter. For example, `["hero", "as"]` is also correct.

---

#### Example 2:
**Input**:  
`words = ["leetcode", "et", "code"]`  
**Output**:  
`["et", "code"]`  
**Explanation**:  
- "et" is a substring of "leetcode".  
- "code" is a substring of "leetcode".

---

#### Example 3:
**Input**:  
`words = ["blue", "green", "bu"]`  
**Output**:  
`[]`  
**Explanation**:  
No string in the array is a substring of another string.

---
### Constraints:
$$
\begin{aligned}
&1 \leq \text{words.length} \leq 100 \\
&1 \leq \text{words[i].length} \leq 30 \\
&\text{Each string in words contains only lowercase English letters.} \\
&\text{All strings in words are unique.}
\end{aligned}
$$

### What to Do:
1. Go through each string in the array.
2. Check if it is a substring of any other string in the array.
3. Collect all such strings and return them in any order.

### Output:
The output is an array containing strings that are substrings of other strings in the input array.


# Problem: Count Prefix and Suffix Pairs

You are given an array of strings called `words`. Your task is to count the number of pairs `(i, j)` (where `i < j`) such that a string `words[i]` is both a **prefix** and a **suffix** of another string `words[j]`.

---

### Key Definitions:



-   **Prefix** :  A string `str1` is a prefix of `str2` if `str2` starts with `str1`. 
     Example: `"ab"` is a prefix of `"abc"`, but not of `"cab"`.
- **Suffix**: A string `str1` is a suffix of `str2` if `str2` ends with `str1`.  
  Example: `"bc"` is a suffix of `"abc"`, but not of `"bca"`.
- **Prefix and Suffix**: A string `str1` is both a prefix and suffix of `str2` 
     if:
          -  `str2` starts with `str1`, and
          -  `str2` ends with `str1`.
---
### Examples:

#### Example 1:
**Input**: `words = ["a", "aba", "ababa", "aa"]`  
**Output**: `4`  

**Explanation**:  
The valid pairs `(i, j)` are:
1. `(0, 1)` because `"a"` is both a prefix and suffix of `"aba"`.
2. `(0, 2)` because `"a"` is both a prefix and suffix of `"ababa"`.
3. `(0, 3)` because `"a"` is both a prefix and suffix of `"aa"`.
4. `(1, 2)` because `"aba"` is both a prefix and suffix of `"ababa"`.

---

#### Example 2:
**Input**: `words = ["pa", "papa", "ma", "mama"]`  
**Output**: `2`  

**Explanation**:  
The valid pairs `(i, j)` are:
1. `(0, 1)` because `"pa"` is both a prefix and suffix of `"papa"`.
2. `(2, 3)` because `"ma"` is both a prefix and suffix of `"mama"`.

---

#### Example 3:
**Input**: `words = ["abab", "ab"]`  
**Output**: `0`  

**Explanation**:  
No valid pairs exist because none of the strings in `words` satisfy the condition of being both a prefix and suffix.

---

### Constraints:
- `1 <= words.length <= 50`
- `1 <= words[i].length <= 10`
- `words[i]` contains only lowercase English letters.


### Goal:
Return the total number of valid `(i, j)` pairs where `i < j` and `words[i]` is both a **prefix** and a **suffix** of `words[j]`.





Select a card whose code you want to track