DSA-450 🚀

This repository contains solutions to the 450 Questions of the DSA Cracker Sheet curated by Love Babbar.

DSA-450 Sheet : Link

Topics

• Array
• Matrix
• String
• Linked List
• Searching & Sorting
• Stack & Queue
• Binary Tree
• Bit Manipulation

Array

#	Problem	Solution	Time	Space
1	Reverse an Array	Sol	O(n)	O(1)
2	Find the maximum and minimum element in an array	Sol	O(n)	O(1)
3	Find the "Kth" max and min element of an array	Sol	O(n*logk)	O(k)
4	Sort an array which consists of only 0, 1 and 2 without using any sorting algo	Sol	O(n)	O(1)
5	Move all the negative elements to one side of the array	Sol	O(n)	O(1)
6	Find the Union and Intersection of the two sorted arrays.	Sol	O(m+n)	O(m+n)
7	Write a program to cyclically rotate an array by one.	Sol	O(n)	O(d)
8	Find Largest sum contiguous Subarray V. IMP	Sol	O(n)	O(1)
9	Minimise the maximum difference between heights V.IMP	Sol	O(n*logn)	O(1)
10	Minimum no. of Jumps to reach end of an array		-	-
11	Find duplicate in an array of N+1 Integers	Sol	O(n)	O(1)
12	Merge 2 sorted arrays without using Extra space.		O(logn)	O(1)
13	Kadane's Algo [V.V. IMP]		O(n)	O(1)
14	Merge Intervals	Sol	O(n*logn)	O(logn)
15	Next Permutation	Sol	O(n)	O(1)
16	Count Inversion		-	-
17	Best time to buy and Sell stock	Sol	O(n)	O(1)
18	Find all pairs on integer array whose sum is equal to given number	Sol	O(n)	O(n)
19	Find common elements In 3 sorted arrays		-	-
20	Rearrange the array in alternating positive and negative items with O(1) extra space		-	-
21	Find if there is any subarray with sum equal to 0		-	-
22	Find factorial of a large number		-	-
23	Find maximum product subarray		-	-
24	Find longest coinsecutive subsequence		-	-
25	Given an array of size n and a number k, find all elements that appear more than n/k times.		-	-
26	Maximum profit by buying and selling a share atmost twice		-	-
27	Find whether an array is a subset of another array		-	-
28	Find the triplet that sum to a given value		-	-
29	Trapping Rain water problem		-	-
30	Chocolate Distribution problem		-	-
31	Smallest Subarray with sum greater than a given value		-	-
32	Three way partitioning of an array around a given value		-	-
33	Minimum swaps required bring elements less equal K together		-	-
34	Minimum no. of operations required to make an array palindrome		-	-
35	Median of 2 sorted arrays of equal size		-	-
36	Median of 2 sorted arrays of different size		-	-

⬆️ Back to Top

Matrix

#	Problem	Solution	Time	Space
1	Spiral traversal on a Matrix	Sol	O(r*c)	O(r*c)
2	Search an element in a matriix	Sol	O(logmn)	O(1)
3	Find median in a row wise sorted matrix	Sol	O(32*r*logc)	O(1)
4	Find row with maximum no. of 1's	Sol	O(n+m)	O(1)
5	Print elements in sorted order using row-column wise sorted matrix	Sol	O(n2logn)	O(n2)
6	Maximum size rectangle	-	-
7	Find a specific pair in matrix	-	-
8	Rotate matrix by 90 degrees	Sol	O(n2)	O(1)
9	Kth smallest element in a row-column wise sorted matrix	-	-
10	Common elements in all rows of a given matrix	-	-

⬆️ Back to Top

String

