DSA Mastersheet

119 / 414

Reverse an array

Find the maximum and minimum element in an array

Find the Kth max and min element in an array

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

Move all the negative elements to one side of the array

Find the union and intersection of the two sorted arrays

Cyclically rotate an array by one

Minimise the maximum difference between heights

Minimum number of jumps to reach end of an array

Find the duplicate in an array of N+1 integers

Kadane’s algorithm

Merge intervals

Next permutation

Count inversion

Best time to buy and sell stock

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

Find common elements in 3 sorted arrays

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

Find if there is any subarray with sum equal to 0

Find factorial of a large number

Find maximum product subarray

Find longest consecutive subsequence

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

Find whether an array is a subset of another array

Find the triplet that sum to a given value

Trapping rain water

Chocolate distribution

Smallest subarray with sum greater than a given value

Three way partitioning of an array around a given value

Minimum swaps required to bring elements <= K together

Minimum number of merge operations required to make an array palindrome

Median of 2 sorted arrays of equal size

Median of 2 sorted arrays of different size

Spiral traversal on a matrix

Search an element in a matrix

Find median in a row wise sorted matrix

Find row with maximum number of 1s

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

Maximum size rectangle

Find a specific pair in matrix

Rotate matrix by 90 degrees

Kth smallest element in a row-column wise sorted matrix

Common elements in all rows of a given matrix

Reverse a string

Check whether a string is palindrome

Find duplicate characters in a string

Why are strings immutable in Java?

Check whether one string is a rotation of another

Check whether a string is a valid shuffle of two strings

Count and say

Find the longest palindrome in a string

Print all subsequences of a string

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

Word wrap

Edit distance

Find next greater number with same set of digits

Balanced parenthesis

Word break

Rabin Karp algorithm

KMP algorithm

Convert a sentence into its equivalent mobile numeric keypad sequence

Minimum number of bracket reversals needed to make an expression balanced

Count all palindromic subsequence in a given string

Count of number of given string in 2D character array

Search a word in a 2D grid of characters

Boyer Moore algorithm for pattern searching

Converting roman numerals to decimal

Longest common prefix

Number of flips to make binary string alternate

Find the second most repeated word in string

Minimum number of swaps for bracket balancing

Program to generate all possible valid IP addresses from given string

Find the smallest window that contains all characters of string itself

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

Minimum characters to be added at front to make string palindrome

Given a sequence of words, print all anagrams together

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

Recursively remove all adjacent duplicates

String matching where one string contains wildcard characters

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

Transform one string to another using minimum number of given operation

Check if two given strings are isomorphic to each other

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

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

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

Search in a rotated sorted array

Square root of an integer

Maximum and minimum of an array using minimum number of comparisons

Optimum location of point to minimize total distance

Find missing and repeating

Find majority element

Searching in an array where adjacent differ by at most K

Find a pair with a given difference

Find four elements that sum to a given value

Maximum sum such that no 2 elements are adjacent

Count triplet with sum smaller than a given value

Merge 2 sorted arrays

Print all subarrays with 0 sum

Product array puzzle

Sort array according to count of set bits

Minimum number of swaps required to sort the array

Bishu and soldiers

Rasta and Kheshtak

Kth smallest number again

Find pivot element in a sorted array

Kth element of two sorted arrays

Aggressive cows

Book allocation aka Painter’s Partition


Job scheduling algorithm

Missing number in AP

Smallest number with atleast N trailing zeroes in factorial

Roti Prata


Subset sums

Implement merge-sort in-place

Partitioning and sorting arrays with many repeated entries

Reverse a linked list

Reverse a linked list in group of given size

Detect loop in a linked list

Delete loop in a linked list

Find the starting point of the loop

Remove duplicates in a sorted linked list

Remove duplicates in a unsorted linked list

Move the last element to front in a linked list

Add 1 to a number represented as a linked list

Add two numbers represented by linked lists

Intersection of two sorted linked list

Intersection point of two linked lists

