archgaelix

DSA 450 [42/413]

  1. Reverse an array

    #array 

  2. Find the maximum and minimum element in an array

    #array 

  3. Find the Kth max and min element in an array

    #array  #heap 

  4. Sort an array of 0s, 1s and 2s

    #array 

  5. Move all the negative elements to one side of the array

    #array 

  6. Find the union and intersection of the two sorted arrays

    #array 

  7. Cyclically rotate an array by one

    #array 

  8. Minimise the maximum difference between heights

    #array 

  9. Minimum number of jumps to reach end of an array

    #array 

  10. Find the duplicate in an array of N+1 integers

    #array 

  11. Kadane’s algorithm

    #array  #dp 

  12. Merge intervals

    #array 

  13. Next permutation

    #array 

  14. Count inversion

    #array  #search-sort 

  15. Best time to buy and sell stock

    #array 

  16. Find all pairs on integer array whose sum is equal to K

    #array 

  17. Find common elements in 3 sorted arrays

    #array 

  18. Rearrange the array in alternating positive and negative items with O(1) extra space

    #array 

  19. Find if there is any subarray with sum equal to 0

    #array 

  20. Find factorial of a large number

    #array 

  21. Find maximum product subarray

    #array 

  22. Find longest consecutive subsequence

    #array 

  23. Given an array of size N and a number K, find all elements that appear more than N/K times

    #array 

  24. Find whether an array is a subset of another array

    #array 

  25. Find the triplet that sum to a given value

    #array 

  26. Trapping rain water

    #array 

  27. Chocolate distribution

    #array  #greedy 

  28. Smallest subarray with sum greater than a given value

    #array 

  29. Three way partitioning of an array around a given value

    #array 

  30. Minimum swaps required to bring elements <= K together

    #array 

  31. Minimum number of merge operations required to make an array palindrome

    #array 

  32. Median of 2 sorted arrays of equal size

    #array 

  33. Median of 2 sorted arrays of different size

    #array 

  34. Spiral traversal on a matrix

    #matrix 

  35. Search an element in a matrix

    #matrix 

  36. Find median in a row wise sorted matrix

    #matrix 

  37. Find row with maximum number of 1s

    #matrix 

  38. Print elements in sorted order using row-column wise sorted matrix

    #matrix 

  39. Maximum size rectangle

    #matrix 

  40. Find a specific pair in matrix

    #matrix 

  41. Rotate matrix by 90 degrees

    #matrix 

  42. Kth smallest element in a row-column wise sorted matrix

    #matrix 

  43. Common elements in all rows of a given matrix

    #matrix 

  44. Check whether a string is palindrome

    #string 

  45. Find duplicate characters in a string

    #string 

  46. Why are strings immutable in Java?

    #string 

  47. Check whether one string is a rotation of another

    #string 

  48. Check whether a string is a valid shuffle of two strings

    #string 

  49. Count and say

    #string 

  50. Find the longest palindrome in a string

    #string 

  51. Print all subsequences of a string

    #string 

  52. Split the binary string into two substring with equal 0s and 1s

    #string 

  53. Word wrap

    #string  #dp 

  54. Edit distance

    #string  #dp 

  55. Find next greater number with same set of digits

    #string 

  56. Balanced parenthesis

    #string  #st-q 

  57. Word break

    #string  #trie  #backtracking  #dp 

  58. Rabin Karp algorithm

    #string 

  59. KMP algorithm

    #string 

  60. Bayer Moore algorithm

    #string 

  61. Convert a sentence into its equivalent mobile numeric keypad sequence

    #string 

  62. Minimum number of bracket reversals needed to make an expression balanced

    #string 

  63. Count all palindromic subsequence in a given string

    #string  #dp 

  64. Count of number of given string in 2D character array

    #string 

  65. Search a word in a 2D grid of characters

    #string 

  66. Converting roman numerals to decimal

    #string 

  67. Longest common prefix

    #string 

  68. Number of flips to make binary string alternate

    #string 

  69. Find the second most repeated word in string

    #string 

  70. Minimum number of swaps for bracket balancing

    #string 

  71. Program to generate all possible valid IP addresses from given string

    #string 

  72. Find the smallest window that contains all characters of string itself

    #string 

  73. Rearrange characters in a string such that no two adjacent are same

    #string  #heap  #greedy 

  74. Minimum characters to be added at front to make string palindrome

    #string 

  75. Given a sequence of words, print all anagrams together

    #string  #trie  #greedy 

  76. Find the smallest window in a string containing all characters of another string

    #string 

  77. Recursively remove all adjacent duplicates

    #string 

  78. String matching where one string contains wildcard characters

    #string 

  79. Function to find number of customers who could not get a computer

    #string 

  80. Transform one string to another using minimum number of given operation

    #string 

  81. Check if two given strings are isomorphic to each other

    #string 

  82. Recursively print all sentences that can be formed from list of word lists

    #string 

  83. Find first and last positions of an element in a sorted array

    #search-sort 

  84. Find a fixed point (value equal to index) in a given array

    #search-sort 

  85. Search in a rotated sorted array

    #search-sort 

  86. Square root of an integer

    #search-sort 

  87. Maximum and minimum of an array using minimum number of comparisons

    #search-sort 

  88. Optimum location of point to minimize total distance

    #search-sort 

  89. Find missing and repeating

    #search-sort 

  90. Find majority element

    #search-sort 

  91. Searching in an array where adjacent differ by at most K

    #search-sort 

  92. Find a pair with a given difference

    #search-sort 

  93. Find four elements that sum to a given value

    #search-sort 

  94. Maximum sum such that no 2 elements are adjacent

    #search-sort 

  95. Count triplet with sum smaller than a given value

    #search-sort 

  96. Merge 2 sorted arrays

    #array  #search-sort 

  97. Print all subarrays with 0 sum

    #search-sort 

  98. Product array puzzle

    #search-sort 

  99. Sort array according to count of set bits

    #search-sort 

  100. Minimum number of swaps required to sort the array

    #search-sort 

  101. Bishu and soldiers

    #search-sort 

  102. Rasta and Kheshtak

    #search-sort 

  103. Kth smallest number again

    #search-sort 

  104. Find pivot element in a sorted array

    #search-sort 

  105. Kth element of two sorted arrays

    #search-sort 

  106. Aggressive cows

    #search-sort 

  107. Book allocation aka Painter’s Partition

    #search-sort 

  108. Ekospoj

    #search-sort 

  109. Job scheduling algorithm

    #search-sort 

  110. Missing number in AP

    #search-sort 

  111. Smallest number with atleast N trailing zeroes in factorial

    #search-sort 

  112. Roti Prata

    #search-sort 

  113. Doublehelix

    #search-sort 

  114. Subset sums

    #search-sort 

  115. Implement merge-sort in-place

    #search-sort 

  116. Partitioning and sorting arrays with many repeated entries

    #search-sort 

  117. Reverse a linked list

    #ll 

  118. Reverse a linked list in group of given size

    #ll 

  119. Detect loop in a linked list

    #ll 

  120. Delete loop in a linked list

    #ll 

  121. Find the starting point of the loop

    #ll 

  122. Remove duplicates in a sorted linked list

    #ll 

  123. Remove duplicates in a unsorted linked list

    #ll 

  124. Move the last element to front in a linked list

    #ll 

  125. Add 1 to a number represented as a linked list

    #ll 

  126. Add two numbers represented by linked lists

    #ll 

  127. Intersection of two sorted linked list

    #ll 

  128. Intersection point of two linked lists

    #ll 

  129. Merge sort for linked lists

    #ll 

  130. Quicksort for linked lists

    #ll 

  131. Find the middle element of a linked list

    #ll 

  132. Check if a linked list is a circular linked list

    #ll 

  133. Split a circular linked list into two halves

    #ll 

  134. Check whether the singly linked list is a palindrome

    #ll 

  135. Deletion from a circular linked list

    #ll 

  136. Reverse a doubly linked list

    #ll 

  137. Find pairs with a given sum in a DLL

    #ll 

  138. Count triplets in a sorted DLL whose sum is equal to given value X

    #ll 

  139. Sort a K sorted doubly linked list

    #ll 

  140. Rotate DLL by N nodes

    #ll 

  141. Rotate a doubly linked list in group of given size

    #ll 

  142. Can we reverse a linked list in less than O(n)?

    #ll 

  143. Why is quicksort preferred for arrays while merge sort for linked lists?

    #ll 

  144. Flatten a linked list

    #ll 

  145. Sort a ll of 0s, 1s and 2s

    #ll 

  146. Clone a linked list with next and random pointer

    #ll 

  147. Multiply 2 numbers represented by ll

    #ll 

  148. Delete nodes which have a greater value on right side

    #ll 

  149. Segregate even and odd nodes in a linked list

    #ll 

  150. Program for Nth node from the end of a linked list

    #ll 

  151. Find the first non-repeating character from a stream of characters

    #ll 

  152. Level order traversal

    #bt 

  153. Reverse level order traversal

    #bt 

  154. Height of a tree

    #bt 

  155. Diameter of a tree

    #bt 

  156. Mirror of a tree

    #bt 

  157. Inorder traversal of a tree

    #bt 

  158. Preorder traversal of a tree

    #bt 

  159. Postorder traversal of a tree

    #bt 

  160. Right view of a tree

    #bt 

  161. Left view of a tree

    #bt 

  162. Top view of a tree

    #bt 

  163. Bottom view of a tree

    #bt 

  164. Zig-zag traversal of a binary tree

    #bt 

  165. Check if a tree is balanced

    #bt 

  166. Diagonal traversal of a binary tree

    #bt 

  167. Boundary traversal of a binary tree

    #bt 

  168. Construct binary tree from string with bracket representation

    #bt 

  169. Convert binary tree into doubly linked list

    #bt 

  170. Convert binary tree into sum tree

    #bt 

  171. Construct binary tree from inorder and preorder traversal

    #bt 

  172. Find minimum swaps required to convert a binary tree into BST

    #bt 

  173. Check if binary tree is sum tree

    #bt 

  174. Check if all leaf nodes are at same level

    #bt 

  175. Check if a binary tree contains duplicate subtrees of size 2 or more

    #bt 

  176. Check if 2 trees are mirror

    #bt 

  177. Sum of nodes on the longest path from root to leaf node

    #bt 

  178. Check if given graph is tree

    #bt 

  179. Find largest subtree sum in a tree

    #bt 

  180. Maximum sum of nodes in binary tree such that no two are adjacent

    #bt 

  181. Print all K sum paths in a binary tree

    #bt 

  182. Find LCA in a binary tree

    #bt 

  183. Find distance between 2 nodes in a binary tree

    #bt 

  184. Kth ancestor of node in a binary tree

    #bt 

  185. Find all duplicate subtrees in a binary tree

    #bt 

  186. Tree isomorphism

    #bt 

  187. Find a value in a BST

    #bst 

  188. Find min and max value in a BST

    #bst 

  189. Find inorder successor and inorder predecessor in a BST

    #bst 

  190. Deletion of a node in a BST

    #bst 

  191. Check if a tree is a BST

    #bst 

  192. Populate inorder successor of all nodes

    #bst 

  193. Find LCA in a BST

    #bst 

  194. Construct BST from preorder traversal

    #bst 

  195. Convert binary tree into BST

    #bst 

  196. Convert a normal BST into a balanced BST

    #bst 

  197. Merge two BST

    #bst 

  198. Find Kth largest element in a BST

    #bst 

  199. Find Kth smallest element in a BST

    #bst 

  200. Count pairs from 2 BST whose sum is equal to given value X

    #bst 

  201. Find the median of BST in O(n) time and O(1) space

    #bst 

  202. Count BST nodes that lie in a given range

    #bst 

  203. Replace every element with the least greater element on its right

    #bst 

  204. Given N appointments, find the conflicting appointments

    #bst 

  205. Check preorder is valid

    #bst 

  206. Check whether BST contains dead end

    #bst 

  207. Largest BST in a binary tree

    #bst 

  208. Flatten BST to sorted list

    #bst 

  209. Activity selection

    #greedy 

  210. Job sequencing

    #greedy 

  211. Huffman coding

    #greedy 

  212. Water connection

    #greedy 

  213. Fractional knapsack

    #greedy 

  214. Find minimum number of coins

    #greedy 

  215. Maximum trains for which stoppage can be provided

    #greedy 

  216. Minimum platforms

    #greedy 

  217. Buy maximum stocks if I stocks can be bought on Ith day

    #greedy 

  218. Find the minimum and maximum amount to buy all N candies

    #greedy 

  219. Minimum cost to cut a board into squares

    #greedy 

  220. Check if it is possible to survive on island

    #greedy 

  221. Find maximum meetings in one room

    #greedy 

  222. Maximum product subset of an array

    #greedy 

  223. Maximize array sum after K negations

    #greedy 

  224. Maximize the sum of arr[i]*i

    #greedy 

  225. Maximum sum of absolute difference of an array

    #greedy 

  226. Maximize sum of consecutive differences in a circular array

    #greedy 

  227. Minimum sum of absolute difference of pairs of two arrays

    #greedy 

  228. Shortest Job First (SJF) CPU scheduling

    #greedy 

  229. Least Recently Used (LRU) page replacement algorithm

    #greedy 

  230. Smallest subset with sum greater than all other elements

    #greedy 

  231. Defense of a kingdom

    #greedy 

  232. Die hard

    #greedy 

  233. Wine trading in Gergovia

    #greedy 

  234. Picking up chicks

    #greedy 

  235. Chocolate

    #greedy 

  236. Arranging amplifiers

    #greedy 

  237. K centers

    #greedy 

  238. Find smallest number with given number of digits and sum of digits

    #greedy 

  239. Find maximum sum possible equal sum of three stacks

    #greedy 

  240. Rat in a maze

    #graph  #backtracking 

  241. Printing all solutions to N-queens

    #backtracking 

  242. Remove invalid parentheses

    #backtracking 

  243. Sudoku solver

    #backtracking 

  244. M coloring

    #graph  #backtracking 

  245. Print all palindromic partitions of a string

    #backtracking 

  246. Knight’s tour

    #backtracking 

  247. Tug of war

    #backtracking 

  248. Find shortest safe route in a path with landmines

    #backtracking 

  249. Combination sum

    #backtracking 

  250. Find maximum number possible by doing atmost K swaps

    #backtracking 

  251. Print all permutations of a string

    #string  #backtracking 

  252. Longest possible route in a matrix with hurdles

    #backtracking 

  253. Print all possible paths from top left to bottom right of a MxN matrix

    #backtracking 

  254. Partition a set into K subsets with equal sum

    #backtracking 

  255. Find the Kth permutation sequence of first N natural numbers

    #backtracking 

  256. Implement stack from scratch

    #st-q 

  257. Implement queue from scratch

    #st-q 

  258. Implement 2 stack in an array

    #st-q 

  259. Find the middle element of a stack

    #st-q 

  260. Implement N stacks in an array

    #st-q 

  261. Reverse a string using stack

    #st-q 

  262. Design a stack that supports getmin() in O(1) time and O(1) extra space

    #st-q 

  263. Find the next greater element

    #st-q 

  264. Celebrity

    #st-q 

  265. Arithmetic expression evaluation

    #st-q 

  266. Evaluation of postfix expression

    #st-q 

  267. Implement a method to insert an element at its bottom without using any other data structure

    #st-q 

  268. Reverse a stack using recursion

    #st-q 

  269. Sort a stack using recursion

    #st-q 

  270. Merge overlapping intervals

    #st-q 

  271. Largest rectangular area in histogram

    #st-q 

  272. Length of the longest valid substring

    #st-q 

  273. Expression contains redundant bracket

    #st-q 

  274. Implement stack using queue

    #st-q 

  275. Implement stack using deque

    #st-q 

  276. Stack permutations

    #st-q 

  277. Implement queue using stack

    #st-q 

  278. Implement N queue in an array

    #st-q 

  279. Implement a circular queue

    #st-q 

  280. LRU cache implementation

    #st-q 

  281. Reverse a queue using recursion

    #st-q 

  282. Reverse the first K elements of a queue

    #st-q 

  283. Interleave the first half of the queue with second half

    #st-q 

  284. Find the first circular tour that visits all petrol pumps

    #st-q 

  285. Minimum time required to rot all oranges

    #st-q 

  286. Distance of nearest cell having 1 in a binary matrix

    #st-q 

  287. First negative integer in every window of size K

    #st-q 

  288. Check if all levels of two trees are anagrams

    #st-q 

  289. Sum of minimum and maximum elements of all subarrays of size K

    #st-q 

  290. Minimum sum of squares of character counts in a given string after removing K characters

    #st-q 

  291. Next smaller element

    #st-q 

  292. Implement a maxheap/minheap

    #heap 

  293. Heap sort

    #heap 

  294. Maximum of all subarrays of size K

    #heap 

  295. Kth largest element in an array

    #heap 

  296. Merge K sorted arrays

    #heap 

  297. Merge 2 binary max heaps

    #heap 

  298. Kth largest sum continuous subarrays

    #heap 

  299. Reorganize strings

    #heap 

  300. Merge K sorted linked lists

    #ll  #heap 

  301. Smallest range in K lists

    #heap 

  302. Median in a stream of integers

    #heap 

  303. Check if a binary tree is heap

    #heap 

  304. Connect N ropes with minimum cost

    #heap  #greedy 

  305. Convert BST to min heap

    #heap 

  306. Convert min heap to max heap

    #heap 

  307. Minimum sum of two numbers formed from digits of an array

    #heap 

  308. Create and print a graph

    #graph 

  309. Implement BFS

    #graph 

  310. Implement DFS

    #graph 

  311. Detect cycle in directed graph using BFS/DFS

    #graph 

  312. Detect cycle in undirected graph using BFS/DFS

    #graph 

  313. Minimum steps by knight

    #graph 

  314. Flood fill algorithm

    #graph 

  315. Clone a graph

    #graph 

  316. Making wired connections

    #graph 

  317. Word ladder

    #graph 

  318. Dijkstra algorithm

    #graph 

  319. Implement topological sort

    #graph 

  320. Minimum time taken by each job to be completed given by a directed acyclic graph

    #graph 

  321. Find whether it is possible to finish all tasks from given dependencies

    #graph 

  322. Find the number of islands

    #graph 

  323. Given a sorted dictionary of an alien language, find order of characters

    #graph 

  324. Implement Kruskal’s algorithm

    #graph 

  325. Implement Prim’s algorithm

    #graph 

  326. Total number of spanning tree in a graph

    #graph 

  327. Implement Bellman Ford algorithm

    #graph 

  328. Implement Floyd Warshall algorithm

    #graph 

  329. Travelling salesman

    #graph 

  330. Graph colouring

    #graph 

  331. Snake and ladders

    #graph 

  332. Find bridge in a graph

    #graph 

  333. Count strongly connected components (Kosaraju algorithm)

    #graph 

  334. Check if graph is bipartite

    #graph 

  335. Detect negative cycle in a graph

    #graph 

  336. Longest path in a directed acyclic graph

    #graph 

  337. Journey to the moon

    #graph 

  338. Cheapest flights within K stops

    #graph 

  339. Oliver and the game

    #graph 

  340. Water jug using BFS

    #graph 

  341. Minimum edges to reverse to make path from source to destination

    #graph 

  342. Paths to travel each nodes using each edge

    #graph 

  343. Vertex cover

    #graph 

  344. Chinese postman or route inspection

    #graph 

  345. Number of triangles in a directed and undirected graph

    #graph 

  346. Minimise the cashflow in a set of friends

    #graph  #greedy 

  347. Two clique

    #graph 

  348. Construct a trie from scratch

    #trie 

  349. Find shortest unique prefix for every word in a given list

    #trie 

  350. Implement a phone directory

    #trie 

  351. Print unique rows in a given boolean matrix

    #trie 

  352. Coin change

    #dp 

  353. Knapsack

    #dp 

  354. Binomial coefficient

    #dp 

  355. Permutation coefficient

    #dp 

  356. Nth catalan number

    #dp 

  357. Matrix chain multiplication

    #dp 

  358. Subset sum aka Partitions

    #dp  #backtracking 

  359. Friends pairing

    #dp 

  360. Gold mine

    #dp 

  361. Assembly line scheduling

    #dp 

  362. Painting the fence

    #dp 

  363. Maximize the cut segments

    #dp 

  364. Longest common subsequence

    #string  #dp 

  365. Longest repeated subsequence

    #string  #dp 

  366. Longest increasing subsequence

    #dp 

  367. Space optimized solution of LCS

    #dp 

  368. LCS of three strings

    #dp 

  369. Maximum sum increasing subsequence

    #dp 

  370. Count all subsequences having product less than K

    #dp 

  371. Longest subsequence such that difference between adjacent is one

    #dp 

  372. Maximum subsequence sum such that no three are consecutive

    #dp 

  373. Egg dropping

    #dp 

  374. Maximum length chain of pairs

    #dp 

  375. Maximum size square sub-matrix with all 1s

    #dp 

  376. Maximum sum of pairs with specific difference

    #dp 

  377. Min cost path

    #dp 

  378. Maximum difference of zeros and ones in binary string

    #dp 

  379. Minimum cost to fill given weight in a bag

    #dp 

  380. Minimum removals from array to make max - min <= K

    #dp 

  381. Longest common substring

    #dp 

  382. Count number of ways to reach a given score in a game

    #dp 

  383. Count balanced binary trees of height h

    #dp 

  384. Smallest sum contiguous subarray

    #dp 

  385. Unbounded knapsack

    #dp 

  386. Largest independent set

    #dp 

  387. Longest palindromic subsequence

    #dp 

  388. Longest palindromic substring

    #dp 

  389. Longest alternating subsequence

    #dp 

  390. Weighted job scheduling

    #dp 

  391. Coin game winner where every player has three choices

    #dp 

  392. Count derangements

    #dp 

  393. Optimal strategy for a game

    #dp 

  394. Optimal binary search tree

    #dp 

  395. Palindrome partitioning

    #dp 

  396. Mobile numeric keypad

    #dp 

  397. Boolean parenthesization

    #dp 

  398. Largest rectangular sub-matrix whose sum is 0

    #dp 

  399. Largest area rectangular sub-matrix with equal number of 1s and 0s

    #dp 

  400. Maximum sum rectangle in a 2D matrix

    #dp 

  401. Maximum profit by buying and selling a share at most K times

    #dp 

  402. Find if a string is interleaved of two other strings

    #dp 

  403. Maximum length of pair chain

    #dp 

  404. Count set bits in an integer

    #bit 

  405. Find the two non-repeating elements in an array of repeating elements

    #bit 

  406. Count number of bits to be flipped to convert A to B

    #bit 

  407. Count total set bits in all numbers from 1 to N

    #bit 

  408. Check if a number is a power of 2

    #bit 

  409. Find position of the only set bit

    #bit 

  410. Copy set bits in a range

    #bit 

  411. Divide two integers without using multiplication, division or mod operator

    #bit 

  412. Calculate square of a number without using *, / and pow()

    #bit 

  413. Power set

    #bit