#	Problem	Solution	Time	Space
1	Reverse a String	Sol	O(n)	O(1)
2	Check whether a String is Palindrome or not	Sol	O(n)	O(1)
3	Find Duplicate characters in a string	Sol	O(n)	O(k)
4	Why strings are immutable in Java?
5	Check whether one string is a rotation of another	Sol	O(n1+n2)	O(1)
6	Check whether a string is a valid shuffle of two strings or not	Sol	O(n)	O(1)
7	Count and Say problem	Sol	O(n*m)	O(1)
8	Find the longest Palindrome in a string[Longest palindromic Substring]
9	Find Longest Recurring Subsequence in String
10	Print all Subsequences of a string.
11	Print all the permutations of the given string	Sol	O(n*n!)	O(n)
12	Split the Binary string into two substring with equal 0’s and 1’s
13	Word Wrap Problem [VERY IMP].
14	EDIT Distance [Very Imp]
15	Find next greater number with same set of digits [V.V. IMP]
16	Balanced Parenthesis problem.[Imp]	Sol	O(n)	O(n)
17	Word break Problem[ Very Imp]
18	Rabin Karp Algo
19	KMP Algo
20	Convert a Sentence into its equivalent mobile numeric keypad sequence

⬆️ Back to Top

Linked List

#	Problem	Solution	Time	Space
1	Reverse the Linked List (Both iterative and recursive)	Sol	O(n)	O(1)
2	Reverse a Linked List in group of given Size. [Very Imp]
3	Detect loop in linked list
4	Delete loop in linked list
5	Find starting point of the loop
6	Remove duplicates in sorted linked list
7	Remove duplicates in unsorted linked list
8	Move last element to front in linked list
9	Add 1 to a number represented as linked list
10	Add two numbers represented by linked list

⬆️ Back to Top

Search & Sort

#	Problem	Solution	Time	Space
1	Find first and last positions of x in sorted array	Sol	O(logn)	O(1)
2	Find element equal to its index value	Sol	O(n)	O(1)
3	Search in rotated sorted array	Sol	O(logn)	O(1)
4	Count perfect squares less than n	Sol	O(sqrt(n))	O(1)
5	Find middle of three numbers	Sol	O(1)	O(1)
6	Optimum location of point to minimize total distance
7	Find missing and repeating elements	Sol	O(n)	O(1)
8	Find majority element	Sol	O(n)	O(1)
9	Search in array where adjacent differ by atmost k	Sol	O(n)	O(1)
10	Find a pair with given difference	Sol	O(n*logn)	O(1)
11	Find all quadruples that sum up to given value	Sol	O(n3)	O(1)

⬆️ Back to Top

Stack & Queue

#	Problem	Solution	Time	Space
1	Implement Stack	Sol
2	Implement Queue
3	Implement 2 stacks in one array
4	Find middle element of stack
5	Implement n stacks in one array
6	Check valid parenthesis	Sol	O(n)	O(n)
7	Reverse string using stack	Sol	O(n)	O(n)
8	Design a stack that supports getMin() in O(1) time and space
9	Find next greater element	Sol	O(n)	O(n)
10	The celebrity problem

⬆️ Back to Top

Binary Tree

#	Problem	Solution	Time	Space
1	Level Order Traversal	Sol	O(n)	O(n)
2	Reverse Level Order Traversal	Sol	O(n)	O(n)
3	Height of binary tree	Sol	O(n)	O(n)
4	Diameter of binary tree	Sol	O(n)	O(h)
5	Mirror tree of binary tree	Sol	O(n)	O(n)
6	Inorder traversal both iteratively & recursively	Sol	O(n)	O(n)
7	Preorder traversal both iteratively & recursively	Sol	O(n)	O(n)
8	Postorder traversal both iteratively & recursively	Sol	O(n)	O(n)
9	Left view of binary tree	Sol	O(n)	O(h)
10	Right view of binary tree	Sol	O(n)	O(h)
11	Top view of binary tree
12	Bottom view of binary tree
13	Zig-Zag level order traversal of binary tree	Sol	O(n)	O(n)
14	Check if given binary tree is balanced or not	Sol	O(n)	O(n)

⬆️ Back to Top

Bit Manipulation

#	Problem	Solution	Time	Space
1	Count set bits in n	Sol	O(logn)	O(1)
2	Find two non-repeating elements in an array of repeating elements	Sol	O(n)	O(1)
3	Count number of bits to be flipped to convert A to B	Sol	O(logn)	O(1)
4	Count total number of set bits from 1 to n	Sol	O(logn)	O(1)
5	Check if n is power of two	Sol	O(logn)	O(1)
6	Find position of only set sit
7	Copy set bits in a range
8	Divide two numbers without using *, / and % operator
9	Calculate square of number without using *, / and pow()
10	Power set

⬆️ Back to Top