Merge sort for linked lists

Quicksort for linked lists

Find the middle element of a linked list

Check if a linked list is a circular linked list

Split a circular linked list into two halves

Check whether the singly linked list is a palindrome

Deletion from a circular linked list

Reverse a doubly linked list

Find pairs with a given sum in a DLL

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

Sort a K sorted doubly linked list

Rotate DLL by N nodes

Rotate a doubly linked list in group of given size

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

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

Flatten a linked list

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

Clone a linked list with next and random pointer

Multiply 2 numbers represented by ll

Delete nodes which have a greater value on right side

Segregate even and odd nodes in a linked list

Program for Nth node from the end of a linked list

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

Level order traversal

Reverse level order traversal

Height of a tree

Diameter of a tree

Mirror of a tree

Inorder traversal of a tree

Preorder traversal of a tree

Postorder traversal of a tree

Right view of a tree

Left view of a tree

Top view of a tree

Bottom view of a tree

Zig-zag traversal of a binary tree

Check if a tree is balanced

Diagonal traversal of a binary tree

Boundary traversal of a binary tree

Construct binary tree from string with bracket representation

Convert binary tree into doubly linked list

Convert binary tree into sum tree

Construct binary tree from inorder and preorder traversal

Find minimum swaps required to convert a binary tree into BST

Check if binary tree is sum tree

Check if all leaf nodes are at same level

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

Check if 2 trees are mirror

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

Check if given graph is tree

Find largest subtree sum in a tree

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

Print all K sum paths in a binary tree

Find LCA in a binary tree

Find distance between 2 nodes in a binary tree

Kth ancestor of node in a binary tree

Find all duplicate subtrees in a binary tree

Tree isomorphism

Find a value in a BST

Deletion of a node in a BST

Find min and max value in a BST

Find inorder successor and inorder predecessor in a BST

Check if a tree is a BST

Populate inorder successor of all nodes

Find LCA in a BST

Construct BST from preorder traversal

Convert binary tree into BST

Convert a normal BST into a balanced BST

Merge two BST

Find Kth largest element in a BST

Find Kth smallest element in a BST

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

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

Count BST nodes that lie in a given range

Replace every element with the least greater element on its right

Given N appointments, find the conflicting appointments

Check preorder is valid

Check whether BST contains dead end

Largest BST in a binary tree

Flatten BST to sorted list

Activity selection

Job sequencing

Huffman coding

Water connection

Fractional knapsack

Find minimum number of coins

Maximum trains for which stoppage can be provided

Minimum platforms

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

Find the minimum and maximum amount to buy all N candies

Minimum cost to cut a board into squares

Check if it is possible to survive on island

Find maximum meetings in one room

Maximum product subset of an array

Maximize array sum after K negations

Maximize the sum of arr[i]*i

Maximum sum of absolute difference of an array

Maximize sum of consecutive differences in a circular array

Minimum sum of absolute difference of pairs of two arrays

Shortest Job First (SJF) CPU scheduling

Least Recently Used (LRU) page replacement algorithm

Smallest subset with sum greater than all other elements

Defense of a kingdom

Die hard

Wine trading in Gergovia

Picking up chicks


Arranging amplifiers

K centers

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

Find maximum sum possible equal sum of three stacks

Rat in a maze

Printing all solutions to N-queens

Remove invalid parentheses

Sudoku solver

M coloring

Print all palindromic partitions of a string

Knight’s tour

Tug of war

Find shortest safe route in a path with landmines

Combination sum

Find maximum number possible by doing atmost K swaps

Print all permutations of a string

Longest possible route in a matrix with hurdles

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

Partition a set into K subsets with equal sum

Find the Kth permutation sequence of first N natural numbers

Implement stack from scratch

Implement queue from scratch

Implement 2 stack in an array

Find the middle element of a stack

Implement N stacks in an array

Reverse a string using stack

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

Find the next greater element


Arithmetic expression evaluation

Evaluation of postfix expression

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

