Problem Of The Day
“Alternate Vowel and Consonant String”

Solve the problem to win points

Given a string S of lowercase english characters. Rearrange characters of the given string such that the vowels and consonants occupy alternate positions and the string so formed should be lexicographically (alphabetically) smallest.
Note: Vowels are 'a', 'e', 'i', 'o' and 'u'.

Example 1:
Input:
S = "aeroplane"
Output: alanepero
Explanation: alanepero
The vowels and cosonants are arranged
alternatively with vowels shown in bold.
Also, there's no lexicographically smaller
string possible with required conditions.

Example 2:
Input:
S = "mississippi"
Output: -1
Explanation: The number of vowels is 4
whereas the number of consonants is 7.
Hence, there's no way to arrange the
vowels and consonants alternatively.

Your Task:
You don't need to read input or print anything. Your task is to complete the function rearrange() which takes the string S and its size N as inputs and returns the modified string as stated in the description. If such a modification is not possible, return the string "-1".

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/alternate-vowel-and-consonant-string2939/1

Must Do DSA Topics Day 46
Queue
Level order traversal in spiral form : Given a Binary Tree, the task is to print the Level order traversal of the Binary Tree in spiral form i.e, alternate order.
Learn more : http://bit.ly/3Fo9wI1

Sliding Window Maximum (Maximum of all subarrays of size k) : Given an array and an integer K, find the maximum for each and every contiguous subarray of size K.
Learn more : Given an array and an integer K, find the maximum for each and every contiguous subarray of size K.
Learn more : http://bit.ly/3H8zGQk

Find the first circular tour that visits all petrol pumps : Given information about N petrol pumps (say arr[]) that are present in a circular path. The information consists of the distance of the next petrol pump from the current one (in arr[i][1]) and the amount of petrol stored in that petrol pump (in arr[i][0]).
Learn more : http://bit.ly/3H8loPK

Problem Of The Day
“Shortest Path by Removing K walls”

Solve the problem to win points

Given a 2-D binary matrix of size n*m, where 0 represents an empty space while 1 represents a wall you cannot walk through. You are also given an integer k.
You can walk up, down, left, or right. Given that you can remove up to k walls, return the minimum number of steps to walk from the top left corner (0, 0) to the bottom right corner (n-1, m-1).
Note: If there is no way to walk from the top left corner to the bottom right corner, return -1.

Example 1:
Input: n = 3, m = 3, k = 1
mat = {{0, 0, 0},
{0, 0, 1},
{0, 1, 0}}
Output:
4
Explanation:
We can remove any one of the walls and
reach the bottom in 4 moves.

Example 2:
Input:
n = 2, m = 2, k = 0
mat[] = {{0, 1},
{1, 0}}
Output:
-1
Explanation:
There's no way of reaching the bottom
corner without removing any walls.

Your Task:
The task is to complete the function shotestPath() which takes three integers n, m, and k and also a matrix of size n*m as input and returns the minimum number of steps to walk from the top left corner to the bottom right corner.

Constraints:
1 ≤ n,m ≤ 50
0 ≤ k ≤ n*m
Top left and bottom right corners doesn't have 1

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/shortest-path-by-removing-k-walls/1

Must Do DSA Topics Day 47
Queue
Smallest multiple of a given number made of digits 0 and 9 only : We are given an integer N. We need to write a program to find the least positive integer X made up of only digits 9’s and 0’s, such that, X is a multiple of N.
Learn more : http://bit.ly/3XQclcl

Iterative Method to find Height of Binary Tree : The idea is to traverse level by level. Whenever move down to a level, increment height by 1 (height is initialized as 0). Count number of nodes at each level, stop traversing when the count of nodes at the next level is 0.
Learn more : http://bit.ly/3VRzYzj

Implement PriorityQueue through Comparator in Java : Priority Queue, Comparator Priority Queue is like a regular queue, but each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Learn more : http://bit.ly/3XTCsiu

Must Do DSA Topics Day 48
Queue
First negative integer in every window of size k : Given an array and a positive integer k, find the first negative integer for each window(contiguous subarray) of size k. If a window does not contain a negative integer, then print 0 for that window.
Learn more : http://bit.ly/3uqPBlw

