arnab2001/dsa

Collection of DSA problems and solutions

dsa's Issues

Print a single cycle in a graph

I would like to add this code. Please assign it to me.

kth largest element in an array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

example: Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

i want to add solution of this problem covering all possible approaches (from sorting to quick select)

Reverse a LinkedList in Javascript

Bellman Ford Algo

I want to add bellman ford algo in C++.
@arnab2001 Please, Assign me

Add Stack DataStructure folder

Range Query using Segment Tree

I would like to add this code. Please assign it to me.

Adding the code of graph traversal

Add the code of dfs and bfs.

Print Shortest Common Supersequence (CPP)

(DP Problem Using C++)

Given two strings X and Y of lengths m and n respectively, PRINT smallest string which has both, X and Y as its sub-sequences.
Example 1
Input:
X = abcd, Y = xycd
Output: abxycd
Explanation: Shortest Common Supersequence
would be abxycd which is of length 6 and
has both the strings as its subsequences.

// I wanna contribute this to DP folder , Please assign this to me

Sieve of Eratothenes

Printing Prime numbers till a given numbers

Add Max area Rectangle.

Hi, I would like to add maximum area of a rectangle formed only of 1s in the given matrix,
using c++.
Please assign it to me @arnab2001 .

Add three array problems

• LC 31- Next Permutation
• LC 56- Merge Intervals
• LC 287- Find the Duplicate Number

Rotate matrix by 90 degrees clockwise

LC. 48. Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Partition Problem (CPP)

Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is the same.

EXAMPLE:
A[ ]= {1, 5, 11, 5}
Output: true (1)
The array can be partitioned as {1, 5, 5} and {11}

A[ ] = {1, 5, 3}
Output: false (0)
The array cannot be partitioned into equal sum sets.

// I wanna contribute this to DP folder , Please assign this to me

Adding Binary Search In Javascript

Adding LinkedList in Javascript

Add Recursion Problems and solutions with C++

I would like to add some recursion questions to this repo like indirect, head, tail, tree Fibonacci recursion.

Will this contribution count in hacktoberfest?

Longest Common Substring (CPP)

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

Input : X = “zxabcdezy”, y = “yzabcdezx”
Output : 6
Explanation:
The longest common substring is “abcdez” and is of length 6.

// I wanna contribute this to DP folder , Please assign this to me

Coin change Dynamic programming problem

Given a value N, if we want to make change for N cents, and we have a supply of each of C = { C1, C2, .. , Cm} valued coins, how many ways can we make the change if the order of coins doesn’t matter.

Minimum Sum Partition (CPP)

Given an integer array A of size N, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

EXAMPLE:
Input: N = 4, A[ ] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11

// I wanna contribute this to DP folder , Please assign this to me

Minimum number of jumps to reach end of the array

LC. 45. Jump game II
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Dp: Maximum Sum Increasing Subsequence

Description: Tag Dynamic Programming
: find the sum of maximum sum subsequence of the given array

Add of Complex Number class

Unbounded Knapsack using C++

(DP Problem)
Knapsack with Duplicate Items :
Given a set of N items, each with a weight and a value, and a weight limit W. Find the maximum value of a collection containing any of the N items any number of times so that the total weight is less than or equal to W.

Please assign me.

Target Sum Subsets

You are given a number n, representing the count of elements and a given target value as input.
You are required to calculate and print true or false, if there is a subset the elements of which add up to given target or not.

Pigeonhole Sort

I would like to contribute Pigeonhole Sort in JAVA under the Sorting section.

Largest Arithmetic Subarray

A has an array of N non-negative integers. A wants to calculate maximum length of contiguous arithmetic subarray.

Arithmetic Subarray is an array that contains at least two integers and the difference between consecutive integers are equal. For example [9,10] , [3,3,3] and [9,7,5,3] arithmetic arrays.

Input: No. of test cases T
integer no N
array A[]

shortest-common-supersequence

(DP Problem Using C++)

Given two strings X and Y of lengths m and n respectively, find the length of the smallest string which has both, X and Y as its sub-sequences.
Note: X and Y can have both uppercase and lowercase letters.

Example 1

Input:
X = abcd, Y = xycd
Output: 6
Explanation: Shortest Common Supersequence
would be abxycd which is of length 6 and
has both the strings as its subsequences.

Submit any code related to Sorting and searching

Submit any code related to Sorting and searching
add under array/Sorting and Searching/

Updating README file with more relavant information

Adding problem of Tower of Hanoi

Checking wether graph is Bipartite or not

I want to contribute on this. Please assign me this

Add naive pattern searching algorithm

Add the naive pattern searching algorithm's implementation.

I want to add

Longest Common Subsequence

Longest Common Subsequence using C++ (DP Problem)

longest repeating subsequence

( DP Problem)
Given a string, find the length of the longest repeating subsequence such that the two subsequences don't have same string character at the same position, i.e., any i'th character in the two subsequences shouldn't have the same index in the original string.

Example 1:

Input: str = "axxxy"
Output: 2
Explanation: The longest repeating subsequenece
is "xx".

Dutch National Flag Algorithm

LC. 75. Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Wave Sort in c++

I would like to add wave sort in c++.
Please assign me.

Number of Connected Comonents in a graph

I would like to add Number of Conected Comonents in a graph in c++. Please assign it to me

Palindrome Linked list

Given the head of a singly linked list, return true if it is a palindrome.

Bitmasks on Array of string

Finding Number of pairs of strings in an array of strings so that on joining them the resulting string have all vowels

Traversing a grid using dfs

I would like to add this code. Please assign it to me.

Print Longest Common Subsequence (CPP)

(DP Problem Using C++)

Given two strings X and Y of lengths m and n respectively, PRINT LCS of strings X and Y
Example 1
Input:
X = aggtab, Y = gxtxayb
Output: gtab
Explanation: Longest Common Subsequence
would be gtab which is of length 4

// I wanna contribute this to DP folder , Please assign this to me

Add sum of array

minimum-number-of-deletions-and-insertion

( DP Problem)

Given two strings str1 and str2. The task is to remove or insert the minimum number of characters from/in str1 so as to transform it into str2. It could be possible that the same character needs to be removed/deleted from one point of str1 and inserted to some another point.

Example 1:

Input: str1 = "heap", str2 = "pea"
Output: 3
Explanation: 2 deletions and 1 insertion
p and h deleted from heap. Then, p is
inserted at the beginning One thing to
note, though p was required yet it was
removed/deleted first from its position
and then it is inserted to some other
position. Thus, p contributes one to the
deletion_count and one to the
insertion_count.

Tree Traversal

Inorder Preorder Postorder in cpp. Please assign this to me.

Kruskals algorithm in python

I want to add Kruskals algorithm in python
Please assign me the issue

Print A Cycle in A Directed Graph

Addition of the concept of Disjoint set Union.

Addition of DSU concept.
Often it is also called Union Find because of its two main operations.
I want to add the implementation details. Also,
I will add a question that involves this concept.

Please accept my improvement and assign me this issue. @arnab2001

Minimum cost for climbing stairs

Using Dynamic programming.
Given an integer array C where C[i] is the cost of ith step on a staircase. Once we pay the cost, we can either climb one or two steps.
we can either start from the step with index 0, or the step with index 1.

The output will be to return the minimum cost to reach the top of the floor.