Merge pull request #1161 from leonardogonfiantini/add-go-reverse-array

chore(Go): Add reverse array

.github/workflows/codespell.yml

@@ -8,7 +8,9 @@ jobs:
   codespell:
     runs-on: ubuntu-latest
     steps:
-      - uses: actions/checkout@v2
-      - uses: actions/setup-python@v2
+      - uses: actions/checkout@v3
+      - uses: actions/setup-python@v4
+        with:
+          python-version: 3.x
       - run: pip install codespell
       - run: codespell --ignore-words-list="ans,nnumber,nin,Hel" --quiet-level=2  --skip="**/**/package-lock.json,./docs/pt,./docs/es,./docs/tr,./.github,./algorithms/CSharp/test"

CONTRIBUTING.md

@@ -2,7 +2,7 @@
 
 This documentation aims to simplify and guide the way beginners make their first contribution. If you are looking to make your first contribution, follow the steps below.
 
-_If you're not comfortable with command line, [here are tutorials using GUI tools.](#tutorials-using-other-tools)_
+_If you're not comfortable with the command line, [here are tutorials using GUI tools.](#tutorials-using-other-tools)_
 
 <img align="right" width="300" src="https://user-images.githubusercontent.com/68538660/106238740-67a62b80-61cf-11eb-9892-6a0877a80fbf.png" alt="fork this repository" />
 
@@ -61,7 +61,7 @@ git checkout -b add-new-file
 
 ## Make necessary changes and commit those changes
 
-Now open add or edit file in a text editor. Add code for any existing algorithm in other language or add some new algorithms. Make sure to update correspond README.md file if needed. Now, save the file.
+Now open add or edit file in a text editor. Add code for any existing algorithm in other language or add some new algorithms. Make sure to update the corresponding README.md file if needed. Now, save the file.
 
 <img align="right" width="450" src="https://firstcontributions.github.io/assets/Readme/git-status.png" alt="git status" />
 

README.md

@@ -105,7 +105,7 @@ It can be any of the following ones
 
 #### Source Code File
 
-The source code files, should either be in `src/` folder (**Eg.** `src/main.cpp` or `src/main.js`) or the root folder (**Eg.** `palindrome.go` or `App.java`) where `ext` is the file extension for the specific programming language.
+The source code files should either be in `src/` folder (**Eg.** `src/main.cpp` or `src/main.js`) or the root folder (**Eg.** `palindrome.go` or `App.java`) where `ext` is the file extension for the specific programming language.
 
 Again, the source codes must conform to a valid file structure convention that the programming language enforces.
 

algorithms/CPlusPlus/Arrays/Largest-smallest.cpp

@@ -0,0 +1,20 @@
+#include <iostream>
+#include <algorithm>
+using namespace std;
+
+//simple approach:
+//sort the array in ascending order.
+//the first element would be the smallest and the last element would be the largest
+
+int main()
+{
+    int arr[]={1,2,3,4,5};
+    int n=sizeof(arr)/sizeof(arr[0]);
+    cout<<n<<endl;
+    sort(arr,arr+n);//sorting the array
+    //sort(a,a+n)-->a is the name of the array and n is the size of array a
+    cout<<arr[0]<<" --> smallest number "<<endl;
+    cout<<arr[n-1]<<" --> largest number "<<endl;
+
+    return 0;
+}

algorithms/CPlusPlus/Arrays/balanced-parenthesis.cpp

@@ -0,0 +1,70 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+bool areBracketsBalanced (string expr) 
+{
+
+  stack < char >s;
+  char x;
+
+
+  // Traversing the Expression
+  for (int i = 0; i < expr.length (); i++)
+   if (expr[i] == '(' || expr[i] == '[' ||expr[i] == '{')
+  {
+   // Push the element in the stack
+   s.push (expr[i]);
+   continue;
+  }
+
+  // IF current current character is not opening
+  // bracket, then it must be closing. So stack
+  // cannot be empty at this point.
+ 
+  if (s.empty ()) 
+    return false;
+
+switch (expr[i])
+{
+
+ case ')': // Store the top element in a
+            x = s.top ();
+            s.pop ();
+
+  if (x == '{' || x == '[')
+   return false;
+
+   break;
+
+case '}': // Store the top element in b
+          x = s.top ();
+          s.pop ();
+   if (x == '(' || x == '[') 
+    return false;
+    break;
+case ']': x = s.top ();
+          s.pop ();
+  if (x == '(' || x == '{')
+     return false;
+     break;
+   }
+ }
+return (s.empty ());
+}
+// Driver code
+int main () 
+{
+  string expr = "{()}[]";
+ // Function call
+ if (areBracketsBalanced (expr))
+  cout << "Balanced";
+else
+  cout << "Not Balanced";
+  return 0;
+}
+
+// Output:-
+// Enter the brackets to check if its balanced or not : [{}] 
+// Balanced
+// Enter the brackets to check if its balanced or not : {]
+Not Balanced

algorithms/CPlusPlus/Arrays/max-subarray-sum.cpp

@@ -20,7 +20,7 @@ int maxSubArrSum_A(int a[],int n){
     return maxSum;
 }
 