Minimum sum of squares of character counts in a given string after removing k characters : Given a string of lowercase alphabets and a number k, the task is to print the minimum value of the string after removal of ‘k’ characters. The value of a string is defined as the sum of squares of the count of each distinct character.
Learn more : http://bit.ly/3usE5Gt

Queue based approach for first non-repeating character in a stream : Given a stream of characters and we have to find first non repeating character each time a character is inserted to the stream.
Learn more : http://bit.ly/3Fomm9p

Get access to more topics of Queue : http://bit.ly/3P2yqAm

Problem Of The Day
"Distance of nearest cell having 1"

Solve the problem to win points

Given a binary grid of n*m. Find the distance of the nearest 1 in the grid for each cell.
The distance is calculated as |i1 - i2| + |j1 - j2|, where i1, j1 are the row number and column number of the current cell, and i2, j2 are the row number and column number of the nearest cell having value 1.


Example 1:
Input: grid = {{0,1,1,0},{1,1,0,0},{0,0,1,1}}
Output: {{1,0,0,1},{0,0,1,1},{1,1,0,0}}
Explanation: The grid is-
0 1 1 0
1 1 0 0
0 0 1 1
0's at (0,0), (0,3), (1,2), (1,3), (2,0) and
(2,1) are at a distance of 1 from 1's at (0,1),
(0,2), (0,2), (2,3), (1,0) and (1,1)
respectively.

Example 2:
Input: grid = {{1,0,1},{1,1,0},{1,0,0}}
Output: {{0,1,0},{0,0,1},{0,1,2}}
Explanation: The grid is-
1 0 1
1 1 0
1 0 0
0's at (0,1), (1,2), (2,1) and (2,2) are at a
distance of 1, 1, 1 and 2 from 1's at (0,0),
(0,2), (2,0) and (1,1) respectively.

Yout Task:
You don't need to read or print anything, Your task is to complete the function nearest() which takes the grid as an input parameter and returns a matrix of the same dimensions where the value at index (i, j) in the resultant matrix signifies the minimum distance of 1 in the matrix from grid[i][j].


Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/distance-of-nearest-cell-having-1-1587115620/1

Must Do DSA Topics Day 49
Deque
Implementation of Deque using circular array : Deque or Double Ended Queue is a generalized version of the Queue data structure that allows insert and delete at both ends.
Learn more: http://bit.ly/3Y0Lbzp

Deque interface in Java : Deque interface present in java.util package is a subtype of the queue interface. The Deque is related to the double-ended queue that supports the addition or removal of elements from either end of the data structure.
Learn more : http://bit.ly/3Fu9yOE

Deque in Python : Deque (Doubly Ended Queue) in Python is implemented using the module “collections“. Deque is preferred over a list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to a list that provides O(n) time complexity.
Learn more : http://bit.ly/3iJZDLS

Must Do DSA Topics Day 50
Deque
Level order traversal in spiral form | Using Deque : Given a Binary Tree, the task is to print spiral order traversal of the given tree. For below tree, the function should print 1, 2, 3, 4, 5, 6, 7.
Learn more : http://bit.ly/3HfbiN9

Deque descending Iterator() method in Java : The descendingIterator(E e) method of Deque Interface returns an iterator over the elements in this deque in a reverse sequential order. The elements will be returned in order from last(tail) to first(head).
Learn more : http://bit.ly/3Hfbg7Z

Deque iterator() method in Java : The iterator() method of Deque Interface returns an iterator over the elements in this deque in a proper sequence. The elements will be returned in order from first (head) to last (tail). The returned iterator is a “weakly consistent” iterator.
Learn more : http://bit.ly/3FdFjui

Get access to more topics of deque : https://www.geeksforgeeks.org/tag/deque/

Problem Of The Day
"k-th smallest element in BST"

Solve the problem to win points

Given a BST and an integer K. Find the Kth Smallest element in the BST using O(1) extra space.

Example 1:

Input:
2
/ \
1 3
K = 2
Output: 2
Explanation: 2 is the 2nd smallest element in the BST

Example 2:

Input:
2
/ \
1 3
K = 5
Output: -1
Explanation: There is no 5th smallest element in the BST as the size of BST is 3

Your Task:
You don't need to read input or print anything. Your task is to complete the function KthSmallestElement() which takes the root of the BST and integer K as inputs and return the Kth smallest element in the BST, if no such element exists return -1.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/find-k-th-smallest-element-in-bst/1

Must Do DSA Topics Day 51
Tree
Handshaking Lemma and Interesting Tree Properties : Handshaking lemma is about an undirected graph. In every finite undirected graph, an even number of vertices will always have an odd degree. 
Learn more : http://bit.ly/3VYgCsl

Enumeration of Binary Trees : A Binary Tree is labeled if every node is assigned a label and a Binary Tree is unlabelled if nodes are not assigned any label.
Learn more : http://bit.ly/3BbDQmH

Insertion in a Binary Tree : Given a binary tree and a key, insert the key into the binary tree at the first position available in level order.
Learn more : http://bit.ly/3F65cfn

Must Do DSA Topics Day 52
Tree
AVL with duplicate keys : This is to augment AVL tree node to store count together with regular fields like key, left and right pointers.
Learn more : http://bit.ly/3h49s7d

Applications of tree data structure : Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure.
Learn more : http://bit.ly/3iJPv64

Applications of Minimum Spanning Tree Problem : Minimum Spanning Tree (MST) problem: Given connected graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.
Learn more : http://bit.ly/3hdMzhs

Problem Of The Day
"3 Divisors"

Solve the problem to win points

You are given a list of q queries and for every query, you are given an integer N. The task is to find how many numbers(less than or equal to N) have number of divisors exactly equal to 3.

Example 1:
Input:
q = 1
query[0] = 6
Output:
1
Explanation:
There is only one number 4 which has
exactly three divisors 1, 2 and 4 and
less than equal to 6.

Example 2:
Input:
q = 2
query[0] = 6
query[1] = 10
Output:
1
2
Explanation:
For query 1 it is covered in the
example 1.
query 2: There are two numbers 4 and 9
having exactly 3 divisors and less than
equal to 10.

Your Task:
You don't need to read input or print anything. Your task is to complete the function threeDivisors() which takes an integer q and a list of integer of size q as input parameter and returns the list containing the count of the numbers having exactly 3 divisors for each query.

Expected Time Complexity: O(q*N*log(log(N)))
Expected Auxiliary Space: O(N), where N is min(10^6,N)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/3-divisors3942/1

Must Do DSA Topics Day 53
Tree
Tree Traversals :  Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways.
Learn more : http://bit.ly/3P6FtYC

Inorder Tree Traversal without Recursion : Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.
Learn more : http://bit.ly/3VXzKXv

Inorder Tree Traversal without recursion and without stack! : Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree.
Learn more : http://bit.ly/3VSpi3o

Problem Of The Day
"Black and White"

Solve the problem to win points

Given the chessboard dimensions. Find out the number of ways we can place a black and a white Knight on this chessboard such that they cannot attack each other.

Note:
The knights have to be placed on different squares. A knight can move two squares horizontally and one square vertically (L shaped), or two squares vertically and one square horizontally (L shaped). The knights attack each other if one can reach the other in one move.

Example 1:
Input:
N = 2, M = 2
Output: 12
Explanation: There are 12 ways we can place a black and a white Knight on this chessboard such that they cannot attack each other.

Example 2:
Input:
N = 2, M = 3
Output: 26
Explanation: There are 26 ways we can place a black and a white Knight on this chessboard such that they cannot attack each other.

Your Task:
Your task is to complete the function numOfWays() which takes the chessboard dimensions N and M as inputs and returns the number of ways we can place 2 Knights on this chessboard such that they cannot attack each other. Since this number can be very large, return it modulo 109+7.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/black-and-white-1587115620/1

Must Do DSA Topics Day 54
Tree
Print Postorder traversal from given Inorder and Preorder traversals : We can print postorder traversal without constructing the tree. The idea is, root is always the first item in preorder traversal and it must be the last item in postorder traversal.
Learn more : http://bit.ly/3iEid8g

