We are given an array of integers and a range, we need to find whether the subarray which falls in this range has values in the form of a mountain or not. All values of the subarray are said to be in the form of a mountain if either all values are increasing or decreasing or first increasing and then decreasing. More formally a subarray [a1, a2, a3 … aN] is said to be in form of a mountain if there exists an integer K, 1 <= K <= N such that,
a1 <= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >= aN
You have to process Q queries. In each query you are given two integer L and R, denoting starting and last index of the subarrays respectively.

Example 1:

Input:
N = 8
a[] = {2,3,2,4,4,6,3,2}
Q = 2
Queries = (0,2), (1,3)
Output:
Yes
No
Explanation: For L = 0 and R = 2, a0 = 2,
a1 = 3 and a2 = 2, since they are in the
valid order,answer is Yes.
For L = 1 and R = 3, a1 = 3, a2 = 2 and
a3 = 4, since a1 > a2 and a2 < a4 the
order isn't valid, hence the answer is
No.
Your Task:

Complete the function processQueries() which takes the array, size of array queries and number of queries as parameter. It should return a vector/ArrayList/array (depending upon language cpp/Java/Python) of boolean values, true if the subarray is in mountain form, false otherwise. The driver code will print "Yes" if the returned value is true, otherwise "No".

Expected Time Complexity: O(N + Q).
Expected Auxiliary Space: O(N).

Constraints:
1 <= N, Q <= 105
1 <= a[i] <= 106, for each valid i
0 <= L <= R <= N-1

4. Stack using two queues

Implement a Stack using two queues q1 and q2.

Example 1:
Input:
push(2)
push(3)
pop()
push(4)
pop()
Output: 3 4
Explanation:
push(2) the stack will be {2}
push(3) the stack will be {2 3}
pop() poped element will be 3 the
stack will be {2}
push(4) the stack will be {2 4}
pop() poped element will be 4
Example 2:

Input:
push(2)
pop()
pop()
push(3)
Output: 2 -1
Your Task:

Since this is a function problem, you don't need to take inputs. You are required to complete the two methods push() which takes an integer 'x' as input denoting the element to be pushed into the stack and pop() which returns the integer poped out from the stack(-1 if the stack is empty).

Expected Time Complexity: O(1) for push() and O(N) for pop() (or vice-versa).
Expected Auxiliary Space: O(1) for both push() and pop().

Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

1. Rotate by 90 degree
   Basic Accuracy: 62.34% Submissions: 6532 Points: 1

Given a square matrix[][] of size N x N. The task is to rotate it by 90 degrees in an anti-clockwise direction without using any extra space.

Example 1:

Input:
N = 3
matrix[][] = [[1 2 3],
[4 5 6],
[7 8 9]]
Output:
3 6 9
2 5 8
1 4 7

Your Task:
You only need to implement the given function rotate(). Do not read input, instead use the arguments given in the function.

Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 50
1 <= matrix[][] <= 100

6. Unique rows in boolean matrix
   Easy Accuracy: 39.61% Submissions: 8416 Points: 2
   Given a binary matrix your task is to find all unique rows of the given matrix.

Example 1:

Input:
row = 3, col = 4
M[][] = {{1 1 0 1},{1 0 0 1},{1 1 0 1}}
Output: 1 1 0 1 $1 0 0 1 $
Explanation: Above the matrix of size 3x4
looks like
1 1 0 1
1 0 0 1
1 1 0 1
The two unique rows are 1 1 0 1 and
1 0 0 1 .
Your Task:
You only need to implement the given function uniqueRow(). The function takes three arguments the first argument is a matrix M and the next two arguments are row and col denoting the rows and columns of the matrix. The function should return the list of the unique row of the martrix. Do not read input, instead use the arguments given in the function.

Note: The drivers code print the rows "$" separated.

Expected Time Complexity: O(row * col)
Expected Auxiliary Space: O(row * col)

Constraints:
1<=row,col<=40
0<=M[][]<=1

Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. Each house has a[i] amount of money present in it.

Example 1:

Input:
n = 6
a[] = {5,5,10,100,10,5}
Output: 110
Explanation: 5+100+5=110
Example 2:

Input:
n = 3
a[] = {1,2,3}
Output: 4
Explanation: 1+3=4
Your Task:
Complete the function FindMaxSum() which takes an array arr[] and n as input which returns the maximum money he can get following the rules

Expected Time Complexity: O(N).
Expected Space Complexity: O(N).

Constraints:
1 <= n <= 104
1 <= a[i] <= 104

28. Binary Array Sorting

Basic Accuracy: 51.29% Submissions: 12940 Points: 1
Given a binary array A[] of size N. The task is to arrange the array in increasing order.

Note: The binary array contains only 0 and 1.

Example 1:

Input:
N = 5
A[] = {1,0,1,1,0}
Output: 0 0 1 1 1
Example 2:

Input:
N = 10
A[] = {1,0,1,1,1,1,1,0,0,0}
Output: 0 0 0 0 1 1 1 1 1 1
Your Task:
Complete the function SortBinaryArray() which takes given array as input and returns the sorted array.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Challenge: Try doing it in one pass.