-// Appraoch B - Cumulative Sum Approach O(n^2)
+// Approach B - Cumulative Sum Approach O(n^2)
 int maxSubArrSum_B(int a[],int n){
     int currSum[n+1]; currSum[0] = 0;
     for(int i=1;i<=n;++i){

algorithms/CPlusPlus/Arrays/specialindex2.cpp

@@ -0,0 +1,65 @@
+/*
+@author: nandinisahu407
+special index-> if after deleting element from index i , sum of even index=sum of odd index
+approach->
+after deleting ,previous element at odd index will be now at even index and vice versa
+s_odd= odd[0 to i]+ even[i+1 to len]
+s_even=even[0 to i]+odd[i+1 to len]
+
+*/
+#include<iostream>
+using namespace std;
+ 
+int main(){
+    int num;
+    cout<<"enter length"<<endl;
+    cin>>num;
+    vector <int> arr (num);
+
+    for(int i=0;i<num;i++){
+        cin>>arr[i];
+    }
+
+    int count=0;
+    int s_even,s_odd;
+    for(int i=0;i<num;i++){ //checking whether special index or not
+        s_even=0,s_odd=0;
+
+        for(int j=0;j<i;j++){   // from index[0,i]
+            if(j%2==0){
+                s_even+=arr[j];
+            }
+            else{
+                s_odd+=arr[j];
+            }
+        }
+        for(int j=i+1;j<num;j++){    //from index[i+1,len]
+            if(j%2==0){
+                s_odd+=arr[j];
+            }
+            else{
+                s_even+=arr[j];
+            }
+        }
+
+        if(s_even==s_odd){    //checking whether sum of even index=sum of odd index
+            cout<<"\n special index found at: "<<i;
+            count++;
+        }
+        else{
+            continue;
+        }
+
+    }
+    cout<<"\n total special index: "<<count;   //displaying
+    return 0;
+}
+/* ----INPUT-----
+enter length 6
+4 3 2 7 6 -2
+----- OUTPUT------
+special index found at: 0
+special index found at: 2
+total special index:2
+*/
+//time complexity:o(n^2)

algorithms/CPlusPlus/Backtracking/rat-in-a-maze-problem.cpp

@@ -0,0 +1,60 @@
+#include<iostream>
+using namespace std;
+
+bool issafe(int** arr, int x, int y, int n){
+    if(x<n && y<n && arr[x][y]==1){
+        return true;
+    }
+    return false;
+}
+bool ratinMaze(int** arr, int x, int y, int n, int** solArr){
+    if(x==n-1 && y==n-1){
+        solArr[x][y]=1;
+        return true;
+    }
+    if(issafe(arr, x, y, n)){
+        solArr[x][y]=1;
+        if(ratinMaze(arr, x+1, y, n, solArr)){
+            return true;
+        }
+        if(ratinMaze(arr, x, y+1, n, solArr)){
+            return true;
+        }
+        solArr[x][y]=0;
+        return false;
+    }
+    return false;
+}
+
+int main(){
+    int n;
+    cin>>n;
+    int** arr=new int*[n];
+    for(int i=0; i<n; i++){
+        arr[i]=new int[n];
+    }
+    for(int i=0; i<n; i++){
+        for(int j=0; j<n; j++){
+            cin>>arr[i][j];
+        }
+    }
+    int** solArr=new int*[n];
+    for(int i=0; i<n; i++){
+        solArr[i] = new int[n];
+        for(int j=0; j<n; j++){
+            solArr[i][j]=0;
+        }
+    }
+    if(ratinMaze(arr, 0, 0, n, solArr)){
+        for(int i=0; i<n; i++){
+        for(int j=0; j<n; j++){
+            cout<<solArr[i][j];
+        }cout<<endl;
+
+        }
+    }
+    return 0;
+}
+
+/* Time complexity: O(2^(n^2)). The recursion can run upper-bound 2^(n^2) times.
+   Space Complexity: O(n^2). Output matrix is required so an extra space of size n*n is needed. */

algorithms/CPlusPlus/Dynamic-Programming/rod-cutting.cpp

@@ -0,0 +1,76 @@
+// Rod Cutting Problem
+// Given a rod of length n and a list of rod prices of length i, where 1 <= i <= n, find the optimal way to cut the rod into smaller rods to maximize profit.
+
+// Rod Cutting Optimal Approach
+//     We will solve this problem in a bottom-up manner. (iteratively)  
+//     In the bottom-up approach, we solve smaller subproblems first, then move on to larger subproblems.  
+//     The following bottom-up approach computes dp[i], which stores maximum profit achieved from the rod of length i from 1 to len. 
+//     It uses the value of smaller values i already computed.
+
+// Space complexity: O(n)
+// Time complexity: O(n^n)
+
+
+// Solution
+#include <iostream>
+#include <vector>
+#include <climits>
+
+using namespace std;
+
+// Function to find the maximum revenue from cutting a rod of length (len)
+// where the rod of length (i) has cost (prices[i - 1])
+int RodCutting(vector<int> &prices, int len)
+{
+    // (dp) stores the maximum revenue achieved from cutting a rod of length (from 1 to len)
+    vector<int> dp(len + 1, 0);
+    // If the rod length is negative (invalid) or zero there's no revenue from it
+    if (len <= 0)
+    {
+        return 0;
+    }
+    // Cut a rod of length (i)
+    for (int i = 1; i <= len; i++)
+    {
+        // divide the rod of length (i) into two rods of lengths (j) and (i - j)
+        // and store the maximum revenue
+        for (int j = 0; j < i; j++)
+        {
+            // (dp[i]) stores the maximum revenue achieved from cutting a rod of length (i)
+            dp[i] = max(dp[i], prices[j] + dp[i - j - 1]);
+        }
+    }
+    // (dp[len]) contains the maximum revenue from cutting a rod of length (len)
+    return dp[len];
+}
+
+int main()
+{
+    int len;
+    cout << "Enter the rod length :";
+    cin >> len;
+
+    vector<int> prices(len);
+    for (int i = 1; i <= len; i++)
+    {
+        cout << "Enter the price of the rod of length " << i << " :";
+        cin >> prices[i - 1];
+    }
+
+    cout << "Maximum revenue = " << RodCutting(prices, len);
+    return 0;
+}
+
+
+// Input and output:
+// 1. prices[] = [1, 5, 8, 9, 10, 17, 17, 20]  
+//        rod length = 4  
+//        Best: Cut the rod into two pieces of length 2 each to gain revenue of 5 + 5 = 10
+       
+//     2. prices[] = [1, 5, 8, 9, 10, 17, 17, 20]
+//        rod length = 8
+//        Best: Cut the rod into two pieces of length 2 and 6 to gain revenue of 5 + 17 = 22
+       
+//     3. prices[] = [3, 5, 8, 9, 10, 17, 17, 20]
+//        rod length = 8
+//        Best: Cut the rod into eight pieces of length 1 to gain revenue of 8 * 3 = 24

algorithms/CPlusPlus/Graphs/dijkstra.cpp

@@ -1,99 +1,177 @@
-//Dijkstra's algorithm
-//implemented in the context of a directed graph
-#include <bits/stdc++.h>
-using namespace std;
+#include <cstddef>
+#include <limits>
 
-int dijkstra(vector<vector<pair<int,int>>>& graph, int start, int end){
-    //return value(-1 if endpoint is unreachable)
-    int ret=-1;
+//I highly recommend to create matrix class
+template <typename T>
+inline T& getMatrixElement( T* matrix, size_t size, 
+                            size_t row, size_t column)
+{
+    return *(matrix + row * size + column);
+}
 
-    //storing cost(distance) of each vertex, set initial value as -1
-    vector<int> dist(graph.size(),-1);
+template <typename T>
+inline void setMatrixElement ( T* matrix, size_t size,
+                               size_t row, size_t column, T element)
+{
+    *(matrix + row * size + column) = element;
+}
 
-    //priority queue to store traversing vertices and cost values
-    //data will be stored in the format of: {cost, current vertex}
-    //entry with minimum cost will always be on top
-    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
-    pq.push({0,start});
+template <typename T>
+size_t minDistance(T* vector, bool* states, size_t size)
+{
+    size_t index;
+    T min = std::numeric_limits<T>::max();
 
-    while(!pq.empty()){
-        int cVertex, cCost;
-        tie(cCost,cVertex) = pq.top();
-        pq.pop();
-
-        //vertex already visited with lower cost -> continue
-        if(dist[cVertex]!=-1&&dist[cVertex]<=cCost)continue;
-        //otherwise we update our current cost(distance)
-        dist[cVertex]=cCost;
-
-        if(cVertex==end){
-            ret=cCost;
-            break;
+    for(size_t i = 0; i < size; i++)
+    {
+        if (states[i] == false && vector[i] <= min)
+        {
+            min = vector[i];
+            index = i;
         }
+    }
 
-        for(pair<int,int> nPair : graph[cVertex]){
-            int nVertex, nCost;
-            tie(nVertex,nCost) = nPair;
-            if(dist[nVertex]!=-1&&dist[nVertex]<=cCost+nCost){
-                //the next vertex has already been traversed with lower cost
-                continue;
+    return index;
+}
+
+template <typename T>
+T* dijkstra (T* matrix, size_t matrix_size, size_t start_pos)
+{
+    T* result = new T [matrix_size];
+    // I recoment use dynamic bitset from boost library
+    bool* states = new bool[matrix_size];
+
+    //Set All elements to max value and all state to False
+    for(size_t i = 0; i < matrix_size; i++)
+    {
+        result[i] = std::numeric_limits<T>::max();
+        states[i] = false;
+    }
+    
+    result[0] = 0;
+
+    for(size_t i = 0; i < matrix_size; i++)
+    {
+        size_t index = minDistance(result, states, matrix_size);
+        states[index] = true;
+
+        for(size_t j = 0; j < matrix_size; j++)
+        {
+            if (
+                !states[j] &&
+                getMatrixElement(matrix, matrix_size, index, j) &&
+                result[index] +  getMatrixElement(matrix, matrix_size, index, j) < result[j]
+                //result.get(index) != std::numeric_limits<T>::max()
+                )
+            {
+                T new_val = result[index] + getMatrixElement(matrix, matrix_size, index, j);
+                result[j] = new_val;
             }
-            //otherwise we add a new entry to the priority queue
-            pq.push({nCost+cCost,nVertex});
         }
     }
-    return ret;
+
+    return result;
 }
 
-int main(){
-    //number of vertices(V) and edges(E)
-    int V, E;
-    cout << "Enter the number of vertices: ";
-    cin >> V;
-    cout << "Enter the number of edges: ";
-    cin >> E;
-    cout << "Enter each edge information in the format of: \n";
-    cout << "(Source vertex number) (Destination vertex number) (cost)\n";
-    //Adjacency list
-    //data will be stored in the format of: {destination,cost}
-    //with the first index as the source
-    vector<vector<pair<int,int>>> graph(V+1,vector<pair<int,int>>());
-    while(E--){
-        int source, dest, cost;
-        cin >> source >> dest >> cost;
-        graph[source].push_back({dest,cost});
+#include <iostream>
+
+
+//function declaration below
+//Generate and std::cout << matrix
+void getExampleMatrix(int*& matrix_out, size_t& size_out);
+
+int main()
+{
+    //I highly recommend to create matrix class
+
+    size_t size;
+    std::cout << "Graph Size: ";
+    std::cin >> size; 
+
+    int* user_graph_matrix = new int [size*size];
+
+    for(size_t i = 0; i < size; i++)    
+    {
+        for(size_t j = 0; j < size; j++)    
+        {
+            int temp;
+            std::cout << "(" << j << ", " << i << ") = ";
+            std::cin >> temp;
+
+            setMatrixElement(user_graph_matrix, size, i, j, temp);
+        }
     }
-    //starting point(start), ending point(end)
-    int start, end;
-    cout << "Enter the starting point: ";
-    cin >> start;
-    cout << "Enter the ending point: ";
-    cin >> end;
-    int answer = dijkstra(graph,start,end);
-    if(answer==-1){
-        cout << "Shortest path from " << start << " to " << end << " does not exist." << endl;
+
+
+    size_t start_element = std::numeric_limits<size_t>::max();
+    while (true)
+    {
+        std::cout << "Choose First Element: ";
+        std::cin >> start_element;
+
+        if(start_element < size)
+            break;
+        
+        std::cout << "[Warning] Number of element is greater that matrix size\n";
     }
-    else
-        cout << "The minimum cost for the shortest path is: " << answer << endl;
+
+    auto ex_result = dijkstra(user_graph_matrix, size, start_element);
+    for(size_t i = 0; i < size; i++)
+    {
+        std::cout << ex_result[i] << " ";
+    }
+    std::cout << "\n";
+
+    // !!! Unkoment for example matrix
+
+    // size_t ex_size;
+    // int* ex_matrix;
+    
+    // getExampleMatrix(ex_matrix, ex_size);
+
+    // auto ex_result = dijkstra(ex_matrix, ex_size, 0);
+    // for(size_t i = 0; i < ex_size; i++)
+    // {
+    //     std::cout << ex_result[i] << " ";
+    // }
+    // std::cout << "\n";
 }
-//Time complexity: O(ElogV)
-//Space complexity: O(V+E)
 
-/*
-Sample Input
-5
-8
-1 2 2
-1 3 3
-1 4 1
-1 5 10
-2 4 2
-3 4 1
-3 5 1
-4 5 3
-1
-5
+void getExampleMatrix(int*& matrix_out, size_t& size_out)
+{
+    size_t size = 4;
+    int* graph_matrix = new int[size*size];
 
-Output(minimum cost)
-4
-*/
+    setMatrixElement(graph_matrix, size, 0, 0, 0);
+    setMatrixElement(graph_matrix, size, 0, 1, 0);
+    setMatrixElement(graph_matrix, size, 0, 2, 3);
+    setMatrixElement(graph_matrix, size, 0, 3, 1);
+
+    setMatrixElement(graph_matrix, size, 1, 0, 0);
+    setMatrixElement(graph_matrix, size, 1, 1, 0);
+    setMatrixElement(graph_matrix, size, 1, 2, 0);
+    setMatrixElement(graph_matrix, size, 1, 3, 5);
+
+    setMatrixElement(graph_matrix, size, 2, 0, 3);
+    setMatrixElement(graph_matrix, size, 2, 1, 0);
+    setMatrixElement(graph_matrix, size, 2, 2, 0);
+    setMatrixElement(graph_matrix, size, 2, 3, 1);
+
+    setMatrixElement(graph_matrix, size, 3, 0, 1);
+    setMatrixElement(graph_matrix, size, 3, 1, 5);
+    setMatrixElement(graph_matrix, size, 3, 2, 1);
+    setMatrixElement(graph_matrix, size, 3, 3, 0);
+
+    for(size_t i = 0; i < size; i++)
+    {
+        for (size_t j = 0; j < size; j++)
+        {
+            std::cout << getMatrixElement(graph_matrix, size, i, j) << " ";
+        }
+        std::cout << "\n";
+    }
+    std::cout << "\n";
+
+    size_out = size;
+    matrix_out = graph_matrix;
+}

algorithms/CPlusPlus/Linked-Lists/reverse-the-list-using-stack.cpp

@@ -0,0 +1,97 @@
+/* 
+Algorithm: 
+    (i) Traverse the list and push all of its nodes onto a stack.
+    (ii) Traverse the list from the head node again and pop a value 
+        from the stack top and connect them in reverse order.
+    
+    
+TIME COMPLEXITY: O(n), as we are traversing over the linked list of size N using a while loop.
+SPACE COMPLEXITY: o(n), as we are using stack of size N in worst case which is extra space.
+
+ */
+
+
+#include <iostream>
+#include <stack>
+
+using namespace std;
+
+class Node {
+public:
+    int data;
+    Node *next;
+};
+Node *head;
+
+void Print(Node* n);
+void RevList();
+
+int main() {
+    head = NULL;
+
+    Node *first = new Node;
+    Node *second = new Node;
+    Node *third = new Node;
+    Node *fourth = new Node;
+    Node *fifth = new Node;
+    Node *sixth = new Node;
+    Node *seventh = new Node;
+
+    head = first;
+
+    first->data = 10;
+    first->next = second;
+    
+    second->data = 20;
+    second->next = third;
+    
+    third->data = 30;
+    third->next = fourth;
+    
+    fourth->data = 40;
+    fourth->next = fifth;
+
+    fifth->data = 50;
+    fifth->next = sixth;
+
+    sixth->data = 60;
+    sixth->next = seventh;
+
+    seventh->data = 70;
+    seventh->next = NULL;
+
+    Print(head);
+
+    RevList();
+    cout<<endl;
+    Print(head);
+
+    return 0;
+}
+
+void Print(Node* n){
+    if(n==NULL){
+        return;
+    }
+    cout<<n->data<<" ";
+    Print(n->next);
+}
+void RevList() {
+    if(head == NULL) return;
+    stack<Node *> st;
+    Node * temp = head;
+    while(temp!= NULL){
+        st.push(temp);
+        temp = temp->next;
+    }
+    temp = st.top();
+    head = temp;
+    st.pop();
+    
+    while(!st.empty()) {
+        temp->next = st.top();
+        temp = temp->next;
+        st.pop();
+    }
+    temp->next = NULL;
+}

algorithms/CPlusPlus/Linked-Lists/reverseInGroupsOfK.cpp

@@ -0,0 +1,79 @@
+// Description := Reverse a linkedlist in groups of size K .
+
+// Time and space complexity :-
+// Time Complexity = O(N) and Space Complexity = O(N)
+
+// Example :-
+// Input: 1->2->3->4->5->6->7->8->NULL, K = 3 
+// Output: 3->2->1->6->5->4->8->7->NULL 
+
+#include<bits/stdc++.h>
+using namespace std;
+
+class Node{
+    public:
+    int data;
+    Node* next;
+};
+
+void push(Node* &head_ref, int new_data)
+{
+    Node* new_node = new Node();
+ 
+    new_node->data = new_data;
+ 
+    new_node->next = head_ref;
+ 
+    head_ref = new_node;
+}
+
+void printList(Node* node)
+{
+    while (node != NULL) {
+        cout << node->data << " ";
+        node = node->next;
+    }
+}
+
+Node* kReverse(Node* &head, int k) {
+  
+    // base case
+    if(head == NULL) {
+        return NULL;
+    }
+    
+    Node* next = NULL;
+    Node* curr = head;
+    Node* prev = NULL;
+    int count= 0;
+    
+    while( curr != NULL && count < k ) {
+        next = curr -> next;
+        curr -> next = prev;
+        prev = curr;
+        curr = next;
+        count++;
+    }
+    
+    if(next != NULL) {
+        head -> next = kReverse(next,k);
+    }
+    return prev;
+}
+
+int main(){
+  Node* head=NULL;
+  Node* ans =head;
+  push(head,1);
+  push(head,2);
+  push(head,3);
+  push(head,4);
+  push(head,5);
+  push(head,6);
+  push(head,7);
+  push(head,8);
+  printList(head);
+  head = kReverse(head,3);
+  cout<<endl;
+  printList(head);
+}

algorithms/CPlusPlus/README.md

@@ -31,8 +31,9 @@
 - [Next permutation](Arrays/next-permutation.cpp)
 - [Maximum Minimum Average of numbers](Arrays/max-min-avg.cpp)
 - [Sparse Matrix](Arrays/sparse_matrix.cpp)
-
-
+- [Balanced Parenthesis](Arrays/balanced-parenthesis.cpp)
+- [Find special index](Arrays/specialindex2.cpp)
+- [Largest and smallest number in an array](Arrays/Largest-smallest.cpp)
 
 ## Dynamic-Programming
 
@@ -42,6 +43,7 @@
 - [Matrix chain Multiplication](Dynamic-Programming/matrix-chain-multiplication.cpp)
 - [Edit Distance](Dynamic-Programming/edit-distance.cpp)
 - [Fibonacci](Dynamic-Programming/fibonacci.cpp)
+- [Rod Cutting](Dynamic-Programming/rod-cutting.cpp)
 
 ## Graphs
 
@@ -78,7 +80,8 @@
 - [Find Merge Point of two singly linked list](Linked-Lists/Find-Merge-Point.cpp)
 - [Segregate Even Odd Nodes of linked list](Linked-Lists/segregate-even-odd-nodes-of-linked-list.cpp)
 - [Remove Duplicate in Sorted linked list](Linked-Lists/remove-duplicates-in-sorted-linked-list.cpp)
-
+- [Reverse the linked list using stack](Linked-Lists/reverse-the-list-using-stack.cpp)
+- [Reverse the linked list in groups of K](Linked-Lists/reverse-the-list-in-groups-of-k.cpp)
 ## Searching
 
 - [Linear Search](Searching/linear-search.cpp)
@@ -99,6 +102,7 @@
 - [Infix to postfix expression conversion](Stacks/infix-to-postfix.cpp)
 - [Stock Span Problem using Stacks](Stacks/stock-span-problem.cpp)
 - [Prefix to Postfix expression conversion](Stacks/prefix_to_postfix.cpp)
+- [Redundant Parenthesis](Stacks/redundant-parenthesis.cpp)
 
 ## Sorting
 
@@ -133,6 +137,7 @@
 - [Longest common prefix](Strings/longest-common-prefix.cpp)
 - [First unique character in the string](Strings/first-unique-character.cpp)
 - [Sliding Window to match target string](Strings/sliding-window.cpp)
+- [Reverse String Wordwise](Strings/ReverseTheStringWordwise.cpp)
 
 ## Trees
 
@@ -155,6 +160,9 @@
 ## Trie
 
 - [Trie for searching](Trie/trie_search.cpp)
+- [Trie for insert search and prefix_search](Trie/trie_insert_search_startWith.cpp)
+- [Trie for delete](Trie/trie_delete.cpp)
+- [Find Words Matching Pattern Dictionary](Trie/find_all_words_matching_pattern_in_given_dictionary.cpp)
 
 # Maths
 
@@ -211,3 +219,4 @@
 ## Backtracking
 
 - [N-Queens Problem](Backtracking/n-queens.cpp)
+- [Rat In A Maze Problem](Backtracking/rat-in-a-maze-problem.cpp)

algorithms/CPlusPlus/Stacks/redundant-parenthesis.cpp

@@ -0,0 +1,74 @@
+//  RedundantParenthesis
+// Given a string of balanced expression, find if it contains a redundant parenthesis or not. A set of parenthesis are redundant if the same sub-expression is surrounded by unnecessary or multiple brackets. Print True if redundant, else False.
+
+// Algorithm
+// 1. We iterate through the given expression and for each character in the expression, if the character is an open parenthesis ‘(‘ or any operators, we push it to the stack.
+// 2. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found. 
+// For any sub-expression of expression, if we are able to pick any sub-expression of expression surrounded by (), then we again left with () as part of string, we have redundant braces. 
+// We iterate through the given expression and for each character in the expression, if the character is an open parenthesis ‘(‘ or any of the operators or operands, we push it to the stack. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found. 
+// Now for redundancy two condition will arise while popping- 
+// 1. If immediate pop hits an open parenthesis ‘(‘, then we have found a duplicate parenthesis. For example, (((a+b))+c) has duplicate brackets around a+b. When we reach the second “)” after a+b, we have “((” in the stack. Since the top of stack is an opening bracket, we conclude that there are duplicate brackets. 
+// 2. If immediate pop doesn’t hit any operand(‘*’, ‘+’, ‘/’, ‘-‘) then it indicates the presence of unwanted brackets surrounded by expression. For instance, (a)+b contain unwanted () around a thus it is redundant. 
+
+
+
+// solution
+#include <bits/stdc++.h>
+using namespace std;
+
+int main()
+{
+    cout << "Enter the string:" << endl;
+    string s;
+    cin >> s;
+    // create a stack of characters
+    stack<char> st;
+    bool ans = false;
+
+    // Iterate through the given expression
+    for (int i = 0; i < s.size(); i++)
+    {
+        if (s[i] == '+' or s[i] == '-' or s[i] == '*' or s[i] == '/')
+        {
+            st.push(s[i]);
+        }
+        else if (s[i] == '(')
+        {
+            // if current character is close parenthesis '('
+            st.push(s[i]);
+        }
+        else if (s[i] == ')')
+        {
+            // if current character is close parenthesis ')'
+            if (st.top() == '(')
+            {
+                ans = true;
+            }
+            while (st.top() == '+' or st.top() == '-' or st.top() == '*' or st.top() == '/')
+            {
+                st.pop();
+            }
+            st.pop();
+        }
+    }
+
+    if (ans)
+    {
+        cout << "True";
+    }
+    else
+    {
+        cout << "False";
+    }
+}
+
+
+// Input :
+// For example:
+// 1. ((a+b))
+// 2. (a+b*(c-d))
+
+// Output:
+// 1. True, ((a+b)) can reduced to (a+b), this is Redundant
+// 2. False, (a+b*(c-d)) doesn't have any redundant or multiple
+// brackets

algorithms/CPlusPlus/Strings/ReverseTheStringWordwise.cpp

@@ -0,0 +1,48 @@
+// Description :- Given a string, the task is to reverse the order of the words in the given string. 
+// Example :-
+// Input 1:
+//    A = "the sky is blue"
+// Input 2:
+//    A = "this is ib"
+// Output 1:
+//    "blue is sky the"
+// Output 2:
+//    "ib is this"
+
+
+// Time Complexity = O(N), Space Complexity = O(N)
+
+#include<bits/stdc++.h>
+using namespace std;
+
+string solve(string s) {
+   vector<string>v;
+        string str="";
+        for(int i=0;i<s.length();i++){
+            if(s[i]!=' '){
+                str+=s[i];
+            }
+            else if(str!="" && s[i]==' '){
+                v.push_back(str);
+                str="";
+            }
+        }
+        if(str!=""){
+            v.push_back(str);
+        }
+        str="";
+        for(int i=v.size()-1;i>0;i--){
+                str+=v[i];
+                str+=' ';
+        }
+        str+=v[0];
+        return str;
+}
+
+int main()
+{
+    string s;
+    getline(cin, s);
+    cout<<solve(s);
+    return 0;
+}

algorithms/CPlusPlus/Trie/find_all_words_matching_pattern_in_given_dictionary.cpp

@@ -0,0 +1,120 @@
+#include <iostream>
+#include <vector>
+#include <unordered_map>
+#include <unordered_set>
+#include <string>
+using namespace std;
+ 
+// Data structure to store a Trie node
+struct TrieNode
+{
+    // each node stores a map to its child nodes
+    unordered_map<char, TrieNode*> map;
+ 
+    // true when the node is a leaf node
+    bool isLeaf = false;
+ 
+    // collection to store a complete list of words in the leaf node
+    unordered_set<string> word;
+};
+ 
+// Function to insert a string into a Trie
+void insert(TrieNode*& head, string word)
+{
+    if (head == nullptr) {
+        head = new TrieNode();
+    }
+ 
+    // start from the head node
+    TrieNode* curr = head;
+    for (char c: word)
+    {
+        // insert only uppercase characters
+        if (isupper(c))
+        {
+            // create a new node if the path doesn't exist
+            if (curr->map.find(c) == curr->map.end()) {
+                curr->map[c] = new TrieNode();
+            }
+ 
+            // go to the next node
+            curr = curr->map[c];
+        }
+    }
+ 
+    // mark the current node as a leaf
+    curr->isLeaf = true;
+ 
+    // push the current word into the set associated with a leaf node
+    (curr->word).insert(word);
+}
+ 
+// Function to print all children of a given Trie node
+void printAllWords(TrieNode* root)
+{
+    // if the current node is a leaf, print all words associated with it
+    if (root->isLeaf)
+    {
+        unordered_set<string> collection = root->word;
+        for (string s: collection) {
+            cout << s << endl;
+        }
+    }
+ 
+    // recur for all children of the root node
+    for (auto pair: root->map)
+    {
+        TrieNode* child = pair.second;
+        if (child) {
+            printAllWords(child);
+        }
+    }
+}
+ 
+// Function to print all words in the CamelCase dictionary, which
+// matches the given pattern
+void findAllWords(vector<string> const &dictionary, string pattern)
+{
+    // base case
+    if (dictionary.size() == 0) {
+        return;
+    }
+ 
+    // Trie head node
+    TrieNode* head = nullptr;
+ 
+    // construct a Trie from the given dictionary
+    for (string s: dictionary) {
+        insert(head, s);
+    }
+ 
+    // search for the given pattern in the Trie
+    TrieNode* curr = head;
+    for (char c: pattern)
+    {
+        // move to the child node
+        curr = curr->map[c];
+ 
+        // if the given pattern is not found (reached end of a path in the Trie)
+        if (curr == nullptr) {
+            return;
+        }
+    }
+ 
+    // print all words matching the given pattern
+    printAllWords(curr);
+}
+ 
+int main()
+{
+    vector<string> dictionary {
+        "Hi", "HiTech", "HiTechCity", "Techie", "TechieDelight",
+        "Hello", "HelloWorld", "HiTechLab"
+    };
+ 
+    string pattern = "HT";
+ 
+    findAllWords(dictionary, pattern);
+ 
+    return 0;
+}

algorithms/CPlusPlus/Trie/trie_delete.cpp

@@ -0,0 +1,44 @@
+#include<bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+#define inf 1e9;
+#define inf2 2e18;
+
+
+
+struct custom_hash {
+   static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);}
+   size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); }
+};
+
+
+
+struct TrieNode{ TrieNode* child[26]; bool isEnd;
+    TrieNode(){ isEnd = false; for(int i = 0; i<26; i++){ child[i] = NULL; } }
+};
+struct TrieNode* rootTrie;
+void addTrie(string& s){ TrieNode* curr = rootTrie; for(int i = 0; i<s.length(); i++){ int n = s[i] - 'a';if(curr->child[n] == NULL){curr->child[n] = new TrieNode();} curr = curr->child[n]; } curr->isEnd = true; }
+bool searchTrie(string& s){TrieNode* curr = rootTrie;for(int i = 0; i<s.length(); i++){int n = s[i] - 'a';if(!curr->child[n]) return false;curr = curr->child[n];}return curr->isEnd;}
+bool startsWithTrie(string s) {int n = s.length();TrieNode* curr = rootTrie;for(int i  =0 ; i<n; i++){int k = s[i] - 'a';if(curr->child[k] == NULL) return false;curr = curr->child[k];}return true;}
+bool isEmpty(TrieNode* rootTrie){ for (int i = 0; i < ALPHABET_SIZE; i++){if(rootTrie->child[i])return false;}return true;}
+void remove(TrieNode* rootTrie, string key, int depth = 0){if (!rootTrie)return NULL;if (depth == key.size()) {if (rootTrie->isEnd)rootTrie->isEnd = false;if (isEmpty(rootTrie)) {delete (rootTrie);rootTrie = NULL;}return rootTrie;}int index = key[depth] - 'a';rootTrie->child[index] = remove(rootTrie->child[index], key, depth + 1);if (isEmpty(rootTrie) && rootTrie->isEnd == false) {delete (rootTrie);rootTrie = NULL;}return rootTrie;}
+
+
+int main(){
+//Jai Shree Ram
+    ios_base::sync_with_stdio(false);
+    cin.tie(NULL);
+    
+    string keys[] = { "the", "a", "there", "answer", "any", "by", "bye", "their", "hero", "heroplane" };
+    int n = sizeof(keys) / sizeof(keys[0]);
+ 
+    for (int i = 0; i < n; i++)
+        insert(rootTrie, keys[i]);
+ 
+    search(rootTrie, "the") ? cout << "Yes\n" : cout << "No\n";
+    search(rootTrie, "these") ? cout << "Yes\n" : cout << "No\n";
+ 
+    remove(rootTrie, "heroplane");
+    search(rootTrie, "hero") ? cout << "Yes\n" : cout << "No\n";
+    return 0;
+}

algorithms/CPlusPlus/Trie/trie_insert_search_startWith.cpp

@@ -0,0 +1,44 @@
+#include<bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+#define inf 1e9;
+#define inf2 2e18;
+
+
+
+struct custom_hash {
+   static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);}
+   size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); }
+};
+
+
+
+struct TrieNode{ TrieNode* child[26]; bool isEnd;
+    TrieNode(){ isEnd = false; for(int i = 0; i<26; i++){ child[i] = NULL; } }
+};
+struct TrieNode* rootTrie;
+void addTrie(string& s){ TrieNode* curr = rootTrie; for(int i = 0; i<s.length(); i++){ int n = s[i] - 'a';if(curr->child[n] == NULL){curr->child[n] = new TrieNode();} curr = curr->child[n]; } curr->isEnd = true; }
+bool searchTrie(string& s){TrieNode* curr = rootTrie;for(int i = 0; i<s.length(); i++){int n = s[i] - 'a';if(!curr->child[n]) return false;curr = curr->child[n];}return curr->isEnd;}
+bool startsWithTrie(string s) {int n = s.length();TrieNode* curr = rootTrie;for(int i  =0 ; i<n; i++){int k = s[i] - 'a';if(curr->child[k] == NULL) return false;curr = curr->child[k];}return true;}
+
+
+
+int main(){
+//Jai Shree Ram
+    ios_base::sync_with_stdio(false);
+    cin.tie(NULL);
+    
+    string keys[] = {"the", "a", "there", "answer", "any", "by", "bye", "their" };
+    int n = sizeof(keys)/sizeof(keys[0]);
+    struct TrieNode *root = getNode();
+
+    for (int i = 0; i < n; i++) insert(root, keys[i]);
+ 
+    char output[][32] = {"Not present in trie", "Present in trie"};
+ 
+    cout<<"the"<<" --- "<<output[search(root, "the")]<<endl;
+    cout<<"these"<<" --- "<<output[search(root, "these")]<<endl;
+    cout<<"their"<<" --- "<<output[search(root, "their")]<<endl;
+    cout<<"thaw"<<" --- "<<output[search(root, "thaw")]<<endl;
+    return 0;
+}

algorithms/Go/arrays/reverse-array.go

@@ -0,0 +1,19 @@
+//Description : This program reverses array elements by swapping the first half part of the array
+//Time Complexity : O(n/2), where n is the array size
+//Auxiliary Space : O(1)
+
+package arrays
+
+import ("fmt")
+
+func ReverseArray(arr []int) {
+    // get the length of the array
+    n := len(arr)
+    // iterate over half of the array and swap corresponding elements
+    for i := 0; i < n/2; i++ {
+        arr[i], arr[n-i-1] = arr[n-i-1], arr[i]
+    }
+    // print the reversed array
+    fmt.Println(arr)
+}
+

algorithms/Java/Maths/permutation_sequence.java

@@ -0,0 +1,178 @@
+import java.util.*;
+
+/*
+Problem Name - Permutation Sequence
+
+Description
+The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
+
+By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
+
+1.  "123"
+2.  "132"
+3.  "213"
+4.  "231"
+5.  "312"
+6.  "321"
+Given n and k, return the kth permutation sequence.
+
+Sample Cases:
+Example 1:
+Input: n = 3, k = 3
+Output: "213"
+
+Example 2:
+Input: n = 4, k = 9
+Output: "2314"
+
+Example 3:
+Input: n = 3, k = 1
+// Output: "123"
+
+Constraints:
+
+ 1 <= n <= 9
+ 1 <= k <= n!
+
+You can also practice this question on LeetCode(https://leetcode.com/problems/permutation-sequence/)*/
+
+
+/***Brute Force is to form an array of n size and then compute all the permutations and store it in the list and then trace it with (k-1)**
+**Caution : the permutations should be in sorted order to get the answer**
+*This will give TLE as we have to calculate all the permutations*
+```
+class Solution {
+    public String getPermutation(int n, int k) {
+        int ar[] = new int[n];
+        
+        for(int x=1;x<=n;x++)
+            ar[x-1]=x;
+        List<List<Integer>> ans=new ArrayList<>();
+        backtrack(ans,new ArrayList<>(),ar);
+        String s="";
+        for(int x:ans.get(k-1))
+            s+=x;
+        
+        return s;
+     }
+    public void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
+   if(tempList.size() == nums.length){
+      list.add(new ArrayList<>(tempList));
+   } else{
+      for(int i = 0; i < nums.length; i++){ 
+         if(tempList.contains(nums[i])) continue; // element already exists, skip
+         tempList.add(nums[i]);
+         backtrack(list, tempList, nums);
+         tempList.remove(tempList.size() - 1);
+      }
+   }
+} 
+    
+    
+}
+```
+
+**Best Approach**
+I'm sure somewhere can be simplified so it'd be nice if anyone can let me know. The pattern was that:
+
+say n = 4, you have {1, 2, 3, 4}
+
+If you were to list out all the permutations you have
+
+1 + (permutations of 2, 3, 4)
+
+2 + (permutations of 1, 3, 4)
+
+3 + (permutations of 1, 2, 4)
+
+4 + (permutations of 1, 2, 3)
+
+
+We know how to calculate the number of permutations of n numbers... n! So each of those with permutations of 3 numbers means there are 6 possible permutations. Meaning there would be a total of 24 permutations in this particular one. So if you were to look for the (k = 14) 14th permutation, it would be in the
+
+3 + (permutations of 1, 2, 4) subset.
+
+To programmatically get that, you take k = 13 (subtract 1 because of things always starting at 0) and divide that by the 6 we got from the factorial, which would give you the index of the number you want. In the array {1, 2, 3, 4}, k/(n-1)! = 13/(4-1)! = 13/3! = 13/6 = 2. The array {1, 2, 3, 4} has a value of 3 at index 2. So the first number is a 3.
+
+Then the problem repeats with less numbers.
+
+The permutations of {1, 2, 4} would be:
+
+1 + (permutations of 2, 4)
+
+2 + (permutations of 1, 4)
+
+4 + (permutations of 1, 2)
+
+But our k is no longer the 14th, because in the previous step, we've already eliminated the 12 4-number permutations starting with 1 and 2. So you subtract 12 from k.. which gives you 1. Programmatically that would be...
+
+k = k - (index from previous) * (n-1)! = k - 2*(n-1)! = 13 - 2*(3)! = 1
+
+In this second step, permutations of 2 numbers has only 2 possibilities, meaning each of the three permutations listed above a has two possibilities, giving a total of 6. We're looking for the first one, so that would be in the 1 + (permutations of 2, 4) subset.
+
+Meaning: index to get number from is k / (n - 2)! = 1 / (4-2)! = 1 / 2! = 0.. from {1, 2, 4}, index 0 is 1
+
+
+so the numbers we have so far is 3, 1... and then repeating without explanations.
+
+
+{2, 4}
+
+k = k - (index from previous) * (n-2)! = k - 0 * (n - 2)! = 1 - 0 = 1;
+
+third number's index = k / (n - 3)! = 1 / (4-3)! = 1/ 1! = 1... from {2, 4}, index 1 has 4
+
+Third number is 4
+
+
+{2}
+
+k = k - (index from previous) * (n - 3)! = k - 1 * (4 - 3)! = 1 - 1 = 0;
+
+third number's index = k / (n - 4)! = 0 / (4-4)! = 0/ 1 = 0... from {2}, index 0 has 2
+
+Fourth number is 2
+
+
+Giving us 3142. If you manually list out the permutations using DFS method, it would be 3142. Done! It really was all about pattern finding.
+ */
+
+public class permutation_sequence {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt();
+        int k = sc.nextInt();
+
+        System.out.println(getPermutation(n, k));
+    }
+
+    public static String getPermutation(int n, int k) {
+        List<Integer> numbers = new ArrayList<>();
+        StringBuilder s = new StringBuilder();
+        // create an array of factorial lookup
+    
+        int fact[] = new int[n+1];
+        fact[0] = 1;
+        for(int x=1;x<=n;x++)
+            fact[x]=fact[x-1]*x;
+        // factorial[] = {1, 1, 2, 6, 24, ... n!}
+        
+        // create a list of numbers to get indices
+        for(int x = 1 ;x <= n ;x++)
+            numbers.add(x);
+        
+        k--;
+        // numbers = {1, 2, 3, 4}
+        
+        for(int x = 1 ;x <= n ;x++ ){
+            int i=k/fact[n-x];
+            s.append(String.valueOf(numbers.get(i)));
+            numbers.remove(i);
+            k-=i*fact[n-x];
+        }
+        
+        return s.toString();
+    }
+}
+
+

