Important Algo and Data structures

This repository contains solutions to important problems from leetcode, codechef, codeforces, Interviewbit and Hackerearth.

How to Contribute

1. Fork this repository.
2. Write the solution to the problem in your preferred language.
3. Check if the problem folder is available or not (For eg., BFS, DFS etc problems should go into the graphs folder). If the problem folder is not available, then create the folder.
4. Make sure that the code has comments and at the top, the problem link is given.
5. Create Pull Request.

Thanks and Happy Coding!

Binary Search

Refer this post: https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems

Refer solved problems here

Tip: Whenever we have some problems which tells to find minimised max answer, try to think binary search.

Reference problems:

1. Split Array Largest Sum
2. Divide Chocolate
3. Length of LIS
4. Russian Doll Envelopes
5. Find Indices of Ones

Graphs

Refer this post: https://leetcode.com/discuss/study-guide/1326900/graph-algorithms-problems-to-practice

Refer solved problems here

For 2d points, consider using indexes in adjacency map (Refer Detonate the Maximum Bombs)

Some more important problems

• Longest Increasing Path In a Matrix
• Maximum Score of a Node Sequence
• Alien Dictionary
• Maximum Number Of Invitations
• String Replacement Library

DSU complexity analysis

In union method, why do we set the parent which has greater size?

Refer these links

• https://cs.stackexchange.com/questions/82728/in-disjoint-sets-why-do-we-make-the-smaller-tree-the-subtree-of-the-larger-one

• https://stackoverflow.com/questions/53149097/why-is-the-time-complexity-of-performing-n-union-find-union-by-size-operations

Let's say we have 2 nodes x and y in the union method

We find the parent and note down the sizes of the groups which have x and y.

Suppose the height of group containing x is heightX and similarly for y, it is heightY.

Case 1: heightX > heightY
If we attach node x to node y, the height would become heightX + 1

But if we attach node y to node x, the height would be height X 

So we attach node y to node x.

Case 2: heightX = heightY
In this case, the height of the resultant set would be heightX + 1

Line Sweep

Refer this post: https://leetcode.com/discuss/study-guide/2166045/line-sweep-algorithms

Refer solved problems here

Some important problems

• On Call Rotation Schedule
• Non overlapping intervals (Sort by end time)
• Remove covered intervals (Sort by start time and then by end time in descending order)

Game theory

Solve problems by keeping the state of the current player. (And we can also remove the current player state if we see that it is not used in the recursive function)

Refer:

• Nim Game
• Divisor Game
• Stone Game IV
• Babylon

Solve problems by the Difference of scores method

Refer:

• Predict the winner
• Stone Game I
• Stone Game II
• Stone Game III
• Stone Game VII

Solve problems by sorting and greedy approach (When the problem says that a player can pick any idx from the array for their score).

Refer:

• Stone Game VI
• Maximum Number Of Coins You Can Get

Refer solved problems here

Priority queue

Refer this post: https://leetcode.com/discuss/study-guide/1360400/priority-queue-problems-to-practice

Refer solved problems here

Some important problems

• Reorganise Strings
• Time for turn
• Single threaded CPU
• Median in data stream

Segment tree

Refer this youtube link: Range Sum Query

Refer these problems:

• Count of Smaller Numbers After Self
• Range Sum Query

Tries

Refer solved problems here

Some important problems

• Find Selected Directories

TreeMap / TreeSet

Refer solved problems here

Some important problems

• Find triplets
• Amount of new area painted each day

Rate limiting

Refer these posts

• Fixed Window Counter and Sliding Window Log
• Leaky Bucket and Token Bucket