Problem Of The Day
"A difference of values and indexes"

Solve the problem to win points

Given an unsorted array arr[ ] of size n, you need to find the maximum difference of absolute values of elements and indexes, i.e., for i <= j, calculate maximum of | arr[ i ] - arr[ j ] | + | i - j |.

Example 1:
Input :
n = 3
arr[ ] = {1, 3, -1}
Output: 5
Explanation:
Maximum difference comes from indexes
1, 2 i.e | 3 - (-1) | + | 1 - 2 | = 5

Example 2:
Input :
n = 4
arr[ ] = {5, 9, 2, 6}
Output: 8
Explanation:
Maximum difference comes from indexes
1, 2 i.e | 9 - 2 | + | 1 - 2 | = 8

Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maxDistance() that takes an array (arr), sizeOfArray (n), and return the maximum difference as given in the question. The driver code takes care of the printing.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/a-difference-of-values-and-indexes0302/1

Powered by hirist.com

Must Do DSA Topics Day 67
Heap
Tournament Tree (Winner Tree) and Binary Heap : Given a team of N players. How many minimum games are required to find the second-best player? We can use adversary arguments based on the tournament tree (Binary Heap).
Learn more : https://bit.ly/3HPWJ30

Check if a given Binary Tree is Heap : Given a binary tree, check if it has heap property or not, Binary tree needs to fulfill the following two conditions for being a heap – It should be a complete tree (i.e. all levels except the last should be full).
Every node’s value should be greater than or equal to its child node (considering max-heap).
Learn more : https://bit.ly/3WdkB4H

How to check if a given array represents a Binary Heap? : A Simple Solution is to first check root if it’s greater than all of its descendants. Then check for children of the root. Time complexity of this solution is O(n2)
Learn more : https://bit.ly/3FzaOPu

Problem Of The Day
"Absolute List Sorting"

Solve the problem to win points

Given a linked list of N nodes, sorted in ascending order based on the absolute values of its data,i.e. negative values are considered as positive ones. Sort the linked list in ascending order according to the actual values, and consider negative numbers as negative and positive numbers as positive.

Example 1:
Input:
List: 1, -2, -3, 4, -5
Output:
List: -5, -3, -2, 1, 4
Explanation:
Actual sorted order of {1, -2, -3, 4, -5}
is {-5, -3, -2, 1, 4}

Example 2:
Input:
List: 5, -10
Output:
List: -10, 5
Explanation:
Actual sorted order of {5, -10}
is {5, 10}

Your Task:
You don't need to read or print anyhting. Your Task is to comple the function sortList() which takes the head of the Linked List as input parameter and sort the list in ascending order and return the head pointer of the sorted list.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/absolute-list-sorting/1

Powered by hirist.com

Must Do DSA Topics Day 68
Heap
Merge Sort Tree for Range Order Statistics : The key idea is to build a Segment Tree with a vector at every node and the vector contains all the elements of the sub-range in a sorted order.
Learn more : https://bit.ly/3VgGxuH

Sort numbers stored on different machines : Given N machines. Each machine contains some numbers in sorted form. But the amount of numbers, each machine has is not fixed. Output the numbers from all the machine in sorted non-decreasing form.
Learn more : https://bit.ly/3VdLswu

Smallest Derangement of Sequence : A derangement of S is as any permutation of S such that no two elements in S and its permutation occur at the same position.
Learn more : https://bit.ly/3FEWEwe

Problem Of The Day
"Zero Sum Subarrays"

Solve the problem to win points

You are given an array arr[] of size n. Find the total count of sub-arrays having their sum equal to 0.

Example 1:
Input:
n = 6
arr[] = {0,0,5,5,0,0}
Output: 6
Explanation: The 6 subarrays are
[0], [0], [0], [0], [0,0], and [0,0].

Example 2:
Input:
n = 10
arr[] = {6,-1,-3,4,-2,2,4,6,-12,-7}
Output: 4
Explanation: The 4 subarrays are [-1 -3 4]
[-2 2], [2 4 6 -12], and [-1 -3 4 -2 2]

Your Task:
You don't need to read input or print anything. Complete the function findSubarray() that takes the array arr and its size n as input parameters and returns the total number of sub-arrays with 0 sum.

Expected Time Complexity: O(n*log(n))
Expected Auxilliary Space: O(n)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/zero-sum-subarrays1825/1

Powered by hirist.com

Must Do DSA Topics Day 69
Heap
Maximum distinct elements after removing k elements: Given an array arr[] containing n elements. The problem is to find the maximum number of distinct elements (non-repeating) after removing k elements from the array.
Learn more : https://bit.ly/3GaXd29

Maximum difference between two subsets of m elements : Given an array of n integers and a number m, find the maximum possible difference between two sets of m elements chosen from given array.
Learn more : https://bit.ly/3FNPSEt

Height of a complete binary tree (or Heap) with N nodes : Consider a Binary Heap of size N. We need to find the height of it.
Learn more : https://bit.ly/3hE9lQ9

Problem Of The Day
"Burst Balloons"

Solve the problem to win points