Constraints:
1 <= N <= 106
0 <= A[i] <= 1

Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.

Example 1:

Input:
LinkedList: 1->2->3->4->5
Output: 3
Explanation:
Middle of linked list is 3.
Example 2:

Input:
LinkedList: 2->4->6->7->5->1
Output: 7
Explanation:
Middle of linked list is 7.
Your Task:
The task is to complete the function getMiddle() which takes a head reference as the only argument and should return the data at the middle node of the linked list.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 5000

26. Union of Two Sorted Arrays

Easy Accuracy: 46.19% Submissions: 20148 Points: 2
Union of two arrays can be defined as the common and distinct elements in the two arrays.
Given two sorted arrays of size N and M respectively, find their union.

Example 1:

Input:
N = 5, arr1[] = {1, 2, 3, 4, 5}
M = 3, arr2 [] = {1, 2, 3}
Output: 1 2 3 4 5
Explanation: Distinct elements including
both the arrays are: 1 2 3 4 5.

Example 2:

Input:
N = 5, arr1[] = {2, 2, 3, 4, 5}
M = 5, arr2[] = {1, 1, 2, 3, 4}
Output: 1 2 3 4 5
Explanation: Distinct elements including
both the arrays are: 1 2 3 4 5.

Example 3:

Input:
N = 5, arr1[] = {1, 1, 1, 1, 1}
M = 5, arr2[] = {2, 2, 2, 2, 2}
Output: 1 2
Explanation: Distinct elements including
both the arrays are: 1 2.

Your Task:
You do not need to read input or print anything. Complete the function findUnion() that takes two arrays arr1[], arr2[], and their size N and M as input parameters and returns a list containing the union of the two arrays.

Expected Time Complexity: O(N+M).
Expected Auxiliary Space: O(N+M).

Constraints:
1 <= N, M <= 105
1 <= arr[i], brr[i] <= 106

6. Implement Atoi
   Medium Accuracy: 32.9% Submissions: 57463 Points: 4
   Your task is to implement the function atoi. The function takes a string(str) as argument and converts it to an integer and returns it.

Example 1:

Input:
str = 123
Output: 123

Example 2:

Input:
str = 21a
Output: -1
Explanation: Output is -1 as all
characters are not digit only.
Your Task:
Complete the function atoi() which takes a string as input parameter and returns integer value of it. if the input string is not a numerical string then returns 1..

Expected Time Complexity: O(|S|), |S| = length of string S.
Expected Auxiliary Space: O(1)

Constraints:
1<=length of (s,x)<=10

Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

5. Search in a row-column sorted Matrix
   Easy Accuracy: 59.73% Submissions: 8056 Points: 2
   Given a matrix of size n x m, where every row and column is sorted in increasing order, and a number x. Find whether element x is present in the matrix or not.

Example 1:

Input:
n = 3, m = 3, x = 62
matrix[][] = {{ 3, 30, 38},
{36, 43, 60},
{40, 51, 69}}
Output: 0
Explanation:
62 is not present in the matrix,
so output is 0.
Example 2:

Input:
n = 1, m = 6, x = 55
matrix[][] = {{18, 21, 27, 38, 55, 67}}
Output: 1
Explanation: 55 is present in the matrix.

Your Task:
You don't need to read input or print anything. Complete the function search() that takes n, m, x, and matrix[][] as input parameters and returns a boolean value. True if x is present in the matrix and false if it is not present.

Expected Time Complexity: O(N + M)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N, M <= 1000
1 <= mat[][] <= 105
1 <= X <= 1000

3. Boundary traversal of matrix
   Easy Accuracy: 45.05% Submissions: 9917 Points: 2

You are given a matrix of dimensions n x m. The task is to perform boundary traversal on the matrix in a clockwise manner.

Example 1:

Input:
n = 4, m = 4
matrix[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15,16}}
Output: 1 2 3 4 8 12 16 15 14 13 9 5
Explanation:
The matrix is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
The boundary traversal is:
1 2 3 4 8 12 16 15 14 13 9 5

Example 2:

Input:
n = 3, m = 4
matrrix[][] = {{12, 11, 10, 9},
{8, 7, 6, 5},
{4, 3, 2, 1}}
Output: 12 11 10 9 5 1 2 3 4 8

Your Task:
Complete the function boundaryTraversal() that takes matrix, n and m as input parameters and returns the list of integers that form the boundary traversal of the matrix in a clockwise manner.

Expected Time Complexity: O(N + M)
Expected Auxiliary Space: O(1)

Constraints:
1 <= n, m<= 100
0 <= matrixi <= 1000

Given an array of 0s and 1s. Find the length of the largest subarray with equal number of 0s and 1s.

Example 1:

Input:
N = 4
A[] = {0,1,0,1}
Output: 4
Explanation: The array from index [0...3]
contains equal number of 0's and 1's.
Thus maximum length of subarray having
equal number of 0's and 1's is 4.
Example 2:

Input:
N = 5
A[] = {0,0,1,0,0}
Output: 2
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxLen() which takes the array arr[] and the size of the array as inputs and returns the length of the largest subarray with equal number of 0s and 1s.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
1 <= N <= 105
0 <= A[] <= 1