algorithms/Java/README.md

@@ -18,8 +18,10 @@
 - [Dijkstras](graphs/Dijkstras.java)
 - [Prims](graphs/Prims.java)
 
+
 ## Linked Lists
 
+- [Circular Singly Linked List](linked-lists/circular-singly-linkedlist.java)
 - [Circular](linked-lists/circular.java)
 - [Clone Linked List](linked-lists/clone-linkedlist.java)
 - [Doubly](linked-lists/doubly.java)
@@ -36,6 +38,7 @@
 - [Random Node in Linked List](Maths/algorithms_random_node.java)
 - [Square Root using BinarySearch](Maths/square-root.java)
 - [Roman Numerals Conversion](Maths/roman-numerals.java)
+- [Permutation Sequence](Maths/permutation_sequence.java)
 
 ## Queues
 

algorithms/Java/linked-lists/circular-singly-linkedlist.java

@@ -0,0 +1,119 @@
+ class circularll {
+        Node head;
+        Node tail;
+        class Node{
+            int data;
+            Node next;
+
+            Node(int data){
+                this.data=data;
+                this.next=null;
+            }
+        }
+  
+   //add() function add element to the rear of the linkedlist
+        public void add(int data){
+            Node newNode = new Node(data);
+            if(head==null){
+                head=tail=newNode;
+            }
+            else{
+                tail.next=newNode;
+                tail=tail.next;
+            }
+            tail.next=head;
+        }
+  
+   //display() function to show elements of linkedlist
+        public void display(){
+            System.out.printf("\nThe Linkedlist is ");
+            Node temp=head;
+            do{
+                System.out.print(temp.data+" ");
+                temp=temp.next;
+            }while (temp!=head);
+        }
+
+   //search() function searches the element in the linkedlist
+    public void search(int target){
+        int flag=0;
+        Node temp=head;
+        do{
+           if(target==temp.data){
+               System.out.print("\nTarget is found");
+               flag=1;
+               break;
+           }
+            temp=temp.next;
+        }while (temp!=head);
+
+        if (flag==0)
+            System.out.print("\nTarget Not Found");
+    }
+   
+   
+    // addfront() function added a element to the front of the circular singly linkedlist
+        public void addfront(int data){
+            Node newNode = new Node(data);
+            newNode.next=head;
+            head=newNode;
+            tail.next=head;
+        }
+
+   //reverse() function is reversing the circular singly linkedlist
+        public void reverse(){
+            Node previous=tail;
+            Node current=head,nextnode = head;
+
+
+            do{
+                nextnode=current.next;
+                current.next=previous;
+
+                previous=current;
+                current=nextnode;
+
+            }while(current!=head);
+
+            tail=head;
+            head=previous;
+            tail.next=head;
+
+        }
+
+        public static void main(String[] args) {
+            System.out.println("LinkedList");
+            circularll ll = new circularll();
+            ll.add(5);
+            ll.add(8);
+            ll.add(7);
+            ll.add(1);
+            ll.add(2);
+            ll.display();
+            ll.addfront(9);
+            ll.display();
+            ll.search(2);
+            ll.search(4);
+            ll.reverse();
+            ll.display();
+
+        }
+    }
+
+
+
+/*
+
+OUTPUT: 
+
+    LinkedList
+
+The Linkedlist is 5 8 7 1 2 
+The Linkedlist is 9 5 8 7 1 2 
+Target is found
+Target Not Found
+The Linkedlist is 2 1 7 8 5 9 
+
+*/
+
+// Here initial linkedlist was 9 5 8 7 1 2 and after using reverse function the linkedlist become 2 1 7 8 5 9