You are given N balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array arr. You are asked to brust all the balloons.

If you brust the ith  balloon,, you will get arr[ i - 1 ] * arr[ i ] * arr[ i + 1] coins. If i - 1, or i + 1 goes out of bounds of the array, consider it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by brusting the balloons wisely.

Example 1:
Input:
N = 4
arr[ ] = {3, 1, 5, 8}
Output: 167
Explanation: 
arr[ ] = {3, 1, 5, 8}  - - > {3, 5, 8} - - > {3, 8} - - > { 8} - -> { }
coins = 3 *1 *5,      +      3*5*8     +   1*3*8   +  1*8*1   = 167

Example 2:
Input:
N = 2
arr[ ] = {1, 10}
Output: 20

Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes the array of integers arr and N as parameters and returns the maximum coin you can collect.

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

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

Powered by hirist.com

Must Do DSA Topics Day 70
Heap
Print all nodes less than a value x in a Min Heap : Given a binary min heap and a value x, print all the binary heap nodes having value less than the given value x.
Learn more : https://bit.ly/3hLMF06

Median of Stream of Running Integers using STL : Given that integers are being read from a data stream. Find the median of all the elements read so far starting from the first integer till the last integer.
Learn more : https://bit.ly/3viNyAl

Largest triplet product in a stream : Given a stream of integers represented as arr[]. For each index i from 0 to n-1, print the multiplication of largest, second largest, third largest element of the subarray arr[0…i]. If i < 2 print -1.
Learn more : https://bit.ly/3VnXoLY

Get access to all the topics of heap: https://www.geeksforgeeks.org/heap-data-structure/

Problem Of The Day
"Wine Buying and Selling"

Solve the problem to win points

Given an array, Arr[] of size N represents N house built along a straight line with equal distance between adjacent houses. Each house has a certain number of wine and they want to buy/sell those wines to other houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of work. The task is to find the minimum number of work is required to fulfill all the demands of those N houses.

if arr[i] < 0, then ith house wants to sell arr[i] number of a wine bottle to other houses.

if arr[i] > 0, then ith house wants to buy arr[i] number of a wine bottle from other houses.

Note: One have to print the minimum number such that, all the house can buy/sell wine to each other.
It is guaranteed that sum of all the elements of the array will be 0.

Example 1:
Input: N = 5, Arr[] = {5, -4, 1, -3, 1}
Output: 9
Explanation:
1th house can sell 4 wine bottles to 0th house,
total work needed 4*(1-0) = 4, new arr[] = 1,0,1,-3,1
now 3rd house can sell wine to 0th, 2th and 4th.
so total work needed = 1*(3-0)+1*(3-2)+1*(4-3) = 5
So total work will be 4+5 = 9

Example 2:
Input: N = 5,
Arr[]={-1000, -1000, -1000, 1000, 1000, 1000}
Output: 9000
Explanation:
0th house sell 1000 wine bottles to 3rd house,
total work needed 1000*(3-0) = 3000.
1st house sell 1000 wine bottles to 4th house,
total work needed 3000 + 1000*(3-0) = 6000.
2nd house sell 1000 wine bottles to 5th house,
total work needed 6000 + 1000*(3-0) = 9000.
So total work will be 9000 unit.

Your Task:
You don't need to read input or print anything. Complete the function wineSelling() which takes the array Arr[] and its size N as input parameters and returns an integer as output.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/wine-buying-and-selling/1

Powered by hirist.com

Must Do DSA Topics Day 71
Graph
Introduction to Graphs : A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph.
Learn more : https://bit.ly/3vhejp8

Graph and its representations : Graphs are used to represent many real-life applications: Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network.
Learn more : https://bit.ly/3WER0kv

Types of Graphs with Examples : Any graph which contains some parallel edges but doesn’t contain any self-loop is called a multigraph.
Learn more : https://bit.ly/3GfOc8h

Job Alert 💼🔊
Micro Focus is hiring for Software Development Engineer - Java in Bangalore.

Interested candidates can apply and share the job opportunity with friends.😃🤌

Click on the following link for more details: https://practice.geeksforgeeks.org/jobs/microfocus-sdejava

Problem Of The Day
"Missing number in matrix"

Solve the problem to win points

Given a matrix of size n x n such that it has only one 0, Find the positive number (greater than zero) to be placed in place of the 0 such that sum of the numbers in every row, column and two diagonals become equal. If no such number exists, return -1.

Note: Diagonals should be only of the form matrix[i][i] and matrix[i][n-i-1]. n is always greater than 1.

Example 1:
Input: matrix = {{5, 5}, {5, 0}}
Output: 5
Explanation: The matrix is
5 5
5 0
Therefore If we place 5 instead of 0, all
the element of matrix will become 5.
Therefore row 5+5=10, column 5+5=10 and
diagonal 5+5=10, all are equal.

Example 2:
Input: matrix = {{1, 2, 0}, {3, 1, 2},
{2, 3, 1}}
Output: -1
Explanation: It is not possible to insert
an element in place of 0 so that the
condition is satisfied.thus result is -1.