8. Positive Negative Pair
   Easy Accuracy: 33.14% Submissions: 3386 Points: 2
   Given an array of distinct integers, find all the pairs having both negative and positive values of a number in the array.

Example 1:

Input:
N = 8
arr[] = {1,3,6,-2,-1,-3,2,7}
Output: -1 1 -3 3 -2 2
Explanation: 1, 3 and 2 are present
pairwirse postive and negative. 6 and
7 have no pair.

Example 2:

Input:
N = 3
arr[] = {3,2,1}
Output: 0
Explanation: No such pair exists so the
output is 0.

Your Task:
You do not need to read input or print anything. Complete the function findPairs() which takes the array A[] and the size of the array, N, as input parameters and returns a list of integers denoting the pairs. The pair that appears first in A[] should appear first in the returning list and within the pair the negative integer should appear before positive integer. Return an empty integer list if no such pair exists.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 106
-106 <= arr[i] <= 106

Write a program to implement a Stack using Array. Your task is to use the class as shown in the comments in the code editor and complete the functions push() and pop() to implement a stack.

Example 1:

Input:
push(2)
push(3)
pop()
push(4)
pop()
Output: 3, 4
Explanation:
push(2) the stack will be {2}
push(3) the stack will be {2 3}
pop() poped element will be 3,
the stack will be {2}
push(4) the stack will be {2 4}
pop() poped element will be 4
Example 2:

Input:
pop()
push(4)
push(5)
pop()
Output: -1, 5
Your Task:
You are required to complete two methods push() and pop(). The push() method takes one argument, an integer 'x' to be pushed into the stack and pop() which returns an integer present at the top and popped out from the stack. If the stack is empty then return -1 from the pop() method.

Expected Time Complexity : O(1) for both push() and pop().
Expected Auixilliary Space : O(1) for both push() and pop().

Constraints:
1 <= Q <= 100
1 <= x <= 100

Given a singly linked list of size N. The task is to rotate the linked list counter-clockwise by k nodes, where k is a given positive integer smaller than or equal to length of the linked list.

Example 1:

Input:
N = 5
value[] = {2, 4, 7, 8, 9}
k = 3
Output: 8 9 2 4 7
Explanation:
Rotate 1: 4 -> 7 -> 8 -> 9 -> 2
Rotate 2: 7 -> 8 -> 9 -> 2 -> 4
Rotate 3: 8 -> 9 -> 2 -> 4 -> 7
Example 2:

Input:
N = 8
value[] = {1, 2, 3, 4, 5, 6, 7, 8}
k = 4
Output: 5 6 7 8 1 2 3 4

Your Task:
You don't need to read input or print anything. Your task is to complete the function rotate() which takes a head reference as the first argument and k as the second argument, and returns the head of the rotated linked list.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 103
1 <= k <= N

Container With Most Water
Medium Accuracy: 49.05% Submissions: 2388 Points: 4
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 is at (i, ai) and (i,0). Find two lines, which together with x-axis forms a container, such that it contains the most water.

Example 1:

Input:
N = 4
a[] = {1,5,4,3}
Output: 6
Explanation: 5 and 3 are distance 2 apart.
So the size of the base = 2. Height of
container = min(5, 3) = 3. So total area
= 3 * 2 = 6.
Example 2:

Input:
N = 5
a[] = {3,1,2,4,5}
Output: 12
Explanation: 5 and 3 are distance 4 apart.
So the size of the base = 4. Height of
container = min(5, 3) = 3. So total area
= 4 * 3 = 12.
Your Task :
You only need to implement the given function maxArea. Do not read input, instead use the arguments given in the function and return the desired output.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
2<=N<=105
1<=A[i]<=100

27. Intersection of two arrays

Basic Accuracy: 39.09% Submissions: 8377 Points: 1
Given two arrays A and B respectively of size N and M, the task is to print the count of elements in the intersection (or common elements) of the two arrays.

For this question, the intersection of two arrays can be defined as the set containing distinct common elements between the two arrays.

Example 1:

Input:
5 3
89 24 75 11 23
89 2 4

Output:
1

Explanation:
89 is the only element
in the intersection of two arrays.
Example 2:

Input:
6 5
1 2 3 4 5 6
3 4 5 6 7

Output:
4

Explanation:
3 4 5 and 6 are the elements
in the intersection of two arrays.
Your Task:
The task is to complete the function NumberofElementsInIntersection() which takes 4 inputs ie- array a, array b, n which is the size of array a, m which is the size of array b. The function should return the count of the number of elements in the intersection.

Expected Time Complexity: O(N + M).
Expected Auxiliary Space: O(min(N,M)).

Constraints:
1 ≤ N, M ≤ 105
1 ≤ A[i], B[i] ≤ 105

5. Special Stack

Design a data-structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. Your task is to complete all the functions, using stack data-Structure.

Example 1:

Input:
Stack: 18 19 29 15 16
Output: 15
Explanation:
The minimum element of the stack is 15.