Reverse a stack using recursion

Sort a stack using recursion

Merge overlapping intervals

Largest rectangular area in histogram

Length of the longest valid substring

Expression contains redundant bracket

Implement stack using queue

Implement stack using deque

Stack permutations

Implement queue using stack

Implement N queue in an array

Implement a circular queue

LRU cache implementation

Reverse a queue using recursion

Reverse the first K elements of a queue

Interleave the first half of the queue with second half

Find the first circular tour that visits all petrol pumps

Minimum time required to rot all oranges

Distance of nearest cell having 1 in a binary matrix

First negative integer in every window of size K

Check if all levels of two trees are anagrams

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

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

Next smaller element

Implement a maxheap/minheap

Heap sort

Maximum of all subarrays of size K

Kth largest element in an array

Merge K sorted arrays

Merge 2 binary max heaps

Kth largest sum continuous subarrays

Reorganize strings

Merge K sorted linked lists

Smallest range in K lists

Median in a stream of integers

Check if a binary tree is heap

Connect N ropes with minimum cost

Convert BST to min heap

Convert min heap to max heap

Minimum sum of two numbers formed from digits of an array

Create and print a graph

Implement BFS

Implement DFS

Detect cycle in directed graph using BFS/DFS

Detect cycle in undirected graph using BFS/DFS

Minimum steps by knight

Flood fill algorithm

Clone a graph

Making wired connections

Word ladder

Dijkstra algorithm

Implement topological sort

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

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

Find the number of islands

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

Implement Kruksal’s algorithm

Implement Prim’s algorithm

Total number of spanning tree in a graph

Implement Bellman Ford algorithm

Implement Floyd Warshall algorithm

Travelling salesman

Graph colouring

Snake and ladders

Find bridge in a graph

Count strongly connected components (Kosaraju algorithm)

Check if graph is bipartite

Detect negative cycle in a graph

Longest path in a directed acyclic graph

Journey to the moon

Cheapest flights within K stops

Oliver and the game

Water jug using BFS

Minimum edges to reverse to make path from source to destination

Paths to travel each nodes using each edge

Vertex cover

Chinese postman or route inspection

Number of triangles in a directed and undirected graph

Minimise the cashflow in a set of friends

Two clique

Construct a trie from scratch

Find shortest unique prefix for every word in a given list

Implement a phone directory

Print unique rows in a given boolean matrix

Coin change


Binomial coefficient

Permutation coefficient

Nth catalan number

Matrix chain multiplication

Subset sum aka Partitions

Friends pairing

Gold mine

Assembly line scheduling

Painting the fence

Maximize the cut segments

Longest common subsequence

Longest repeated subsequence

Longest increasing subsequence

Space optimized solution of LCS

LCS of three strings

Maximum sum increasing subsequence

Count all subsequences having product less than K

Longest subsequence such that difference between adjacent is one

Maximum subsequence sum such that no three are consecutive

Egg dropping

Maximum length chain of pairs

Maximum size square sub-matrix with all 1s

Maximum sum of pairs with specific difference

Min cost path

Maximum difference of zeros and ones in binary string

Minimum cost to fill given weight in a bag

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

Longest common substring

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

Count balanced binary trees of height h

Smallest sum contiguous subarray

Unbounded knapsack

Largest independent set

Longest palindromic subsequence

Longest palindromic substring

Longest alternating subsequence

Weighted job scheduling

Coin game winner where every player has three choices

Count derangements

Optimal strategy for a game

Optimal binary search tree

Palindrome partitioning

Mobile numeric keypad

Boolean parenthesization

Largest rectangular sub-matrix whose sum is 0

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

Maximum sum rectangle in a 2D matrix

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

Find if a string is interleaved of two other strings

Maximum length of pair chain

Count set bits in an integer

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

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

Count total set bits in all numbers from 1 to N

Check if a number is a power of 2

Find position of the only set bit

Copy set bits in a range

Divide two integers without using multiplication, division or mod operator

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

Power set