algorithms/JavaScript/README.md

@@ -3,6 +3,8 @@
 ## Arrays
 
 - [Counting Inversions](src/arrays/counting-inversions.js)
+- [Two Sum](src/arrays/two-sum.js)
+- [Single Occurring Element](src/arrays/single-occurring-element.js)
 
 ## Linked Lists
 
@@ -50,6 +52,11 @@
 - [Max Heap](src/heaps/max-heap.js)
 - [Min Heap](src/heaps/min-heap.js)
 
+## Graphs
+
+- [Breadth First Search](src/graph/breadth-first-search.js)
+- [Depth First Search](src/graph/depth-first-search.js)
+
 ## Trie
 
 - [Trie Implementation](src/trie/trie-implementation.js)

algorithms/JavaScript/src/arrays/single-occurring-element.js

@@ -0,0 +1,18 @@
+// Problem: Given an array of integers,
+// every element appears twice except for one. Find that single one.
+// Space Complexity: O(1)
+// Time Complexity: O(n)
+
+function singleOccurringElement(arr) {
+  let result = 0;
+  for (const el of arr) {
+    result ^= el;
+  }
+  return result;
+}
+
+const arr = [2, 5, 7, 3, 1, 8, 8, 9, 4, 2, 7, 1, 4, 9, 5];
+console.log(singleOccurringElement(arr));
+
+// Input: [2, 5, 7, 3, 1, 8, 8, 9, 4, 2, 7, 1, 4, 9, 5]
+// Output: 3

