Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in place and use only constant extra memory.


Given an array of integers `nums` of size `n`, find the next permutation.

### Input Format

First Parameter - number `n`

Second Parameter - array `nums` of size `n`

### Output Format

return the array of integers.

### Example 1:
```txt
Input:
    3
    1 2 3
Output:
    1 3 2
```

### Example 2:
```txt
Input:
    3
    3 2 1
Output:
    1 2 3
```

### Example 3:
```txt
Input:
    3
    1 1 5
Output:
    1 5 1
```

#### Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
- Expected Time Complexity: O(n)
- Expected Space Complexity: O(1)


Best Time to Buy and Sell Stock

You are given an array of prices where prices[i] is the price of a given stock on an ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

### Input Format

First Parameter - number `n`

Second Parameter - array of integers of size `n`

### Output Format

Return the number.

### Example 1:
```txt
Input:
    6
    7 1 5 3 6 4
Output:
    5
Explanation:
    Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
    Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
```

### Example 2:
```txt
Input:
    5
    7 6 4 3 1
Output:
    0
Explanation:
    In this case, no transactions are done and the max profit = 0.
```

#### Constraints:
- 1 <= prices.length <= 10^5^
- 0 <= prices[i] <= 10^4^
- Expected Time Complexity: O(n)
- Expected Space Complexity: O(1)


Maximum Product Subarray

Given an array `arr` that contains N integers. Find a contiguous non-empty subarray that has the largest product, and return the product.

*The test cases are generated so that the answer will fit in a 32-bit integer.*

### Input Format

First Parameter - number `n`

Second Parameter - array of integers `arr` of size `n`

### Output Format

Return the number

### Example 1:
```txt
Input:
    5
    6 -3 -10 0 2
Output:
    180
Explanation:
    Subarray with maximum product
    is [6, -3, -10] which gives the product as 180.
```
### Example 2:
```txt
Input:
    6
    2 3 4 5 -1 0
Output:
    120
Explanation:
    Explanation: Subarray with maximum product
    is [2, 3, 4, 5] which gives product as 120.
```


#### Constraints:
- 1 ≤ N ≤ 2 * 10^4^
- -10 ≤ arr[i] ≤ 10
- Expected Time Complexity: O(N)
- Expected Auxiliary Space: O(1)


Next Greater Element