Your Task:
You don't need to read or print anyhting. Your task is to complete the function MissingNo() which takes the matrix as input parameter and returns the number which should be placed in place of 0 such that the condition gets satisfied. If not possible return -1.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/missing-number-in-matrix5316/1

Powered by hirist.com

Must Do DSA Topics Day 72
Graph
Applications of Depth First Search : Depth-first search (DFS) is an algorithm (or technique) for traversing a graph. DFS uses a stack data structure for the traversal. A graph can have more than one DFS traversal.
Learn more : https://bit.ly/3vfC9S1

Applications of Breadth First Traversal : We have earlier discussed Breadth First Traversal Algorithm for Graphs. We have also discussed Applications of Depth First Traversal. In this article, applications of Breadth First Search are discussed.
Learn more : https://bit.ly/3gjipte

Iterative Depth First Search : Depth First Traversal (or Search) for a graph is similar to Depth First Traversal (DFS) of a tree. The only catch here is, unlike trees, graphs may contain cycles, so a node might be visited twice.
Learn more : https://bit.ly/3Gh2mWt

Job Alert 💼🔊
LinuXbean is hiring for PHP Developer in Indore.

Interested candidates can apply and share the job opportunity with friends.

Click on the following link for more details: https://practice.geeksforgeeks.org/jobs/PHP-DeveloperLinuxBean

Problem Of The Day
"Akku and Binary Numbers"

Solve the problem to win points

Akku likes binary numbers and she likes playing with these numbers. Her teacher once gave her a question.For given value of L and R, Akku have to find the count of number X, which have only three-set bits in it's binary representation such that "L ≤ X ≤ R".Akku is genius, she solved the problem easily. Can you do it ??

Example 1:
Input:
L = 11 and R = 19
Output: 4
Explanation:
There are 4 such numbers with 3 set bits in
range 11 to 19.
11 -> 1011
13 -> 1101
14 -> 1110
19 -> 10011

Example 2:
Input:
L = 25 and R = 29
Output: 3
Explanation:
There are 3 such numbers with 3 set bits in
range 25 to 29.
25 -> 11001
26 -> 11010
28 -> 11100

Your Task:
You don't need to read input or print anything. Your task is to complete the function solve() which takes the integer L and R as input parameters and returns the count of number X, which have only three-set bits in its binary representation such that "L ≤ X ≤ R".

Expected Time Complexity: O(633) + O(log(R-L))
Expected Auxiliary Space: O(633)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/akku-and-binary-numbers0902/1

Powered by hirist.com

Must Do DSA Topics Day 73
Graph
Detect Cycle in a Directed Graph : Given the root of a Directed graph, The task is to check whether the graph contains a cycle if yes then return true, return false otherwise.
Learn more : https://bit.ly/3VpGyw8

Detect cycle in an undirected graph : Given an undirected graph, The task is to check if there is a cycle in the given graph.
Learn more : https://bit.ly/3FUgJib

Detect cycle in a direct graph using colors : Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.
Learn more : https://bit.ly/3vidgoO

Problem Of The Day
"Container With Most Water"

Solve the problem to win points

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.

Note : In Case of single verticle line it will not be able to hold 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).

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/container-with-most-water0535/1

Powered by hirist.com

Must Do DSA Topics Day 74
Graph
Dijkstra’s shortest path algorithm : Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.
Learn more : https://bit.ly/3YRz3kz

Bellman–Ford Algorithm : Given a graph and a source vertex src in the graph, find the shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.
Learn more : https://bit.ly/3YRYz9C

Floyd Warshall Algorithm : The Floyd Warshall Algorithm is for solving all pairs of shortest-path problems. The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed Graph.
Learn more : https://bit.ly/3WoTGmQ

Problem Of The Day
"Largest subtree sum in a tree"

Solve the problem to win points

Given a binary tree. The task is to find subtree with maximum sum in the tree and return its sum.

Example 1:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output: 28
Explanation:
As all the tree elements are positive,
the largest subtree sum is equal to
sum of all tree elements.

Example 2:
Input:
1
/ \
-2 3
/ \ / \
4 5 -6 2
Output: 7
Explanation:
Subtree with largest sum is :
-2
/ \
4 5
Also, entire tree sum is also 7.

Your Task:
You don't need to read input or print anything. Your task is to complete the function findLargestSubtreeSum() which takes the root of a binary tree and returns an integer.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/largest-subtree-sum-in-a-tree/1

Powered by hirist.com

Must Do DSA Topics Day 75
Graph
Prim’s Minimum Spanning Tree (MST) : Prim’s algorithm always starts with a single node and it moves through several adjacent nodes, in order to explore all of the connected edges along the way.
Learn more : https://bit.ly/3Vr7tYD

Kruskal’s Minimum Spanning Tree Algorithm : A Spanning tree is a subset to a connected graph G, where all the edges are connected, i.e, one can traverse to any edge from a particular edge with or without intermediates.
Learn more : https://bit.ly/3I6v39X

Difference between Prim’s and Kruskal’s algorithm for MS : Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together.
Learn more : https://bit.ly/3VtsiTa