algorithms/JavaScript/src/arrays/two-sum.js

@@ -0,0 +1,52 @@
+// Documentation credit: Himanshu from two-sum.go
+/*
+    Problem Statement : Given an array of integers nums and an integer target,
+    return indices of the two numbers such that they add up to target.
+    You may assume that each input would have exactly one solution,
+    and you may not use the same element twice.
+
+    Input: An array of integers and a target (int)
+    Output: array of indexes of len(2) with sum of element
+    at that index equal to target or nil
+*/
+
+
+/*
+Using Brute Force : For every element check for another element if
+    it exist in the array such that sum of both the element is equals
+    to the target
+    Time Complexity   : O(n^2)
+*/
+const twoSumBrute = (arr, target) => {
+  for (let i = 0; i < arr.length; i++) {
+    for (let j = 0; j < arr.length; j++) {
+      if (arr[i] + arr[j] === target) {
+        return [i, j];
+      }
+    }
+  }
+  return [];
+};
+
+/*
+    Using Map := While traversing every element add the element as key
+    and its position as its value in a map Check the required value
+    (i.e target - arr[i]) in the map If the map contains the required value
+    then we have two elements with the required sum and return the positions.
+    Time Complexity : O(n)
+*/
+
+const twoSum = (arr, target) => {
+  const map = new Map();
+
+  for (let i = 0; i < arr.length; i++) {
+    if (map.has(arr[i])) return [map.get(arr[i]), i];
+    map.set(target - arr[i], i);
+  }
+  return [];
+};
+
+const nums = [2, 7, 11, 15];
+const target = 9;
+console.log(`Two Sum brute: ${twoSumBrute(nums, target)}`);
+console.log(`Two sum optimized: ${twoSum(nums, target)}`);

