JSJive

Posts

Finding middle element in a linked list (DSA)

Problem Statement: (👈click here for GFG) Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if the linked list is 1-> 2->3->4->5 , then the middle node of the list is 3 . If there are two middle nodes(in case, when N is even), print the second middle element. For example, if the linked list given is 1->2->3->4->5->6 , then the middle node of the list is 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 Auxilia...

Detect cycle in a directed graph (DSA)

problem Statement :(👈click here for GFG) Given a Directed Graph with V vertices (Numbered from 0 to V-1 ) and E edges, check whether it contains any cycle or not. Example 1: Input: Output: 1 Explanation : 3 -> 3 is a cycle Example 2: Input: Output: 0 Explanation : no cycle in the graph Your task: You dont need to read input or print anything. Your task is to complete the function isCyclic() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the given directed graph contains a cycle or not. Expected Time Complexity: O(V + E) Expected Auxiliary Space: O(V) Constraints: 1 ≤ V, E ≤ 10^5 Solution: class Solution { // Function to detect cycle in a directed graph. isCyclic(V, adj) { // Create arrays to keep track of visited nodes and nodes in the current recursion stack. let visited = new Array(V).fill(false); let recStack = new ...

Detect cycle in an undirected graph (DSA)

Problem Statement :(👈click here for GFG) Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not. Graph is in the form of adjacency list where adj[i] contains all the nodes ith node is having edge with. Example 1: Input: V = 5, E = 5 adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}} Output: 1 Explanation: 1->2->3->4->1 is a cycle. Example 2: Input: V = 4, E = 2 adj = {{}, {2}, {1, 3}, {2}} Output: 0 Explanation: No cycle in the graph. Your Task: You don't need to read or print anything. Your task is to complete the function isCycle() which takes V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the undirected graph contains any cycle or not, return 1 if a cycle is present else return 0. NOTE: The adjacency list denotes the edges of the graph where edges[i] stores all other vertices to which ith vertex is connected. Expected Time Comple...

Nth node from end of linked list (DSA)

Problem Statement :(👈click here for GFG) Given a linked list consisting of L nodes and given a number N . The task is to find the N th node from the end of the linked list. Example 1: Input: N = 2 LinkedList: 1->2->3->4->5->6->7->8->9 Output: 8 Explanation: In the first example, there are 9 nodes in linked list and we need to find 2nd node from end. 2nd node from end is 8. Example 2: Input: N = 5 LinkedList: 10->5->100->5 Output: -1 Explanation: In the second example, there are 4 nodes in the linked list and we need to find 5th from the end. Since 'n' is more than the number of nodes in the linked list, the output is -1. Your Task: The task is to complete the function getNthFromLast() which takes two arguments: reference to head and N and you need to return Nth from the end or -1 in case node doesn't exist. Note: Try to solve in a single traversal. Expected Time Complexity: O(N). Expected A...

Count pairs with given sum (DSA)

Problem Statement: (👈click here for GFG) Given an array of N integers, and an integer K , find the number of pairs of elements in the array whose sum is equal to K . Example 1: Input: N = 4, K = 6 arr[] = {1, 5, 7, 1} Output: 2 Explanation: arr[0] + arr[1] = 1 + 5 = 6 and arr[1] + arr[3] = 5 + 1 = 6. Example 2: Input: N = 4, K = 2 arr[] = {1, 1, 1, 1} Output: 6 Explanation: Each 1 will produce sum 2 with any 1. Your Task: You don't need to read input or print anything. Your task is to complete the function getPairsCount() which takes arr[], n and k as input parameters and returns the number of pairs that have sum K. Expected Time Complexity: O(N) Expected Auxiliary Space: O(N) Constraints: 1 <= N <= 105 1 <= K <= 108 1 <= Arr[i] <= 106 Solution: class Solution { getPairsCount(arr,n,k){ //code here let count = 0; let hash = {}; for(let i = 0; i < n; i++){ ...

Next Greater Element (DSA)

Problem Statement :(👈click here for GFG) Given an array arr[ ] of size N having elements, the task is to find the next greater element for each element of the array in order of their appearance in the array. Next greater element of an element in the array is the nearest element on the right which is greater than the current element. If there does not exist next greater of current element, then next greater element for current element is -1. For example, next greater of the last element is always -1. Example 1: Input : N = 4, arr[] = [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 ? since it doesn't exist, it is -1. Example 2: Input : N = 5, arr[] [6 8 0 1 3] Output : 8 -1 1 3 -1 Explanation : In the array, the next larger element to 6 is 8, for 8 there is no larger elements hence it is -1, for 0 it is 1 , for 1 it is 3 and then for 3 there is no larger element on right...