Given a circular integer array `nums` (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in `nums`.

The next greater number of a number `x` is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

### Input Format

First Parameter - number `n`

Second Parameter - array `nums` of size `n`

### Output Format

Return the array

### Example 1:
```txt
Input:
    4
    1 3 2 4
Output:
    3 4 4 -1
Explanation:
    In the array, the next larger element to 1 is 3, 3 is 4, 2 is 4 and for 4 needs to search circularly. Since there exists no next number greater than 4, it's -1. 
```

### Example 2:
```txt
Input:
    5
    6 8 0 1 3
Output:
    8 -1 1 3 6
Explanation: 
    In the array, the next larger element to 6 is 8, 8 is -1, 0 is 1, 1 is 3 and 3 is 6.
```


#### Constraints:
- 1 ≤ n ≤ 10^4^
- -10^9^ ≤ arr[i] ≤ 10^9^
- Expected Time Complexity: O(N)
- Expected Auxilliary Space: O(N)


Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i are at (i, ai) and (i, 0). 

Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

*Return the maximum amount of water a container can store.*

**Note**: that you may not slant the container.

### Input Format

First Parameter - number `n`

Second Parameter - array `arr` of size `n`

### Output Format

Return the number.

### Example 1:

!["1](https://cdn.discordapp.com/attachments/882247424809242705/909760369751379968/unknown.png)
```txt
Input:
    9
    1 8 6 2 5 4 8 3 7
Output:
    49
Explanation:
    The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
```

### Example 2:
```txt
Input:
    2
    1 1
Output:
    1
```

#### Constraints:
- 2 <= n <= 10^5^
- 0 <= arr[i] <= 10^4^
- Expected Space Complexity: O(n)
- Expected Time Complexity: O(1)

Binary Search

Given an array of integers `nums` which are sorted in ascending order, and an integer `target`, write a function to search target in `nums`. If the target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

### Input Format

First Parameter - number `n`

Second Parameter - array of integers `nums` of size `n`

Third Parameter - number `target`

### Output Format

Return the number

### Example 1

```txt
Input:
    6
    -1 0 3 5 9 12
    9
Output:
    4
Explanation:
    Explanation: 9 exists in nums and its index is 4
```

### Example 2

```txt
Input:
    6
    -1 0 3 5 9 12
    2
Output:
    -1
Explanation:
    2 does not exist in nums so return -1
```

#### Constraints

- 1 <= nums.length <= 10^4^
- -10^4^ < nums[i], target < 10^4^
- All the integers in nums are unique, nums is sorted in ascending order.
- Expected Time Complexity: O(log n)
- Expected Space Complexity: O(1)

Two Sum

Given an array of integers `nums` of size `n` and an integer `target`, return indices of the two numbers such that they add up to target.

You may assume that each input would have **exactly one solution**, and you may not use the same element twice.

Note: The pair of integers must be in the order of their position in the array i.e., the smaller index first then comes the larger one.

### Input Format 

First Parameter - number `n`

Second Parameter - array of integers `nums` of size `n`

Third Parameter - number `target`

### Output Format 

Return the pair of indices in an array.

### Example 1:
```txt
Input : 
   4
   2 7 11 15
   9
Output : 
    0 1
Explaination : nums[0] + nums[1] == 9, return 0, 1
```

### Example 2:
```txt
Input : 
    3
    3 2 4
    6
Output : 
     1 2
```

#### Constraints:
    
- 2 <= N <= 10^5^
- -10^9^ <= arr[i] <= 10^9^
- -2 * 10^9^ <= target <= 2 * 10^9^
- Only one valid answer exists.
- Expected Time complexity: O(n)
- Expected Space complexity: O(1)


Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

```
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.  
```
Given n, calculate F(n).

**Try doing it in both recursive and iterative method**     
### Input Format

First Parameter - Integer `n`

### Output Format

Return the integer

### Example 1:
```txt
Input:
    3
Output:
    2
Explanation:
    F(3) = F(2) + F(1) = 1 + 1 = 2.
```

### Example 2:
```txt
Input:
    4
Output:
    3
Explanation:
    F(4) = F(3) + F(2) = 2 + 1 = 3.
```
#### Constraints:
- 0 <= n <= 30


Set Matrix Zeroes

Given an m x n integer matrix `matrix`, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

### Input Format

First Parameter - `matrix` of size `m x n`

### Output Format

Return the matrix.

### Example 1:
```txt
Input:
     3 3
     1 1 1
     1 0 1
     1 1 1
Output:
     [[1,0,1],[0,0,0],[1,0,1]]
Explanation: 3 3 represents the size of the matrix. All the value which are in row 1 and column 1 is converted to 0.
   
```

### Example 2:
```txt
Input:
    3 4
    0 1 2 0
    3 4 5 2
    1 3 1 5
Output:
    [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
```
#### Constraints:
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
- Expected Time Complexity: O(m x n)
- Expected Space Complexity: O(1)


Contains Duplicate

Given an integer array 'nums', return 1(true) if any value appears at least twice in the array, and return 0(false) if every element is distinct.

### Input Format

First Parameter - Number `n`

Second Parameter - Array of Integer `arr`

### Output Format

Return the integer(0 or 1)

### Example 1:
```txt
Input:
    4
    1 2 3 1
Output:
    1
Explanation:
    '1' is repeated two times.
```

### Example 2:
```txt
Input:
    4
    1 2 3 4 
Output:
    0
Explanation:
    No values are repeated.
```
#### Constraints:
- 1 <= nums.length <= 105
- -10^9 <= nums[i] <= 10^9



Flood Fill

An image is represented by an `m x n` integer grid `image` where `image[i][j]` represents the pixel value of the image.

You are also given three integers `sr`, `sc`, and `color`. You should perform a **flood fill** on the image starting from the pixel `image[sr][sc]`.

To perform a **flood fill**, consider the starting pixel, plus any pixels connected **4-directionally** to the starting pixel of the same color as the starting pixel, plus any pixels connected **4-directionally** to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with **color**.

Return the modified image after performing the flood fill.

### Input Format

First Parameter - matrix `image` of size `m x n`

Second Parameter - number `sr`

Third Parameter - number `sc`

Fourth Parameter - number `newColor`

### Output Format

Return the modified matrix.

### Example 1:

!["flood-grid-1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/flood-grid-1)

```txt
Input:
     3 3
     1 1 1
     1 1 0
     1 0 1
     1 
     1 
     2
Output:
     [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
3 3 represents the size of the matrix. From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels are connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2 because it is not 4-directionally connected to the starting pixel.
   
```

### Example 2:
```txt
Input:
    2 3
    0 0 0
    0 0 0
    0 
    0 
    2
Output:
    [[2,2,2],[2,2,2]]
```
#### Constraints:
- m == image.length
- n == image[i].length
- 1 <= m, n <= 50
- 0 <= image[i][j], color < 2^16^
- 0 <= sr < m
- 0 <= sc < n
- Expected Time Complexity: O(n)
- Expected Space Complexity: O(n)


Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and *return an array of the non-overlapping intervals that cover all the intervals in the input.*

### Input Format

First Parameter - matrix `intervals` of size `m x n`

### Output Format

Return the matrix.

### Example 1:
```txt
Input:
     4 2
     1 3
     2 6
     8 10
     15 18
Output:
     [[1,6],[8,10],[15,18]]
Explanation:
4 2 represents the size of the matrix. Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
   
```

### Example 2:
```txt
Input:
    2 2
    1 4
    4 5
Output:
    [[1,5]]
Explanation: 
    2 2 represents the size of the matrix. Intervals [1,4] and [4,5] are considered overlapping.
```
#### Constraints:
- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104


Final Value of Variable After Performing Operations

There is a programming language with only four operations and one variable X:

`++X` and `X++` increment the value of the variable X by 1.
`--X` and `X--` decrements the value of the variable X by 1.
Initially, the value of X is 0.

Given an array of strings operations containing a list of operations, return the final value of X after performing all the operations.

### Input Format

First Parameter - number `n`

Second Parameter - Array `arr` of strings

### Output Format

Return the number

### Example 1:
```txt
Input:
    3
    --X X++ X++
Output:
    1
Explanation:
    The operations are performed as follows:
Initially, X = 0.
--X: X is decremented by 1, X =  0 - 1 = -1.
X++: X is incremented by 1, X = -1 + 1 =  0.
X++: X is incremented by 1, X =  0 + 1 =  1.
```

### Example 2:
```txt
Input:
    3
    ++X ++X X++
Output:
    3
Explanation:
    The operations are performed as follows:
Initially, X = 0.
++X: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
X++: X is incremented by 1, X = 2 + 1 = 3
```
#### Constraints:
- 1 <= arr.length <= 100
- `arr[i]` will be either `++X`, `X++`, `--X`, or `X--`.
- Expected Time Complexity: O(n)
- Expected Space Complexity: O(1)


Missing Number

Given an array **arr** containing n distinct numbers in the range **[0, n]**, return the only number in the range that is missing from the array.

### Input Format
First parameter - number `n`

Second Parameter - array of integers `arr` of size `n`

### Output Format
Return the number

### Example 1
```txt
Input: 
   3
   3 0 1
Output: 
   2
Explanation: 
    n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in arr.
```

### Example 2
```txt
Input: 
   2
   0 1
Output: 
   2
Explanation: 
   n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in arr.
```

#### Constraints
- 1 <= n <= 10^4^
- 0 <= arr[i] <= n
- All the numbers of **arr** are **unique**.
- Expected Time complexity: O(n)
- Expected Space Complexity: O(1)


Add two numbers

You are given two **non-empty linked lists** representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

```
Class Node:
    data (int)
    next (Node)
```

### Input Format

First Parameter - Node `l1`

Second Parameter - Node `l2`

### Output Format

Return the `head` of the list which has sum of both the lists.

### Example 1 :
```
Input :
   l1 = 2 4 3 
   l2 = 5 6 4
Output : 
   7 0 8
Explanation :
    243 
  + 564 
=   708  (adding left to right)
```

### Example 2 : 
```
Input :
    l1 = 9 9 9 9 9 9 9 
    l2 = 9 9 9 9 
Output :
    8 9 9 9 0 0 0 1
```
#### Constraints:
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= `Node.data` <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.

Convert Binary Number in a Linked List to Integer

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

```
Class Node:
    data (int)
    next (Node)
```

### Input Format

First Parameter - Node `head`

### Output Format

Return the number

### Example 1:
```txt
Input:
    1 0 1
Output:
    5
Explanation:
    (101) in base 2 = (5) in base 10.
```

### Example 2:
```txt
Input:
    0
Output:
    0
```
#### Constraints:
- The Linked List is not empty.
- Number of nodes will not exceed 30.
- Each node's value is either 0 or 1

 Find if Path Exists in Graph

There is a **bi-directional** graph with `n` vertices, where each vertex is labeled from `0` to `n - 1` **(inclusive)**. The edges in the graph are represented as a 2D integer array `edges`, where each `edges[i] = [ui, vi]` denotes a bi-directional edge between vertex `ui` and vertex `vi`. Every vertex pair is connected by **at most one** edge, and no vertex has an edge to itself.

You want to determine if there is a **valid path** that exists from vertex `source` to vertex `destination`.

Given `edges` and the integers `n`, `source`, and `destination`, return `1` if there is a **valid path** from `source` to `destination`, or `0` otherwise.

### Input Format: 

First Parameter: Number of vertex `n` 

Second Parameter:  matrix `edges`  of size `mat_dims[0] x mat_dims[1]`

Third parameter: number `source`

Fourth Parameter: number `destination`


### Output Format:  
Return the number.

### Example 1:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/Verify-Graph)
```txt
Input: 
3
3 2
0 1
1 2
2 0
0
2
Output:
1
Explanation: 3 2 represents the size of the matrix. 
There are two paths from vertex 0 to vertex 2:
     -0->1->2
     -0->2
```
### Example 2:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/Verify-Graph-2)
```txt
Input: 
6
5 2
0 1
0 2
3 5
5 4
4 3
0
5
Output:
0
Explanation: 5 2 represents the size of the matrix.
There is no path from vertex 0 to vertex 5.
```
### Constraints:

+ 1 <= n <= 2 * 10^5^
+ 0 <= `edges.length` <= 2 * 10^5^
+ `edges[i].length` == 2
+ 0 <= `ui, vi` <= `n - 1`
+ `ui` != `vi`
+ 0 <= `source`, `destination` <= `n - 1`
+ There are no duplicate edges.
+ There are no self edges.
+ Expected Time Complexity: O(N)
+ Expected Auxiliary Space: O(N)







Hello User

You are given a String  **`str`**. Return the String by Concatenating it with String **"Hello, "** and an exclamation mark at the end **"!"**.

### Input Format

First Parameter - String **str**

### Output Format

Return a String **`s`**

### Example 1:

    Input:
        "Mac"
    Output:
        "Hello, Mac!"
    Explanation:
        Given a String, Mac is Concatenated with string "Hello, " at the beginning and "!" at the end

#### Constraints 
+ 1 <= length of string <= 20
+ Expected Time Complexity: O(1)
+ Expected Space Complexity: O(1)


Product of Sum and Difference

You are given two integers, **`a`** and **`b`**.  
Compute the Sum and Difference of `a` and `b`. Return the Product of Sum and Difference. 

### Input Format

First Parameter - Integer **`a`**

Second Parameter  - Integer **`b`**

### Output Format

Return the integer.

### Example 1:

    Input:
        5
        2
    Output:
        21
    Explanation:
        Sum is (5 + 2)  = 7 and Difference is (5 - 2) = 3. The product of Sum and Difference is 21.

### Example 2:

    Input:
        -14
        -4
    Output:
        180
    Explanation:
        The Sum is -18 and Difference is -10. The product is 180.

#### Constraints 
+ -10^4^  <= a, b <=  10^4^
+ Expected Time Complexity: O(1)
+ Expected Space Complexity: O(1)


Product of Division

You are given two integers, **`a`** and **`b`**. 

Let `x` be the integer division and `y` be the decimal(float) division of `a` and `b`. 

Return the product of `x` and `y`.

### Input Format

First Parameter - Integer **`a`**

Second Parameter  - Integer **`b`**

### Output Format

Return the decimal product of integer division **x** and decimal division **y**  of **a** and **b**.

### Example 1:

    Input:
        21
        5
    Output:
        16.8
    Explanation:
        The int and float value of 21 / 5 is 4 and 4.2 respectively. The product is 16.8
        
### Example 2:

    Input:
        11
        4
    Output:
        5.5
    Explanation:
        The integer and float value of (11 / 4) is 2 and 2.75 respectively. The product is 5.5

#### Constraints 
+ Range of a and b is [-10^4^, 10^4^] except 0.
+ Expected Time Complexity: O(1)
+ Expected Space Complexity: O(1)


Average between Indices

Given an array **`arr`** of size **`n`**, and two intervals **`x`** and **`y`**.  Find the average of elements which lies between the given intervals inclusively.

### Input Format

First Parameter - number **`n`**

Second Parameter  - array **`arr`** of size **`n`**

Third Parameter - number **`x`** 

Fourth Parameter - number **`y`**

### Output Format

Return the decimal value

### Example 1:

    Input:
        6
        6 2 5 4 3 1
        2
        5
    Output:
        3.25
    Explanation:
        The elements between indices 2 and 5 are 5, 4, 3 and 1. The Average is: 
             (5 + 4 + 3 + 1) / 4 = 3.25
        
### Example 2:

    Input:
        2
        7 2
        0
        1
    Output:
        4.5
    Explanation:
        The elements between indices 0 and 1 are 7 and 2. The average is:
            (7 + 2) / 2 = 4.5

#### Constraints 
+ 0 <= n <= 10^4^
+ -10^4^ <= arr[i] <= 10^4^
+ 0 <= x <= y < n
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(1)


Characters Frequency

Given a string `str1`, Return the array containing the frequency of each character in the order of their occurrence.

### Input Format

First Parameter - string `str1`

### Output Format

Return the array. 

### Example 1:

    Input:
        arfardarb
    Output:
        3 3 1 1 1
    Explanation:
        a is repeated 3 times, followed by r which is repeated 3 times. f, d and b occurs only 1 time.    

#### Constraints 
+ 1 <= n <= 10^5^
+ String contains lowercase letters
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(1)

Palindromic Staircase

Given a Positive Integer **`n`**,  return an array of string containing the palindromic string of intergers.

### Input Format

First Parameter - number `n`

### Output Format

Return the array of string. 

### Example 1:

    Input:
        5
    Output:
        1
        121
        12321
        1234321
        123454321
    Explanation:
        The size of staircase is 5. So you have to generate string of integers in such a way that it is palindromic. 

### Example 2:

    Input:
        3
    Output:
        1
        121
        12321
        
#### Constraints 
+ 0 < n < 10
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(n)

Second Largest Element

Given an `arr` of size `n`. Return the second largest element.

### Input Format

First Parameter - number `n`

Second Parameter - array `arr` of characters of size `n`

### Output Format

Return the number. 

### Example 1:

    Input:
        6
        2 1 2 8 7 8
    Output:
        7
    Explanation:
        The second largest element is 7.

### Example 2:

    Input:
        2
        20 10
    Output:
        10
    Explanation:
        The second largest is 10.

#### Constraints 
+ 1 < n <= 10^5^
+ -10^4^ <= arr[i] <= 10^4^
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(1)

Redundant Connection

In this problem, a tree is an **undirected graph** that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from `1` to `n`, with one additional edge added. The added edge has two **different** vertices chosen from `1` to `n`, and was not an edge that already existed. The graph is represented as an array `edges` of length `n` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the graph.

Return an edge that can be removed so that the resulting graph is a tree of `n` nodes. If there are multiple answers, return the answer that occurs last in the input.

### Input Format

First Parameter - matrix `edges` of size `m x n`

### Output Format

Return the array of number.

### Example 1:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/NO-Cycle-1)
```txt
Input: 
3 2
1 2
1 3
2 3
Output:
2 3
Explanation: 3 2 represents the size of the matrix and while traversing the matrix, edge 2 3 will form cycle. so, we need to remove the edge 2 3. 
```
### Example 2:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/NO-Cycle-2)
```txt
Input: 
5 2
1 2
2 3
3 4
1 4
1 5
Output:
1 4
Explanation: 5 2 represents the size of the matrix and while traversing the matrix, edge 1 4 will form cycle. so, we need to remove the edge 1 4. 
```

### Constraints:
+ n == `edges.length`
+ 3 <= `n` <= 1000
+ `edges[i].length` == 2
+ 1 <= ai < bi <= `edges.length`
+ ai != bi
+ There are no repeated edges.
+ The given graph is connected.
+ Expected Time Complexity: O(N)
+ Expected Auxiliary Space: O(N)

Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given `height`, a 2D array of size `rows x columns`, where `height[row][col]` represents the height of cell `(row, col)`. You are situated in the top-left cell, `(0, 0)`, and you hope to travel to the bottom-right cell, `(rows-1, columns-1)` (i.e., **0-indexed**). You can move **up**, **down**, **left**, or **right**, and you wish to find a route that requires the minimum effort.

A route's **effort** is the **maximum absolute difference** in heights between two consecutive cells of the route.

*Return the minimum **effort** required to travel from the top-left cell to the bottom-right cell.*

### Input format

First Parameter - matrix `height` of size `rows x columns`

### Output Format

Return the number.

### Example 1:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/Min-Cost-1)
```txt
Input: 
3 3
1 2 2
3 8 2
5 3 5
Output:
2
Explanation: 
The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
```
### Example 2:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/Min-Cost-2)
```txt
Input: 
3 3
1 2 3
3 8 4
5 3 5
Output:
1
Explanation: 3 3 represents the size of the matrix.
The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
```
### Example 3:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/Min-Cost-3)
```txt
Input: 
5 5
1 2 1 1 1
1 2 1 2 1
1 2 1 2 1
1 2 1 2 1
1 1 1 2 1
Output:
0
Explanation: 5 5 represents the size of the matrix.
This route does not require any cost.
```
#### Constraints:
+ `rows` == `height.length`
+ `columns` == `height[i].length`
+ 1 <= `rows, columns` <= 100
+ 1 <= `height[i][j]` <= 10^6^
+ Expected Time Complexity: O(`rows` * `cols`* `log(MAX_HEIGHT)`)
+ Expected Auxiliary Space: O(`m`*`n`)

Surrounded Regions

Given an `m x n` matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.
### Input Format
First Parameter - matrix `board` of string of size `m x n`

### Output Format

Return the matrix of string.

### Example 1:
!["1"](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/Capture%20territory)
```txt
Input: 
4 4
X X X X
X O O X
X X O X
X O X X
Output:
X X X X
X X X X
X X X X
X O X X
Explanation: 4 4 represents the size of the board. 
      Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
```
### Constraints:

+ `m` == `board.length`
+ `n` == `board[i].length`
+ 1 <= `m, n` <= 200
+ `board[i][j]` is 'X' or 'O'.
+ Expected Time Complexity: O(n*m)
+ Expected Auxiliary Space: O(n*m)

Search Insert Position

Given an sorted array `arr` of size `n` and an integer `key`. If the target exists in the array, return its index. If not, return the index where it would be if it were inserted in order.

### Input Format

First Parameter - number `n`

Second Parameter - array `arr` of size `n`

Third Parameter - number `key`

### Output Format

Return the number. 

### Example 1:

    Input:
        5
        1 3 4 5 10
        2
    Output:
        1
    Explanation:
        Since 2 is missing from the given array, it would be inserted at index 1.

### Example 2:

    Input:
        5
        1 3 8 9 11
        9
    Output:
        3
    Explanation:
        The key 9 was found at index 3.

#### Constraints 
+ 1 < n <= 10^4^
+ -10^4^ <= arr[i], key <= 10^4^
+ All the integers in `arr` are unique.
+ `arr` is sorted in ascending order.
+ Expected Time Complexity: O(log n)
+ Expected Space Complexity: O(1)

Remove Duplicates from Sorted Array

Given an array `arr` of size `n` sorted in **non-decreasing order**, remove the duplicates in-place such that each unique element appears only once keeping the relative order of the element same.

### Input Format

First Parameter - number `n`

Second Parameter - array `arr` of size `n`

### Output Format

Return the array.

### Example 1:

    Input:
        6
        1 1 4 4 4 7
    Output:
        1 4 7
    Explanation:
        1 and 4 are repeated in the original array. When you remove them, We are left with 1, 4 and 7. 

### Example 2:

    Input:
        5
        3 3 4 5 6
    Output:
        3 4 5 6
    Explanation:
        The repeating element that must be removed is 3.

#### Constraints 
+ 1 <= n <= 3 * 10^4^
+ -100 <= arr[i], key <= 100
+ `arr` is sorted in **non-decreasing order**.
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(n)

Pow(x,n)

Implement pow(x, n), which calculates x raised to the power n.

Return the number

### Input Format

First Parameter - number `x`

Second Parameter - number `n`

### Output Format

Return the number. 

### Example 1:

    Input:
        3
        4
    Output:
        81

### Example 2:

    Input:
        7
        5
    Output:
        16807

#### Constraints 
+ -10< x < 10
+ 0 <= n <= 5
+ Expected Time Complexity: O(log n)
+ Expected Space Complexity: O(1)

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to modify the input 2D matrix directly. 

**You are not allowed to allocate another 2D matrix and do the rotation.**

### Input Format

First Parameter - vector<vector<int>>`mat` of dimension `n` x `n`

### Output Format

Return the matrix. 

### Example 1:

    Input:
        3 3
        1 2 3
        4 5 6
        7 8 9
    Output:
        7 4 1
        8 5 2
        9 6 3
![mat1](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/RotateImage1)


### Example 2:

    Input:
        4 4
        5 1 9 11
        2 4 8 10
        13 3 6 7
        15 14 12 16
    Output:
        15 13 2 5
        14 3 4 1
        12 6 8 9
        16 7 10 11
![mat2](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/RotateImage2)
        

#### Constraints 
+ 3 <= n <= 20
+ Expected Time Complexity: O(n^2^)
+ Expected Space Complexity: O(1)

Product of Array Except Self

Given an integer array `arr`, return an array `res` such that `res[i]` is equal to the product of all the elements of `arr` except `arr[i]`.

 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

**You must write an algorithm that runs in O(n) and without using the division operation.**

### Input Format

First Parameter - int `n`

Second Parameter - array `arr`

### Output Format

Return the array.

### Example 1:

    Input:
        4
        1 2 3 4
    Output:
       24 12 8 6
    Explanation:
        The output contains the product of each element except itself. For res[0], product of all nums except self is 2 * 3 * 4 = 24 and so on...

### Example 2:

    Input:
        6
        4 -1 5 10 2 1
    Output:
        -100 400 -80 -40 -200 -400
    Explanation:
        The output contains the product of each element except itself.

#### Constraints 
+ 2 <= n <= 10^5^
+ -30 <= arr[i] <= 30
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(n)

Valid Anagram

Given two strings `s1` and `s2`, return true if `s2` is an anagram of `s1`, and false otherwise.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

return **1** if true or **0** if false.

### Input Format

First Parameter - string `s1`

Second Parameter - string `s2`

### Output Format

Return the boolean. 

### Example 1:

    Input:
        dusty
        study
    Output:
        1
    Explanation:
        s2 is anagram of s1. return 1 specifying true.

### Example 2:

    Input:
        cat
        rat
    Output:
        0
    Explanation:
        s2 had letter 'r' which is not in s1. Hence, it is not an anagram. 

#### Constraints 
+ 1 <= s1.length, s2.length <= 5 * 10^4^
+ s1 and s2 consists of lowercase English letters.
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(n)

Longest ZigZag Path in a Binary Tree

You are given the `root` of a binary tree.

A ZigZag path for a binary tree is defined as follow:

+ Choose **any** node in the binary tree and a direction (right or left).
+ If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
+ Change the direction from right to left or from left to right.
+ Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest **ZigZag** path contained in that tree.

```
Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)
```

### Input Format

First Parameter - TreeNode `root`

### Output Format

Return the number.

### Example 1:
![img](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/zigzag1)

    Input:      
        1 null 1 1 1 null null 1 1 null 1 null null null 1 null 1

    Output: 3

    Explanation:   
        Longest ZigZag path in blue nodes (right -> left -> right).

### Example 2:
![img](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/zigzag2)

    Input:   
        root = 1 1 1 null 1 null null 1 1 null 1

    Output: 4

#### Constraints
+ The number of nodes in the tree is in the range [1, 5 * 10^4^].
+ 1 <= `Node.val` <= 100
+ Expected Time Complexity : O(n)
+ Expected Space Complexity : O(n)


Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. 

You must make sure your result is the smallest in lexicographical order among all possible results.

### Input Format:
First Parameter - String `s` 
### Output Format:
Return a string that is the smallest in lexicographical order among all possible results

### Example 1:
```
Input: bcabc
Output: abc
```

### Example 2:
```
Input: devsnest
Output: devnst
```
### Constraints:-
+ 1 <= length of string <= 10^4^
+ string consists of lowercase English letters.
+ Expected Time Complexity:- O(n)
+ Expected Space Complexity: O(n)

Kth Largest Element in an Array

Given an integer array `nums` and an integer `k`, return the k^th^ largest element in the array.

Note that it is the k^th^ largest element in the sorted order, not the k^th^ distinct element.

### Input Format

First Parameter: number `n`

Second Parameter - array `nums` of size `n`

Third Parameter - number `k`

### Output Format

Return the number.

### Example 1
```txt 
Input :
    6
    3 2 1 5 6 4
    2

Output : 
    5
```
### Example 2
```txt
Input : 
    9
    3 2 3 1 2 4 5 5 6
    4

Output : 
    4
```

#### Constraints:
+ *1 <= k <= n <= 10^4^.*
+ *-10^4^ <= nums[i] <= 10^4^.*
+ Expected Time Complexity : O(nlogk).
+ Expected Space Complexity : O(k)

3Sum

Given an integer array `nums` of size `n`, return all the triplets [nums[i], nums[j], nums[k]] such that `i` != `j`,`i` != `k`, and `j` != `k`, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

The result must be in non-decreasing order.

### Input Format

First Parameter - number `n`

Second Parameter - array `nums`

### Output Format

Return the array of array.

### Example 1:

    Input:
        6
        -1 -2 -4 2 2 3
    Output:
        -4 2 2
        -2 -1 3
    Explanation:
        The sum of (-4 + 2 + 2) = 0 and the indices of each element are not equal to each other, i.e. 2 != 3, 3 != 4, 4 != 2. 
### Example 2:

    Input
        0
    Output:
        [] - Empty array
    Explanation:
        There is no 3 elements that sum upto zero. 

#### Constraints 
+ 0 <= n <= 3000
+ -10^5^ <= nums[i] <= 10^5^
+ Expected Time Complexity: O(n^2^)
+ Expected Space Complexity: O(n)

Infix to Postfix

**Infix Expression** :- The expression of the form `a op b` where an operator is written between two operands.

**Postfix Expression** :- The expression of the form `a b op` where an operator is followed for every pair of operands.

Given an infix expression `str`. Convert the given infix expression to postfix expression and return it. 

**Note** :-  The operators `+` and `-` have same precedence. The operators `\` and `*` have same precedence. The operator `^` have higher precedence than `\` and `*`. The operators `*` and `\` have higher precedence than `+` and `-`. 

### Input Format :- 
First parameter - *str* ,  infix expression .
 
### Output Format :- 
Return the string

### Example 1 :-
    Input :
        a+b*(c^d-e)^(f+g*h)-i
    Output :
        abcd^e-fgh*+^*+i-
    Explanation :
        After converting the infix expression into postfix expression, the resultant expression will be abcd^e-fgh*+^*+i- 

### Example 2 :-
    Input :
        A*(B+C)/D
    Output :
        ABC+*D/

#### Constraints :- 
+ 1 <= n <= 10^5^
+ `str` is a valid **infix expression**
+ Expected Time Complexity :- O(n)
+ Expected Space Complexity :- O(n)

Page Replacement Algorithm

In operating system, Page replacement algorithm are responsible to decide which page is needed to be replaced when new page comes in.

Whenever a new page is referred and not present in memory, **page fault** occurs and Operating System replaces one of the existing pages with newly needed page.

Given an array of integers `pages` of size `n` and a memory capacity `capacity`, return the total number of **page faults**.

**Note**: You must find number of page faults using **First In First Out (FIFO)** page replacement algorithm.

### Input Format
First Parameter - number `n`

Second Parameter - array `pages` of size `n`

Third Parameter - number `capacity`

### Output Format

Return a number 

### Example 1:
```
Input:  6
        1 3 0 3 5 6 
        3
Output: 5
Explanation:
     Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page Faults.
When 3 comes, it is already in memory so —> 0 Page Faults.
Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. —> 1 Page Fault
When 6 comes, it is not available in memory so it replaces the oldest page slot i.e 3  —> 1 Page Fault
```

### Example 2:
```
Input: 12
       0 2 1 6 4 0 1 0 3 1 2 1.
       4
Output:
       9
```

#### Constraints 
+ 1 <= n <= 10^6^
+ 1<= pages[i] <= 10
+ 1<=slot <= 100
+ Expected Time Complexity: O(n)
+ Expected Space Complexity: O(n)

Rotten Oranges

You are given an `m x n` grid where each cell can have one of three values:

+ `0` representing an empty cell,
+ `1` representing a fresh orange, 
+ `2` representing a rotten orange.

Every minute, any fresh orange that is **4-directionally adjacent** to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return `-1`.

**Note for C++ and Java:** You should not use **Pair**. 

### Input Format

First Parameter - Matrix `grid` of size `m x n`

### Output Format 

Return the number

### Example 1:

```
Input: 
    3 3
    2 1 1        
    1 1 0
    0 1 1
Output: 4
Explanation: 3 3 represents the size of the grid. Minimum number of minutes until no cell has fresh oranges is 4. 
```
![img1](https://devsnest-custom-images.s3.ap-south-1.amazonaws.com/rotten%20orange)
### Example 2:

```
Input:
    3 3
    2 1 1        
    0 1 1
    1 0 1
Output: -1
Explanation: 3 3 represents the size of the grid. The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
```

#### Constraints

+ `m` == `grid.length`
+ `n` == `grid[i].length`
+ 1 <= `m`, `n` <= 10
+ `grid[i][j]` is `0`, `1` or `2`
+ Expected Time Complexity: O(n^2^)
+ Expected Space Complexity: O(n^2^)
 

DSA Challenges