algorithms/JavaScript/src/graph/breadth-first-search.js

@@ -0,0 +1,93 @@
+// Program to print BFS traversal from a given source vertex s.
+// breadthFirstSearch(graph, source) traverses vertices reachable from source.
+// for the implementation we need the queue data structure;
+
+// Queue class
+class Queue {
+  // Array is used to implement a Queue
+  constructor() {
+    this.items = [];
+  }
+
+  // enqueue function
+  enqueue(element) {
+    // adding element to the queue
+    this.items.push(element);
+  }
+  // dequeue function
+  // removing element from the queue
+  // returns underflow when called
+  // on empty queue
+  dequeue() {
+    if (this.isEmpty()) {
+      return 'Underflow';
+    }
+    return this.items.shift();
+  }
+  // isEmpty function
+  isEmpty() {
+    // return true if the queue is empty.
+    return this.items.length == 0;
+  }
+}
+
+
+class Graph {
+  // defining vertex array and
+  // adjacent list
+  constructor(noOfVertices) {
+    this.noOfVertices = noOfVertices;
+    this.AdjList = new Map();
+  }
+  // add the requeired vertex in the graph
+  addVertex(v) {
+    this.AdjList.set(v, []);
+  }
+  // addition of edges in the graph as the added edge are bidirectional
+  addEdge(v, w) {
+    this.AdjList.get(v).push(w);
+    this.AdjList.get(w).push(v);
+  }
+}
+const breadthFirstSearch = (g, source) => {
+  const visited = {};
+  const q = new Queue();
+  visited[source] = true;
+  q.enqueue(source);
+
+  while (!q.isEmpty()) {
+    // Dequeue a vertex from queue and print it
+    const getQueueElement = q.dequeue();
+    console.log(getQueueElement);
+    const getList = g.AdjList.get(getQueueElement);
+    // Get all adjacent vertices of the dequeued
+    // vertex s. If a adjacent has not been visited,
+    // then mark it visited and enqueue it
+    for (let i = 0; i < getList.length; i++) {
+      const neigh = getList[i];
+      if (!visited[neigh]) {
+        visited[neigh] = true;
+        q.enqueue(neigh);
+      }
+    }
+  }
+};
+
+const g = new Graph(6);
+// adding vertices
+for (let i = 1; i <= 6; i++) {
+  g.addVertex(i);
+}
+g.addEdge(1, 2);
+g.addEdge(2, 4);
+g.addEdge(3, 1);
+g.addEdge(1, 4);
+g.addEdge(5, 3);
+g.addEdge(6, 3);
+
+breadthFirstSearch(g, 6);
+// when we start bfs for the given graph from point 6 the output is as follow;
+// output 6 3 1 5 2 4
+
+// Time complexity: O(n), where n is the number of vertices in graph
+// Space complexity: O(n), where n is the number of vertices in graph