Your Task:
Since this is a function problem, you don't need to take inputs. You just have to complete 5 functions, push() which takes the stack and an integer x as input and pushes it into the stack; pop() which takes the stack as input and pops out the topmost element from the stack; isEmpty() which takes the stack as input and returns true/false depending upon whether the stack is empty or not; isFull() which takes the stack and the size of the stack as input and returns true/false depending upon whether the stack is full or not (depending upon the
given size); getMin() which takes the stack as input and returns the minimum element of the stack.
Note: The output of the code will be the value returned by getMin() function.

Expected Time Complexity: O(N) for getMin, O(1) for remaining all 4 functions.
Expected Auxiliary Space: O(1) for all the 5 functions.

Constraints:
1 ≤ N ≤ 104

4. Roman Number to Integer
   Easy Accuracy: 38.75% Submissions: 4432 Points: 2
   Given a string in roman no format (s) your task is to convert it to an integer . Various symbols and their values are given below.
   I 1
   V 5
   X 10
   L 50
   C 100
   D 500
   M 1000

Example 1:

Input:
s = V
Output: 5
Example 2:

Input:
s = III
Output: 3
Your Task:
Complete the function romanToDecimal() which takes an string as input parameter and returns the equivalent decimal number.

Expected Time Complexity: O(|S|), |S| = length of string S.
Expected Auxiliary Space: O(1)

Constraints:
1<=roman no range<=3999

11. Relative Sorting
    Medium Accuracy: 48.71% Submissions: 3750 Points: 4
    Given two integer arrays. Sort the first array such that all the relative positions of the elements in the first array are the same as the elements in the second array.
    See example for better understanding.

Example 1:

Input:
N = 11, M = 4
A1[] = {2,1,2,5,7,1,9,3,6,8,8}
A2[] = {2,1,8,3}
Output: 2 2 1 1 8 8 3 5 6 7 9
Explanation: Array elements of A1[] are
sorted according to A2[]. So 2 comes first
then 1 comes, then comes 8, then finally 3
comes, now we append remaining elements in
sorted order.
Example 2:

Input:
N = 11, M = 4
A1[] = {2,1,2,5,7,1,9,3,6,8,8}
A2[] = {99,22,444,56}
Output: 1 1 2 2 3 5 6 7 8 8 9
Explanation: No A2 elements are in A1
so we cannot sort A1 according to A2.
Hence we sort the elements in
non-decreasing order.
Input:
The first line of input contains the number of test cases. For each testcase, the first line of input contains the length of arrays N and M and the next two lines contain N and M elements respectively.

Output:
For each testcase, in a new line, print the elements of A1 sorted relatively according to A2.

Your Task:
You don't need to read input or print anything. Your task is to complete the function sortA1ByA2() which takes the array A1[], array A2[] and their respective size N and M as inputs and sorts the array A1[] such that the relative positions of the elements in A1[] are same as the elements in A2[]. For the elements not present in A2[] but in A1[], it appends them at the last in increasing order.

Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).

Constraints:
1 ≤ N,M ≤ 106
1 ≤ A1[], A2[] <= 106

4. Find nth element of spiral matrix

Easy Accuracy: 35.1% Submissions: 4824 Points: 2
Given a matrix with n rows and m columns. Your task is to find the kth element which is obtained while traversing the matrix spirally. You need to complete the method findK which takes four arguments the first argument is the matrix A and the next two arguments will be n and m denoting the size of the matrix A and then the forth argument is an integer k denoting the kth element . The function will return the kth element obtained while traversing the matrix spirally.

Example 1:

Input:
n = 3, m = 3, k = 4
A[][] = [[1 2 3],
[4 5 6],
[7 8 9]]
Output: 6
Explanation: The matrix above will look
like
1 2 3
4 5 6
7 8 9
and the 4th element in spiral fashion
will be 6 .
Your Task:
You only need to implement the given function findK(). Do not read input, instead use the arguments given in the function. Return the K'th element obtained by traversing matrix spirally.

Expected Time Complexity: O(NM)
Expected Auxiliary Space: O(NM)

Constraints:
1<=n,m<=20
1<=k<=n*m

Given a sorted singly linked list and a data, your task is to insert the data in the linked list in a sorted way i.e. order of the list doesn't change.

Example 1:

Input:
LinkedList: 25->36->47->58->69->80
data: 19
Output: 19 25 36 47 58 69 80
Example 2:

Input:
LinkedList: 50->100
data: 75
Output: 50 75 100
Your Task:
The task is to complete the function sortedInsert() which should insert the element in sorted Linked List and return the head of the linked list

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 104
-99999 <= A[i] <= 99999, for each valid i

Count distinct elements in every window
Easy Accuracy: 44.16% Submissions: 54704 Points: 2
Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array.

Example 1:

Input:
N = 7, K = 4
A[] = {1,2,1,3,4,2,3}
Output: 3 4 4 3
Explanation: Window 1 of size k = 4 is
1 2 1 3. Number of distinct elements in
this window are 3.
Window 2 of size k = 4 is 2 1 3 4. Number
of distinct elements in this window are 4.
Window 3 of size k = 4 is 1 3 4 2. Number
of distinct elements in this window are 4.
Window 4 of size k = 4 is 3 4 2 3. Number
of distinct elements in this window are 3.
Example 2:

Input:
N = 3, K = 2
A[] = {4,1,1}
Output: 2 1
Your Task:
Your task is to complete the function countDistinct() which takes the array A[], the size of the array(N) and the window size(K) as inputs and returns an array containing the count of distinct elements in every contiguous window of size K in the array A[].

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
1 <= N <= K <= 105
1 <= A[i] <= 105 , for each valid i

9. Linear Probing in Hashing

Easy Accuracy: 35.16% Submissions: 9115 Points: 2
Linear probing is a collision handling technique in hashing. Linear probing says that whenever a collision occurs, search for the immediate next position.

Given an array of integers and a hash table size. Fill the array elements into a hash table using Linear Probing to handle collisions.

Example 1:

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {4,14,24,44}
Output:
-1 -1 -1 -1 4 14 24 44 -1 -1
Explanation: 4%10=4. So put 4 in
hashtable[4].Now, 14%10=4, but
hashtable[4] is alreadyfilled so put
14 in the next slot and so on.
Example 2:

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {9,99,999,9999}
Output:
99 999 9999 -1 -1 -1 -1 -1 -1 9
Explanation: 9%10=9. So put 9 in
hashtable[9]. Now, 99%10=9, but
hashtable[9] is already filled so
put 99 in the (99+1)%10 =0 slot so
99 goes into hashtable[0] and so on.
Your Task:
You don't need to read input or print anything. Your task is to complete the function linearProbing() which takes as input a empty hash table (hash), the hash table size (hashSize), an integers array arr[] and its size N and inserts all the elements of the array arr[] into the given hash table. The empty cells of the hash table are to be given a value of -1. Also, if there's no more space to insert a new element, just drop that element.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= hashSize <= 100
1 <= sizeOfArray <= 100
0 <= Array[] <= 105

vector<int> linearProbing(int hashSize, int arr[], int N)
{
    //Your code here
}

7. First Non Repeating Character
   Easy Accuracy: 55.68% Submissions: 1107 Points: 2
   Given a string S consisting of lowercase Latin Letters. Find the first non-repeating character in S.

Example 1:

Input:
N = 5
S = hello
Output: h
Explanation: 'h', 'e' and 'o' are the
non-repeating characters out of which
'h' has the least index.
Example 2:

Input:
N = 12
S = zxvczbtxyzvy
Output: c
Explanation: 'c', 'b' and 't' are the
non-repeating characters out of which
'c' has the least index.
Your Task:
You don't need to read input or print anything. Your task is to complete the function find() which takes the string S as its input and returns the first non-repeating character present in S or -1 if there is no non-repeating character. Since the return type is a string we first need to change the character into a string.

Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).

Constraints:
1 <= |S| <= 104

Given a linked list of N nodes. The task is to reverse this list.

Example 1:

Input:
LinkedList: 1->2->3->4->5->6
Output: 6 5 4 3 2 1
Explanation: After reversing the list,
elements are 6->5->4->3->2->1.
Example 2:

Input:
LinkedList: 2->7->8->9->10
Output: 10 9 8 7 2
Explanation: After reversing the list,
elements are 10->9->8->7->2.
Your Task:
The task is to complete the function reverseList() with head reference as the only argument and should return new head after reversing the list.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 104

3. Convert to Roman No
   Basic Accuracy: 49.9% Submissions: 13739 Points: 1
   Given an integer n, your task is to complete the function convertToRoman which prints the corresponding roman number of n. Various symbols and their values are given below.

I 1
V 5
X 10
L 50
C 100
D 500
M 1000

Example 1:

Input:
n = 5
Output: V

Example 2:

Input:
n = 3
Output: III

Your Task:
Complete the function convertToRoman() which takes an integer N as input parameter and returns the equivalent roman.

Expected Time Complexity: O(log10N)
Expected Auxiliary Space: O(log10N * 10)

Constraints:
1<=n<=3999

4. Match specific pattern
   Easy Accuracy: 51.27% Submissions: 10277 Points: 2
   Given a dictionary of words and a pattern. Every character in the pattern is uniquely mapped to a character in the dictionary. Find all such words in the dictionary that match the given pattern.

Example 1:

Input:
N = 4
dict[] = {abb,abc,xyz,xyy}
pattern = foo
Output: abb xyy
Explanation: xyy and abb have the same
character at index 1 and 2 like the
pattern.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMatchedWords() which takes an array of strings dict[] consisting of the words in the dictionary and a string, Pattern and returns an array of strings consisting of all the words in the dict[] that match the given Pattern in lexicographical order.

Expected Time Complexity: O(N*K) (where K is the length of the pattern).
Expected Auxiliary Space: O(N).

Constraints:
1 <= N <= 10

Given a singly linked list, delete middle of the linked list. For example, if given linked list is 1->2->3->4->5 then linked list should be modified to 1->2->4->5.
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL or has 1 node, then it should return NULL

Example 1:

Input:
LinkedList: 1->2->3->4->5
Output: 1 2 4 5
Example 2:

Input:
LinkedList: 2->4->6->7->5->1
Output: 2 4 6 5 1
Your Task:
The task is to complete the function deleteMid() which should delete the middle element from the linked list and return the head of the modified linked list. If the linked list is empty then it should return NULL.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 1000
1 <= value <= 1000

21. Overlapping Intervals

Medium Accuracy: 34.88% Submissions: 4559 Points: 4
Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

Example 1:

Input:
N = 4
Intervals = {(1,3),(2,4),(6,8),(9,10)}
Output: 1 4 6 8 9 10
Explanation: Given intervals: [1,3],[2,4]
[6,8],[9,10], we have only two overlapping
intervals here,[1,3] and [2,4]. Therefore
we will merge these two and return [1,4],
[6,8], [9,10].
Example 2:

Input:
N = 4
Intervals = {(6,8),(1,9),(2,4),(4,7)}
Output: 1 9
Your Task:
Complete the function overlappedInterval() that takes the list of pairs and N as input parameters and returns sorted list of pairs of intervals after merging.

Expected Time Complexity: O(N*Log(N) ).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ N ≤ 100
0 ≤ x ≤ y ≤ 1000

22. Three Sum Closest

Easy Accuracy: 23.97% Submissions: 5680 Points: 2
Given an array Arr of N numbers and another number target, find three integers in the array such that the sum is closest to target. Return the sum of the three integers.

Example 1:

Input:
N = 6, target = 2
A[] = {-7,9,8,3,1,1}
Output: 2
Explanation: There is one triplet with sum
2 in the array. Triplet elements are -7,8,
1 whose sum is 2.
Example 2:

Input:
N = 4, target = 13
A[] = {5,2,7,5}
Output: 14
Explanation: There is one triplet with sum
12 and other with sum 14 in the array.
Triplet elements are 5, 2, 5 and 2, 7, 5
respectively. Since abs(13-12) ==
abs(13-14) maximum triplet sum will be
preferred i.e 14.
Your Task:
Complete threeSumClosest() function and return the expected answer.

NOTE: If their exists more than one answer then return the maximum sum.

Expected Time Complexity: O(N*N).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ N ≤ 103
-105 ≤ A[i] ≤ 105
1 ≤ target ≤ 105

2. Implement Stack using Linked List
   Basic Accuracy: 49.96% Submissions: 52083 Points: 1
   Let's give it a try! You have a linked list and you have to implement the functionalities push and pop of stack using this given linked list. Your task is to use the class as shown in the comments in the code editor and complete the functions push() and pop() to implement a stack.

Example 1:

Input:
push(2)
push(3)
pop()
push(4)
pop()
Output: 3 4
Explanation:
push(2) the stack will be {2}
push(3) the stack will be {2 3}
pop() poped element will be 3,
the stack will be {2}
push(4) the stack will be {2 4}
pop() poped element will be 4
Example 2:

Input:
pop()
push(4)
push(5)
pop()
Output: -1 5
Your Task: You are required to complete two methods push() and pop(). The push() method takes one argument, an integer 'x' to be pushed into the stack and pop() which returns an integer present at the top and popped out from the stack. If the stack is empty then return -1 from the pop() method.

Expected Time Complexity: O(1) for both push() and pop().
Expected Auxiliary Space: O(1) for both push() and pop().

Constraints:
1 <= Q <= 100
1 <= x <= 100

7. Binary String
   Basic Accuracy: 51.59% Submissions: 13140 Points: 1
   Given a binary string S. The task is to count the number of substrings that start and end with 1. For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.

Example 1:

Input:
N = 4
S = 1111
Output: 6
Explanation: There are 6 substrings from
the given string. They are 11, 11, 11,
111, 111, 1111.
Example 2:

Input:
N = 5
S = 01101
Output: 3
Explanation: There 3 substrings from the
given string. They are 11, 101, 1101.
Your Task:
The task is to complete the function binarySubstring() which takes the length of binary string n and a binary string a as input parameter and counts the number of substrings starting and ending with 1 and returns the count.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ |S| ≤ 104

Given a matrix M of n*n size, the task is to complete the function which prints its elements in diagonal pattern as depicted below.

Example 1:

Input:
N = 3
mat[][] = {{1 2 3},{4 5 6},{7 8 9}}
Output: 1 2 4 7 5 3 6 8 9
Example 2:

Input:
N = 2
mat[][] = {{1 2},{3 4}}
Output: 1 2 3 4
Your Task:
You only need to implement the given function matrixDiagonally() which returns a list containing the matrix diagonally.. Do not read input, instead use the arguments given in the function. Print the elements in Matrix in diagonal pattern.

Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
0<=N<=20

Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

5. Implement strstr
   Basic Accuracy: 50.08% Submissions: 50457 Points: 1
   Your task is to implement the function strstr. The function takes two strings as arguments (s,x) and locates the occurrence of the string x in the string s. The function returns and integer denoting the first occurrence of the string x in s (0 based indexing).

Example 1:

Input:
s = GeeksForGeeks, x = Fr
Output: -1
Explanation: Fr is not present in the
string GeeksForGeeks as substring.

Example 2:

Input:
s = GeeksForGeeks, x = For
Output: 5
Explanation: For is present as substring
in GeeksForGeeks from index 5 (0 based
indexing).

Your Task:
You don't have to take any input. Just complete the strstr() function which takes two strings str, target as an input parameter. The function returns -1 if no match if found else it returns an integer denoting the first occurrence of the x in the string s.

Expected Time Complexity: O(|s|*|x|)
Expected Auxiliary Space: O(1)

Note : Try to solve the question in constant space complexity.

Constraints:
1 <= |s|,|x| <= 1000

23. Max Circular Subarray Sum

Hard Accuracy: 45.16% Submissions: 13635 Points: 8
Given an array arr[] of N integers arranged in a circular fashion. Your task is to find the maximum contiguous subarray sum.

Example 1:

Input:
N = 7
arr[] = {8,-8,9,-9,10,-11,12}
Output: 22
Explanation: Starting from the last
element of the array, i.e, 12, and
moving in a circular fashion, we
have max subarray as 12, 8, -8, 9,
-9, 10, which gives maximum sum
as 22.
Example 2:

Input:
N = 8
arr[] = {10,-3,-4,7,6,5,-4,-1}
Output: 23
Explanation: Sum of the circular
subarray with maximum sum is 23
Your Task:
The task is to complete the function circularSubarraySum() which returns a sum of the circular subarray with maximum sum.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 106
-106 <= Arr[i] <= 106

2. Spirally traversing a matrix
   Medium Accuracy: 48.39% Submissions: 12583 Points: 4

Given a matrix of size R*C. Traverse the matrix in spiral form.

Example 1:

Input:
R = 4, C = 4
matrix[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15,16}}
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Explanation:

Example 2:

Input:
R = 3, C = 4
matrix[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}}
Output:
1 2 3 4 8 12 11 10 9 5 6 7
Explanation:
Applying same technique as shown above,
output for the 2nd testcase will be
1 2 3 4 8 12 11 10 9 5 6 7.

Your Task:
You dont need to read input or print anything. Complete the function spirallyTraverse() that takes matrix, R and C as input parameters and returns a list of integers denoting the spiral traversal of matrix.

Expected Time Complexity: O(RC)
Expected Auxiliary Space: O(RC)

Constraints:
2 <= R, C <= 100
0 <= matrixi <= 100

2. Print all possible strings
   Basic Accuracy: 29.93% Submissions: 5989 Points: 1
   Given a string str your task is to complete the function spaceString which takes only one argument the string str and finds all possible strings that can be made by placing spaces (zero or one) in between them.

For eg . for the string abc all valid strings will be
abc
ab c
a bc
a b c

Example 1:

Input:
str = abc
Output: abc$ab c$a bc$a b c$
Example 2:

Input:
str = xy
Output: xy$x y$

Your Task:
Complete the function spaceString() which takes a character array as an input parameter and returns list of all possible answers. The driver code will print the all possible answer '$' separated

Expected Time Complexity: O(N * 2N)
Expected Auxiliary Space: O(N)

Constraints:
1<= length of string str <=10

Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Smallest window in a string containing all the characters of another string
Medium Accuracy: 37.46% Submissions: 9210 Points: 4
Given two strings. Find the smallest window in the first string consisting of all the characters of the second string.

Example 1:

Input:
S = timetopractice
P = toc
Output: toprac
Explanation: toprac is the smallest
subset in which toc can be found.
Example 2:

Input:
S = zoomlazapzo
P = oza
Output: apzo
Explanation: To find oza in the
zoomlazapzo the smallest subset is
apzo.
Your Task:
You don't need to read input or print anything. Your task is to complete the function smallestWindow() which takes two string S and P as inputs and returns the smallest window in string S having all the characters of the string P. In case there are multiple such windows of same length, return the one with the least starting index. Return "-1" in case there's no such window present.

Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)

Constraints:
1 <= |S|, |P| <= 1000

Given an array having both positive and negative integers. The task is to compute the length of the largest subarray with sum 0.

Example 1:

Input:
N = 8
A[] = {15,-2,2,-8,1,7,10,23}
Output: 5
Explanation: The largest subarray with
sum 0 will be -2 2 -8 1 7.
Your Task:
You just have to complete the function maxLen() which takes two arguments an array A and n, where n is the size of the array A and returns the length of the largest subarray with 0 sum.

Expected Time Complexity: O(N*Log(N)).
Expected Auxiliary Space: O(N).

Constraints:
1 <= N <= 104
-1000 <= A[i] <= 1000, for each valid i

3. Implement two stacks in an array

Your task is to implement 2 stacks in one array efficiently.

Example 1:

Input:
push1(2)
push1(3)
push2(4)
pop1()
pop2()
pop2()

Output:
3 4 -1

Explanation:
push1(2) the stack1 will be {2}
push1(3) the stack1 will be {2,3}
push2(4) the stack2 will be {4}
pop1() the poped element will be 3
from stack1 and stack1 will be {2}
pop2() the poped element will be 4
from stack2 and now stack2 is empty
pop2() the stack2 is now empty hence -1 .