Find postorder traversal of BST from preorder traversal : An efficient approach is to find postorder traversal without constructing the tree. The idea is to traverse the given preorder array and maintain a range in which current element should lie. 
Learn more : http://bit.ly/3VXXSZY

Find all possible binary trees with given Inorder Traversal : Given an array that represents Inorder Traversal, find all possible Binary Trees with the given Inorder traversal and print their preorder traversals.
Learn more : http://bit.ly/3iMlPVS

Problem Of The Day
“Build the smallest”

Solve the problem to win points

Given a number k and string num of digits (0 to 9) denoting a positive integer. Find a string denoting the lowest integer number possible by removing k digits from num, without changing their order.
Note: num will not contain any leading zero.

Example 1:
Input:
k = 2
num = "143729"
Output: "1329"
Explanation: 1329 is the minimum number
possible after removing '4' and '7'.

Example 2:
Input:
k = 3
num = "10056"
Output: "0"
Explanation: 0 is the minimum number
possible after removing '1' , '5' and '6'.

Your Task:
You dont need to read input or print anything. Complete the function buildLowestNumber() which accepts string num and integer k as input parameters and returns a string denoting the smallest integer possible after removing k digits from num without changing the order.

Expected Time Complexity: O(Length of num)
Expected Auxiliary Space: O(Length of num)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/build-the-smallest2841/1

Must Do DSA Topics Day 55
Tree
Find n-th node of inorder traversal : We do simple Inorder Traversal. While doing the traversal, we keep track of count of nodes visited so far. When count becomes n, we print the node.
Learn more : http://bit.ly/3YdwUQ8

Find n-th node in Postorder traversal of a Binary Tree : Given a Binary tree and a number N, write a program to find the N-th node in the Postorder traversal of the given Binary tree.
Learn more : http://bit.ly/3FgMYb5

Level order traversal line by line : Given the root of the Binary Tree. The task is to print the Level order traversal of a tree is breadth first traversal for the tree.
Learn more : https://bit.ly/3EUF9HN

Problem Of The Day
“Array Pair Sum Divisibility Problem”

Solve the problem to win points

Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.


Example 1 :
Input : arr = [9, 5, 7, 3], k = 6
Output: True
Explanation: {(9, 3), (5, 7)} is a
possible solution. 9 + 3 = 12 is divisible
by 6 and 7 + 5 = 12 is also divisible by 6.

Example 2:
Input : arr = [2, 4, 1, 3], k = 4
Output: False
Explanation: There is no possible solution.

Your Task:
You don't need to read or print anything. Your task is to complete the function canPair() which takes array and k as input parameter and returns true if array can be divided into pairs such that sum of every pair is divisible by k otherwise returns false.

Expected Time Complexity: O(n)
Expected Space Complexity : O(n)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/array-pair-sum-divisibility-problem3257/1

Must Do DSA Topics Day 56
Tree
Reverse Level Order Traversal : The idea is to print the last level first, then the second last level, and so on. Like Level order traversal, every level is printed from left to right.
Learn more : https://bit.ly/3uKMwwI

Reverse tree path : Given a tree and node data, the task to reverse the path to that particular Node.
Learn more : https://bit.ly/3YaV8u9

Perfect Binary Tree Specific Level Order Traversal : In standard Level Order Traversal, we enqueue root into a queue 1st, then we dequeue ONE node from queue, process (print) it, enqueue its children into queue.
Learn more : https://bit.ly/3uKM4yw

Problem Of The Day
“Articulation Point - I”

Solve the problem to win points

Given an undirected connected graph with V vertices and adjacency list adj. You are required to find all the vertices removing which (and edges through it) disconnects the graph into 2 or more components.
Note: Indexing is zero-based i.e nodes numbering from (0 to V-1). There might be loops present in the graph.

Example 1:
Input:

Output:{1,4}

Your Task:
You don't need to read or print anything. Your task is to complete the function articulationPoints() which takes V and adj as input parameters and returns a list containing all the vertices removing which turn the graph into two or more disconnected components in sorted order. If there are no such vertices then returns a list containing -1.


Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/articulation-point-1/1