algorithms/JavaScript/src/graph/depth-first-search.js

@@ -0,0 +1,56 @@
+class Graph {
+  // defining vertex array and
+  // adjacent list
+  constructor(noOfVertices) {
+    this.noOfVertices = noOfVertices;
+    this.AdjList = new Map();
+  }
+  // add the requeired vertex in the graph
+  addVertex(v) {
+    this.AdjList.set(v, []);
+  }
+  // addition of edges in the graph as the added edge are bidirectional
+  addEdge(v, w) {
+    this.AdjList.get(v).push(w);
+    this.AdjList.get(w).push(v);
+  }
+}
+
+// Recursive function which process and explore
+// all the adjacent vertex of the vertex with which it is called
+
+const depthFirstSearch = (g, currVertex, visited) => {
+  visited[currVertex] = true;
+  console.log(currVertex);
+
+  const getNeighbours = g.AdjList.get(currVertex);
+  // Recursive call for the non visited vertex
+  for (let i = 0; i < getNeighbours.length; i++) {
+    const getElement = getNeighbours[i];
+    if (!visited[getElement]) {
+      depthFirstSearch(g, getElement, visited);
+    }
+  }
+};
+
+const g = new Graph(6);
+const visited = {};
+// adding vertices
+for (let i = 1; i <= 6; i++) {
+  g.addVertex(i);
+}
+g.addEdge(1, 2);
+g.addEdge(2, 4);
+g.addEdge(3, 1);
+g.addEdge(1, 4);
+g.addEdge(5, 3);
+g.addEdge(6, 3);
+
+depthFirstSearch(g, 6, visited);
+// for the given graph when we explore it from vertex 6 the output is as follow;
+// output 6 3 1 2 4 5
+
+// TIME COMPLEXITY OF THE PROGRAM
+// O(V+E)
+// where V is number of vertices
+// and E is number of edges

algorithms/JavaScript/src/index.js

@@ -1,5 +1,6 @@
 // Arrays
 require('./arrays/counting-inversions');
+require('./arrays/single-occurring-element');
 
 // Linked Lists
 require('./linked-lists/singly');
@@ -32,3 +33,7 @@ require('./stacks/two-stack');
 
 // Queue
 require('./queues/queue');
+
+//Graphs
+require('./graph/breadth-first-search');
+require('./graph/depth-first-search');

algorithms/Python/README.md

@@ -7,12 +7,14 @@
 - [Missing Number](arrays/missing_number.py)
 - [Remove duplicate items](arrays/remove_duplicates_list.py)
 - [Dutch National Flag Algorithm](arrays/dutch_national_flag_algo.py)
+- [Max Sub Array Sum](arrays/max_sub_array_sum.py)
 
 ## Linked Lists
 - [Doubly](linked_lists/doubly.py)
 - [Singly](linked_lists/singly.py)
 - [Reverse List](linked_lists/reverse-linkedlist.py)
 - [Middle Node](linked_lists/middle-node-linkedlist.py)
+- [Cycle Detection and Removal](linked_lists/cycle-detection-and-removal-linkedlist.py)
 
 
 ## Dictionaries
@@ -64,6 +66,7 @@
 - [Add String](strings/add_string.py)
 - [Rabin Karp algorithm](strings/rabin-karp-algorithm.py)
 - [Find all permutations](strings/find_all_permutations.py)