Your Task:
You don't need to read input or print anything. You are required to complete the 4 methods push1, push2 which takes one argument an integer 'x' to be pushed into stack one and two and pop1, pop2 which returns the integer poped out from stack one and two. If no integer is present in the array return -1.

Expected Time Complexity: O(1) for all the four methods.
Expected Auxiliary Space: O(1) for all the four methods.

Constraints:
1 <= Number of queries <= 100
1 <= value in the stack <= 100
The sum of elements in both the stacks < size of the given array

9. Sorted subsequence of size 3
   Easy Accuracy: 45.69% Submissions: 17170 Points: 2
   Given an array A of N integers, find any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k.

Example 1:

Input:
N = 5
A[] = {1,2,1,1,3}
Output: 1
Explanation: a sub-sequence 1 2 3 exist.
Example 2:

Input:
N = 3
A[] = {1,1,3}
Output: 0
Explanation: no such sub-sequence exist.
Your Task:
Your task is to complete the function find3Numbers which finds any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k. You need to return them as a vector/ArrayList/array (depending on the language cpp/Java/Python), if no such element is present then return the empty vector of size 0.

Note: The output will be 1 if the sub-sequence returned by the function is present in array A else 0. If the sub-sequence returned by the function is not in the format as mentioned then the output will be -1.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 105
1 <= A[i] <= 106, for each valid i

Given an array of positive integers and an integer. Determine whether or not there exist two elements in A whose sum is exactly equal to that integer.

Example 1:

Input:
N = 6, X = 16
A[] = {1,4,45,6,10,8}
Output: Yes
Explanation: 10 and 6 are numbers
making a pair whose sum is equal to 16.
Example 2:

Input:
N = 5, X = 10
A[] = {1,2,4,3,6}
Output: Yes
Your Task :
You don't need to read input or print anything. Your task is to complete the boolean function keypair() which takes the array A[], the size of the array (N) and another number (X) as inputs and returns true if there exists a pair in A[] that sums up to X and returns false otherwise. (THe driver code will print "Yes" if the returned values is true, otherwise "No")

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
1 ≤ N ≤ 105
1 ≤ A[i] ≤ 105
1 ≤ X ≤ 2*105

1. Anagram of String
   Basic Accuracy: 49.25% Submissions: 13995 Points: 1
   Given two strings S1 and S2 in lowercase, the task is to make them anagram. The only allowed operation is to remove a character from any string. Find the minimum number of characters to be deleted to make both the strings anagram. Two strings are called anagram of each other if one of them can be converted into another by rearranging its letters.

Example 1:

Input:
S1 = bcadeh
S2 = hea
Output: 3
Explanation: We need to remove b, c
and d from S1.
Example 2:

Input:
S1 = cddgk
S2 = gcd
Output: 2
Explanation: We need to remove d and
k from S1.
Your Task:
Complete the function remAnagram() which takes two strings S1, S2 as input parameter, and returns minimum characters needs to be deleted.

Expected Time Complexity: O(max(|S1|, |S2|)), where |S| = length of string S.
Expected Auxiliary Space: O(26)

Constraints:
1 <= |S1|, |S2| <= 105

10. Quadratic Probing in Hashing
    Easy Accuracy: 52.65% Submissions: 4337 Points: 2
    Quadratic probing is a collision handling technique in hashing. Quadratic probing says that whenever a collision occurs, search for i2 position.

Given an array of integers and a Hash table. Fill the elements of the array into the hash table by using Quadratic Probing in case of collisions.

Example 1:

Input:
hashSize = 11
N = 4
Array[] = {21,10,32,43}
Output:
10 -1 -1 32 -1 -1 -1 -1 43 -1 2
Explanation: 21%11=10 so 21 goes into
hashTable[10] position. 10%11=10.
hashTable[10] is already filled so we try
for (10+12)%11=0 position. hashTable[0]
is empty so we put 10 there. 32%11=10.
hashTable[10] is filled. We try
(32+12)%11=0. But hashTable[0] is also
already filled. We try (32+22)%11=3.
hashTable[3] is empty so we put 32 in
hashTable[3] position. 43 uses
(43+33)%11=8. We put it in hashTable[8].
Example 2:

Input:
hashSize = 11
N = 4
Array[] = {880,995,647,172 }
Output:
880 -1 -1 -1 -1 995 -1 172 -1 647 -1
Explanation: Using the similar approach
as used in above explanation we will get
the output like
880 -1 -1 -1 -1 995 -1 172 -1 647 -1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function QuadraticProbing() which takes the hash table hash[], the hash table size hashSize, an array arr[] and the size of the array N as inputs and inserts all the elements of the array arr[] into the hash table using Quadratic Probing as a collision handling technique.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
2 <= hashSize (prime) <= 97
1 <= N < hashSize*0.5
0 <= Array[] <= 105

Note:
All the positions that are unoccupied are denoted by -1 in the hash table.
An empty slot can only be found if load factor < 0.5 and hash table size is a prime number.
The given testcases satisfy the above condition so you can assume that an empty slot is always reachable.

void QuadraticProbing(vector <int>&hash, int hashSize, int arr[], int N)
{
    //Your code here
}