Tag Archives: Data Structures

Next Greater Element in array

Problem: You are given an array, print the next greater element for each element. Elements for which no greater element exist, print next greater element as -1. You have to reduce the number of comparisons. For any array, rightmost element always has next greater element as -1. eg. For array [4, 15, 2, 9, 20, Read More →

Spiral traversal of binary tree

binary_tree

Given a binary tree , print it’s nodes in spiral fashion. Example for Given Tree,Output should be F,B,G,I,D,A,C,E,H This is also called zig zag tree traversal. Algorithm : We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal Read More →

Leaders in an array

Problem: You are given an array. You have to write a program that will print all the leaders in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example array {6, 7, 4, 3, 5, 2}, leaders Read More →

Eliminate the pairs (two same chars adjacent to each other) in string

Problem: You are given a string. You have to eliminate the pairs (two same chars adjacent to each other). eg. input string RGBBGBGR –> RGGBGR–> RBGR (output) Solution: We should check if we have character pair then cancel it. and then check for next character and previous character. Keep canceling the character until we either Read More →

Maximum size square sub-matrix with all 1s

Problem: Given a binary matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s. Example: Consider the below matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The Read More →

The Coin Problem – Dynamic Programming

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way Read More →

Reverse every k nodes of a linked list

Given a linked list and a number k. Reverse every k nodes in the list. Example : Input 1->2->3->4->5->6 and k = 2 Output 2->1->4->3->6->5 Solution : We have a pointer q which points to the head of the list initially. Advance this k times in a while loop and keep reversing the list. Now Read More →

Rotate an array by d elements

Problem: Write a program that will rotate a given array of size n by d elements. eg: 1 2 3 4 5 6 7 and d = 3 Output : 4 5 6 7 1 2 3 Method 1: For rotating the array by d elements, first rotate it by 1. Move a[1] to a[0], Read More →

Print nodes at K distance from root in binary tree

In a binary tree, given a root and a number K. You have to find the all nodes at distance K from given root node. For example in a given tree, if K =2 then Output should be 4,5,6 if k = 1 then Output should be 2,3 Time complexity: O(N) as we have to Read More →

Print Pairs with the given difference in sorted array

Given a sorted array and a number k. print all pairs in the array with difference between them is k. Solution 1: Using Hash Map Create a hashmap and then traverse the array. Use array elements as hash keys and enter them in hashmap. Traverse the array again and look for value k + arr[i] Read More →

Find loop in linked list and remove the loop

To remove the loop, we need to find the node at which the loop begins. Detection is easy by using fast and normal pointers (referred to as FP and NP from now on) to traverse such that the fast pointer traverses 2 nodes while normal pointer moves 1 node at a time. If they meet, Read More →

Merge k sorted arrays

Given k sorted arrays of size n,merge them into an output array which is sorted. Solution (Using Min Heap): This solution is similar to method 4 of this post. Steps: i. Create a min heap of size k of first element of each array. Repeat steps from 2 to 4 n*k times: ii. Take the Read More →