+- [Roman to Int](strings/roman-to-int.py)
 
 ## Dynamic Programming
 - [Print Fibonacci Series Up To N-th Term](dynamic_programming/fibonacci_series.py)

algorithms/Python/arrays/max_sub_array_sum.py

@@ -0,0 +1,32 @@
+"""
+Algorithm Name: Max Sum of Sub Array
+Time Complexity: O(n)
+Explanation: arr = [3, 2, -4, 9]
+at the start of the algorithm
+assign current sum (max_sum_curr) = max sum(max_sum) = arr[0]
+(for) iterate from arr[1] to arr[n] and do
+  max_sum_curr = arr[i] if arr[i] > arr[i] + max_sum_curr
+  else 
+  max_sum_curr = max_sum_curr + arr[i]
+  max_sum = max_sum if max_sum > max_sum_curr
+  else 
+  max_sum = max_sum_curr
+end
+return max_sum
+"""
+
+def max_sub_arr_sum(arr): 
+    arr_size = len(arr)
+    max_sum = arr[0]
+    max_sum_curr = arr[0]
+     
+    for i in range(1, arr_size):
+        max_sum_curr = max(arr[i], max_sum_curr + arr[i])
+        max_sum = max(max_sum, max_sum_curr)
+         
+    return max_sum
+    
+
+# print("Enter array of numbers (Ex: 1 2 3 4 for [1, 2, 3, 4])")
+arr = [3, 2, -4, 9] # list(map(int, input().split()))
+print("Maximum Sub Array Sum is", max_sub_arr_sum(arr))

algorithms/Python/linked_lists/cycle-detection-and-removal-linkedlist.py

@@ -0,0 +1,73 @@
+# Topic - Linkedlist
+# Language - Python
+# Problem - Detection and Removal of Cycle in Linkedlist.
+# 
+# Idea - run 2 pointers at the start of the linkedlist
+# increment slow pointer by one and fast pointer by two nodes.
+# if slow pointer is equal to fast pointer - then cycle exist
+# to remove the cycle - we need to start slow pointer to start
+# and another fast pointer to same location it is pointing to
+# we will stop increamenting slow pointer when slow equals to
+# fast pointer and break the link from fast.next is None. 
+
+class Node:
+    def __init__(self, val):
+        self.val = val
+        self.next = None
+
+class Linkedlist:
+    def __init__(self):
+        self.head = None
+
+    # pushAtStart is used to create linkedlist
+    def pushAtStart(self, data):
+        node = Node(data)
+        node.next = self.head
+        self.head = node
+    
+
+    def cycleDetectionAndRemoval(self):
+        temp = self.head
+        if temp is None or temp.next is None:
+            return 'No Cycle Detected'
+        slow_ptr = temp
+        fast_ptr = temp
+
+        while (slow_ptr and fast_ptr and fast_ptr.next):
+            # moving slow pointer by one node and fast by two node.
+            slow_ptr = slow_ptr.next
+            fast_ptr = fast_ptr.next.next
+
+            # if slow equals to fast, then we have encountered cycle
+            if slow_ptr == fast_ptr:
+                slow_ptr = temp
+
+                while slow_ptr != fast_ptr:
+                    slow_ptr = slow_ptr.next
+                    fast_ptr = fast_ptr.next
+
+                # removing cycle
+                fast_ptr.next = None
+                return 'Cycle Detected and Removed'
+        return 'No Cycle Detected'
+
+if __name__ == '__main__':
+
+    # creating linkedlist
+    mylist = Linkedlist()
+
+    # adding nodes
+    mylist.pushAtStart(10)
+    mylist.pushAtStart(20)
+    mylist.pushAtStart(30)
+    mylist.pushAtStart(40)
+    mylist.pushAtStart(50)
+
+    # creating cycle
+    mylist.head.next.next.next.next.next = mylist.head.next.next
+
+    # removing cycle
+    print(mylist.cycleDetectionAndRemoval())
+
+    # after removing cycle we don't have cycle
+    print(mylist.cycleDetectionAndRemoval())

algorithms/Python/strings/roman-to-int.py

@@ -0,0 +1,41 @@
+"""
+This program converts a string that represents a valid roman number to its decimal equivalent.
+If the string is not a valid roman number, raises a ValueError exception.
+Time Complexity : O(n)
+Space Complexity : O(1)
+"""
+
+equivalence = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
+
+def is_valid_roman_string(roman_number: str) -> bool:
+    """Returns True if all characters of the given string are valid roman numbers"""
+    return set(roman_number).issubset(equivalence.keys())
+
+
+def conversion(roman_number: str) -> int:
+    """Traverses a given roman number and returns its decimal equivalent"""
+    digits = len(roman_number)
+    result = 0
+
+    for i, char in enumerate(roman_number):
+        if i < digits - 1 and equivalence[char] < equivalence[roman_number[i + 1]]:
+            result -= equivalence[char]
+        else:
+            result += equivalence[char]
+
+    return result
+
+
+def roman_to_int(roman_number: str) -> int | ValueError:
+    """Main function"""
+    if not is_valid_roman_string(roman_number):
+        raise ValueError(f'The string must contain only valid roman numbers: {equivalence.keys()}')
+
+    return conversion(roman_number)
+
+
+if __name__ == '__main__':
+    print(roman_to_int('MCMXCIV'))
+    # 1994
+    print(roman_to_int('abc'))
+    # ValueError: The string must contain only valid roman numbers: dict_keys(['I', 'V', 'X', 'L', 'C', 'D', 'M'])

docs/en/README.md

@@ -1,11 +1,17 @@
 # Algorithms
 
+## Backtracking
+- [N-Queens](./Backtracking/N-Queens.md)
+
 ## Lists
 - [Singly linked list](./Lists/singly-linked-list.md)
 - [Doubly linked list](./Lists/doubly-linked-list.md)
 
-## Sorting
+## Searching
+- [Binary Search](./Searching/Binary-Search.MD)
+- [Linear Search](./Searching/Linear-Search.md)
 
+## Sorting
 - [Bubble Sort](./Sorting/Bubble-Sort.md)
 - [Merge Sort](./Sorting/Merge-Sort.md)
 - [Selection Sort](./Sorting/Selection-Sort.md)
@@ -13,16 +19,13 @@
 - [Heap Sort](./Sorting/Heap-Sort.md)
 - [Quick Sort](./Sorting/Quick-Sort.md)
 - [Cycle Sort](./Sorting/Cycle-Sort.md)
+- [Radix Sort](./Sorting/Radix-Sort.md)
 
 ## Strings
-
 - [Palindrome](./Strings/Palindrome.md)
 
-## Searching
-
-- [Binary Search](./Searching/Binary-Search.MD)
-- [Linear Search](./Searching/Linear-Search.md)
+## Tree
+- [Min Heap](./Tree/min-heap.md)
 
 ## Others
-
 [How to add new algorithm documentation?](./CONTRIBUTING.md)

docs/en/Searching/Binary-Search.MD

@@ -13,7 +13,7 @@
 1. Find the middle element of the array
 2. Check whether the key is equal to middle element if yes then return the index and exit the program
 3. If the 2 step didn't run then test whether the element is less than the middle element if yes then run the step: 1 between the start to middle-1 index 
-4. If the 3 step didn't run then test whether the element is high than the middle element if yes then run the step: 1 between the middle+1 to last index.
+4. If the 3 step didn't run then test whether the element is higher than the middle element if yes then run the step: 1 between the middle+1 to the last index.
 5. Run the loop till the starting index is less than end index
 6. If the loop over and data not found then return -1 that means data doesn't exist
 > **Note:** The array should be sorted in ascending to descending order
@@ -26,7 +26,7 @@ Element to search: **20**
 
 Procedure:
 
-Middle element:**30** and element is less then 30 so search between start to middle -1 index
+Middle element:**30** and element is less than 30 so search between start to middle -1 index
 
 Middle element: **20** and yes the middle element is the key to found so return the index=**1**
 

docs/en/Searching/Linear-Search.md

@@ -11,12 +11,19 @@ Linear search is usually very **simple to implement**.
 **Linear Search( Array A, Value x)**
 
 Step 1: Set i to 1  
+
 Step 2: if i > n then go to step 7  
+
 Step 3: if A[i] = x then go to step 6  
+
 Step 4: Set i to i + 1  
+
 Step 5: Go to Step 2  
+
 Step 6: Print Element x Found at index i and go to step 8  
+
 Step 7: Print element not found  
+
 Step 8: Exit
 
 ## Pseudocode