Tag: java
-
Data Structures & Algorithms in Java – Graphs – Pacific Atlantic Water Flow
Problem: There is a rectangular island of size m * n where m is the length and n is the breadth. The island is surrounded by Pacific Ocean on the left and the top and the Atlantic Ocean on the right and bottom. The m * n island is divided into m * n grids…
-
Data Structures & Algorithms in Java – Graphs – Course Schedule
Problem: Given the number of courses to take in a class and the dependency of the courses (before taking one course you should have taken another course) find out if all the courses can be taken. The dependency is mentioned by a list of pairs in the form [ [a1,b1],[a2,b2] …] where to take the…
-
Data Structures & Algorithms in Java – Graphs – Clone Graph
Problem: Given a graph , clone it. For example , consider a graph represented by the below adjacency list: [ [2,4],[1,3],[2,4],[1,3] ] You need to create a clone with the same adjacency list as above. An adjacency list is a list containing a list of neighbors of each node in a graph. So in the…
-
Data Structures & Algorithms in Java – Heaps – Find Median from Data Stream
Problem: Given a input stream of integers find the median of them. For example: The input has three methods , you need to implement all of them: MedianFinder() – this is the constructor , called once in the beginning addNum() – this method keeps adding a single number at a time to the stream findMedian()…
-
Data Structures & Algorithms in Java – Heap – Top K Frequent Elements
Problem: Given an array of numbers , find the k most frequent numbers . For example , Given the array: [1,1,1,2,2,3,4,5] and the value k = 2 The output is [1,2] Because these are the most frequent numbers. 1 occurs thrice and 2 occurs twice. Rest other numbers occur only once. So the most frequent…
-
Data Structures & Algorithms in Java – Matrix – Word Search
Problem Given a n*n matrix containing characters, find if the given word can be found in any direction For example , The output for above problem is true since the word ABCGK can be found in the matrix. Try out the solution here: https://leetcode.com/problems/word-search/ Solution: The solution to this problem is backtracking You start with…
-
Data Structures & Algorithms in Java – Matrix – Rotate Image
Problem: Given a n * n matrix representing an image , rotate the matrix by 90 degrees . Constraints: Do not use any extra memory in proportion to the input size. That is , space complexity should be 1. For example, For the input : [ [1,2,3], [4,5,6], [7,8,9]] The output is : [[7,4,1], [8,5,2],…
-
Data Structures & Algorithms in Java – Matrix – Spiral Matrix
Problem: Given a matrix , collect the elements in the matrix in a spiral direction clockwise and return them as a list. For example: Consider the matrix [[1,2,3],[4,5,6],[7,8,9]] You need to traverse the matrix spirally like below: So the output is : [1,2,3,6,9,8,7,4,5] Try out the solution here: https://leetcode.com/problems/spiral-matrix/ Solution: Hint: Traverse right , then…
-
Data Structures & Algorithms in Java – Matrix – Set Matrix Zeroes
Problem: Given a matrix , if any of its element is zero , make all the elements in both the row and column of the element to zero. For example: For the given matrix: [[1,1,1],[1,0,1],[1,1,1]] The second row second column has the value zero. So make all the values in the second row and second…
-
Data Structures & Algorithms in Java – Intervals – Meeting rooms II
Problem: Given an array of meeting intervals , find the minimum number of conference rooms required . For example, If the meeting intervals are : [[1,10],[2,15],[15,20]] Then the number of rooms required are 2. How? First we allocate a meeting room for the first meeting [1,10]. It ends at 10. The next meeting starts at…