Sorting Algorithms

Searching Algorithms

Linked Lists

Stacks

Queues

Programs in C — Sorting And Searching Algorithms, Linked Lists

Pravallika Devireddy

28 min readFeb 10, 2021

Sorting Algorithms

Arranging the elements in ascending order or in descending order is called Sorting. Sorting techniques are broadly categorized into two.

Internal Sorting and
External Sorting.

1. Internal Sorting : All the records that are to be sorted are in main memory.

2. External Sorting: Some sorts that cannot be performed in main memory and must be done on disk or tape. This type of sorting is known as External Sorting.

Efficiency: One of the major issues in the sorting algorithms is its efficiency. If we can efficiently sort the records then that adds value to the sorting algorithm. We usually denote the efficiency of sorting algorithm in terms of time complexity. The time complexities are given in terms of big-oh notation.

Commonly there are O(n^2) and O(n log n ) time complexities for various algorithms. Quick sort is the fastest algorithm and bubble sort is the slowest one.

Sorting Method — — — — — — — — — — — — — — Efficiency

Bubble sort/Selection sort/Insertion sort — — — — 0(n^2)

Quick / Merge — — — — — — — — — — — — — — — 0(n log n)

Insertion Sort Algorithm:

Insertion Sort: Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Time Complexity of InsertionSort

Best Case : O(n) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Example:

Let us sort the following numbers using Insertion sort mechanism,
12, 11, 13, 5, 15

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 15

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 15

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 15

i = 4. 15 will be at position 5 as all the elements are smaller than 15.
5, 11, 12, 13,15

Implementation

#include <stdio.h>
#include <conio.h>void insertsort(int a[],int n)
{
   int temp,i,j;
   for(i=0;i<n;i++)
        for(j=0;j<i+1;j++)
            if (a[i] < a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
}void main()
{
 int a[10];
 int i, n;
 //clrscr();
 printf("Enter n");
 scanf("%d",&n);
 printf("Enter array elements\n");
 for (i=0;i<n;i++)
     scanf("%d",&a[i]);  printf("Array before insertion sort\n");
    for (i=0;i<n;i++)
        printf("%d ",a[i]);printf("\n");insertsort(a,n);printf("Array after insertion sort\n");
 for(i=0;i<n;i++)
        printf("%d ",a[i]);printf("\n");
 //getch();
}

Output:

Enter n 5
Enter array elements
11 9 4 21 34
Array before insertion sort
11 9 4 21 34
Array after insertion sort
4 9 11 21 34

Selection Sort Algorithm

Selection Sort: The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the maximum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

Time Complexity of SelectionSort

Best Case : O(n²) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Following example explains the above steps:

arr[] = 64 25 12 22 11// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

Implementation

#include <stdio.h>
#include <conio.h>
void swap (int a[],int i, int j)
{
 int temp;
 temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}
int maxkey(int a[],int low, int high)
{
 int large, largepos, i;
 large = a[low];
 largepos = low;
 for (i=low+1; i<=high;i++)
  if (a[i] > large)
  {
   large  = a[i];
   largepos = i;
  }
 return (largepos);
}
void selectionsort(int a[], int n)
{
     int current, maxpos;
     for (current = n-1;current >=0;current--)
       {
 maxpos = maxkey(a,0, current);
 swap (a,current,maxpos);
       }
} void main()
{
 int a[10];
 int i, n;
 //clrscr();
 printf("Enter n");
 scanf("%d", &n);printf("Enter array elements\n");
 for (i=0;i<n;i++)
  scanf("%d",&a[i]);printf("\n Array before  sorting\n");
 for (i=0;i<n;i++)
        printf("%d\n",a[i]);printf("\n");selectionsort (a,n);printf("Array after  sorting\n");for(i=0;i<n;i++)
        printf("%d ",a[i]);printf("\n");
 //getch();
}

Output

Enter n 5
Enter array elements
21 34 32 11 10Array before  sorting
21
34
32
11
10Array after  sorting
10 11 21 32 34

Quick Sort Algorithm:

Quick Sort: This is the best sort Technique. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Always pick first element as pivot.
Always pick last element as pivot
Pick a random element as pivot.
Pick median as pivot.

Time Complexity :

Best Case : O(nlogn) #Means array is already sorted.

Average Case : O(nlogn) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Algorithm:

First element is considered as pivot in the implemented code below.
Then we should move all the elements which are less than pivot to one side and greater than pivot to other side.
We divide the array into two arrays in such a way that elements > pivot and elements < pivot.

Implementation

#include<stdio.h>void quick_sort(int arr[],int f,int l){
    int pivot,i,j,temp;
    if (f<l){pivot=f;
        i=pivot+1;
        j=l;while(i<j)
        {
            while(arr[i]<arr[pivot] && i<l)
                i+=1;while (arr[j]>arr[pivot])
                j-=1;if(i<j)
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }temp=arr[pivot];
        arr[pivot]=arr[j];
        arr[j]=temp;quick_sort(arr,f,j-1);
        quick_sort(arr,j+1,l);
    }
}void main(){
    int i,j,arr[10],n;printf("Enter Number of Elements ");
    scanf("%d",&n);printf("Enter the numbers into the array");for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    quick_sort(arr,0,n-1);printf("Sorted Elements are");for(i=0;i<n;i++)
    {
        printf("%d\n",arr[i]);
    }
}

Output

Enter Number of Elements 5
Enter the numbers into the array 67 21 34 56 32
Sorted Elements are
21
32
56
34
67

Merge Sort Algorithm:

Merge Sort: One of the best sorting technique. If n value is large, it follows divide and conquer approach.

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.

Time Complexity :

Best Case : O(nlogn) #Means array is already sorted.

Average Case : O(nlogn) #Means array with random numbers.

Worst Case : O(nlogn) #Means array with descending order.

Algorithm:

1. Find the middle point to divide the array into two halves:  
        middle m = (l+r)/2
2. Call mergeSort for first half:   
        Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
        Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
        Call merge(arr, l, m, r)

Example:

Let us take an array of elements 16,75,19,12,33,2,310,45,54

Partition Mechanism :

Merging Mechanism:

Implementation:

//C program for implementation of MergeSort
// Merges two subarrays of array[].
// First subarray is arr1[low..mid]
// Second subarray is arr2[mid+1..high]
#include<stdio.h>
int n;
void mergeSort(int array[],int low,int mid,int high)
{
    int n1,n2,i,j,k;
    int arr1[100],arr2[100];
    n1 = mid - low + 1;
    n2 = high - mid ;// create temp arrays
    //arr1 = [0] * (n1) ;
    //arr2 = [0] * (n2) ;// Copy data to temp arrays arr1[] and arr2[]
    for(i=0;i<n-1;i++)
        arr1[i] = array[low + i];for (j=0;j<n2;j++)
        arr2[j] = array[mid + 1 + j];// Merge the temp arrays back into arr[l..r]
    i = 0;     // Initial index of first subarray
    j = 0;    // Initial index of second subarray
    k = low;   // Initial index of merged subarraywhile (i < n1 && j < n2 ) {
        if (arr1[i] <= arr2[j]){
            array[k] = arr1[i] ;
            i += 1;
        }
        else
        {
            array[k] = arr2[j] ;
            j += 1;
        }
        k += 1;
    }// Copy the remaining elements of arr1[], if there are any
    while (i < n1){
        array[k] = arr1[i] ;
        i += 1;
        k += 1;
    }
    // Copy the remaining elements of arr2[], if there are any
    while (j < n2)
    {
        array[k] = arr2[j] ;
        j += 1;
        k += 1;
    }
}
void partition(int array[],int low,int high){int mid;if (low < high){// Same as (low+high)//2, but avoids overflow for large low and high
       mid = (low+(high-1))/2 ;// Sort first and second halves
        partition(array, low, mid);
        partition(array, mid+1, high);
        mergeSort(array, low, mid, high);
    }
}
void main(){int array[10],i;
    printf("Enter the size of the array");
    scanf("%d",&n);printf("Enter Elements into array");
    for(i=0;i<n;i++)
        scanf("%d",&array[i]);partition(array,0,n-1);printf("\n\nSorted array is");
    for(i=0;i<n;i++)
        printf("%d\n",array[i]);}

Output

Enter the size of the array 5
Enter Elements into array 2 34 52 1 21Sorted array is
1
2
21
34
52

Bubble Sort:

A well known algorithm called Bubble sort, is easy to understand. Probably this is the least efficient. The basic idea underlying the bubble sort is to pass through the array left to right several times. Each pass consists of comparing each element in the array with its successor and interchanging the two elements if they are not in proper order. At the end of each pass we can observe that the largest element of the list is moved to its final position.

Explanation:

Time Complexity :

Best Case : O(n²) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Implementation:

#include<stdio.h>
#include<conio.h>
bubblesort(a,n)
int a[],n;
{
  int i,j,temp;for(i=0;i<n;i++)
  {
    for(j=0;j<n-1-i;j++)
     if(a[j]>a[j+1])
     {
       temp=a[j];
       a[j]=a[j+1];
       a[j+1]=temp;
     }
   }
}void main()
{
  int i,t,j,n,a[20];
  //clrscr();
  printf("enter size of array");
  scanf("%d",&n);
  printf("enter array elements:");
  for(i=0;i<n;i++)
  scanf("%d",&a[i]);bubblesort(a,n);printf("the sorted arrayis:");
   for(i=0;i<n;i++)
   printf("%d ",a[i]);
   //getch();
 }

Output

enter size of array 5
enter array elements:
12
2
11
32
1
the sorted arrayis:1 2 11 12 32

Note: To run the programs in Turboc please un comment the clrscr() function and getch() function to clear the screen and get the output in the console.

Implementation of all the Operations of a Linked List

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*curr,*temp1;void create(int data)
{temp = malloc(sizeof(struct node));
    // Initialize data into temp data field
    temp->data = data;// Put NULL pointer reference into temp link
    temp->next = NULL;if(head == NULL)
        head = curr = temp;else
    {
        curr->next = temp;
         curr = temp;
    }}
void insert(int ele,int p)
{
    int i;
    temp = malloc(sizeof(struct node));
    temp->data = ele;    if(p==1)
    {
        temp->next=head;
        head=temp;
    }
    if(p==length()+1)
    {
        curr->next = temp;
        temp->next=NULL;
        curr=temp;
    }
    else
    {
        temp1=head;
        for(i=1;i<=p-2;i++)
            temp1=temp1->next;temp->next=temp1->next;
        temp1->next=temp;
    }
}void search(int ele)
{
    int flag=0;
    curr = head; // Initialize current
    while (curr != NULL)
    {
          if (curr->data == ele)
          {
              flag=1;
              break;
          }
          curr = curr->next;
    }
    if(flag == 1)
        printf("True\n");
    else
        printf("False\n");
}void del(int p)
{
    int i;
    if(p == 1)
    {
        temp = head;
        head=head->next;
        free(temp);
    }
    else if(p==length())
    {
       for(temp=head;temp->next!=curr;temp=temp->next)
            temp->next=NULL;
       free(curr);
       curr=temp;
    }
    else
    {
        temp=head;
        for(i=1;i<=(p-2);i++)
            temp=temp->next;
        temp1=temp->next;
        temp->next=temp1->next;
        free(temp1);
    }
}
int length()
{
    int i=0;
    for(temp=head;temp!=NULL;temp=temp->next,i++);
    return i;
}void display()
{for(temp=head;temp!=NULL;temp=temp->next)
        printf("%d->",temp->data);printf("NULL\n");
}void main()
{
    int ch,ele,p;
    printf("1.Create \n2.Delete Element at a specified position \n3.Insert element at a Specific position\n4.Display\n5.Length of the List\n6.Search\n");
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            create(ele);
            break;
        case 2:
            printf("Enter the position to delete");
            scanf("%d",&p);
            del(p);
            break;
        case 3:
            printf("Enter element and position\n");
            scanf("%d%d",&ele,&p);
            insert(ele,p);
            break;
        case 4:
            display();
            break;
        case 5:
            printf("Length of the List %d",length());
            break;
        case 6:
            printf("Enter Search Element");
            scanf("%d",&ele);
            search(ele);
            break;
        default:
            exit(0);
        }
    }
}

Output:

1.Create
2.Delete Element at a specified position
3.Insert element at a Specific position
4.Display
5.Length of the List
6.Search
Enter Choice
1
Enter Element to be created
12
Enter Choice
1
Enter Element to be created
13
Enter Choice
3
Enter element and position
15 1
Enter Choice
4
15->12->13->NULL
Enter Choice
2
Enter the position to delete 3
Enter Choice
4
15->12->NULL
Enter Choice
6
Enter Search Element12
True
Enter Choice
7

Reverse a linked list

Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.

Program to reverse a Linked List:

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*curr,*temp1;void create(int data)
{    temp = malloc(sizeof(struct node));
    // Initialize data into temp data field
    temp->data = data;    // Put NULL pointer reference into temp link
    temp->next = NULL;if(head == NULL)
        head = curr = temp;else
    {
        curr->next = temp;
         curr = temp;
    }}
void del(int p)
{
    int i;
    if(p == 1)
    {
        temp = head;
        head=head->next;
        free(temp);
    }
    else if(p==length())
    {
       for(temp=head;temp->next!=curr;temp=temp->next)
            temp->next=NULL;
       free(curr);
       curr=temp;
    }
    else
    {
        temp=head;
        for(i=1;i<=(p-2);i++)
            temp=temp->next;
        temp1=temp->next;
        temp->next=temp1->next;
        free(temp1);
    }
}
void rev()
{struct node *n,*p;
    curr=temp=head;
    n=NULL;
    p=NULL;
    while(curr != NULL)
    {
        p=n;
        n=curr->next;
        curr->next=p;
        p=curr;
        curr=n;}
    head=p;
}int length()
{
    int i=0;
    for(temp=head;temp!=NULL;temp=temp->next,i++);
    return i;
}
void display()
{     for(temp=head;temp!=NULL;temp=temp->next)
        printf("%d->",temp->data);
}void main()
{
    int ch,ele,p;
    printf("1.Create \n2.Delete \n3..Display\n 4.Reverse The List\n");
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            create(ele);
            break;
        case 2:
            printf("Enter the position to delete\n");
            scanf("%d",&p);
            del(p);
            break;
        case 3:
            display();
            printf("NULL\n");
            break;
        case 4:
            rev();
            break;
        default:
            exit(0);
        }
    }
}

Output:

1.Create
2.Delete
3.Display
4.Reverse The List
Enter Choice
1
Enter Element to be created
12
Enter Choice
1
Enter Element to be created
13
Enter Choice
1
Enter Element to be created
14
Enter Choice
1
Enter Element to be created
15
Enter Choice
2
Enter the position to delete1
Enter Choice
3
13->14->15->NULL
Enter Choice
4
Enter Choice
3
15->14->13->NULL
Enter Choice
5

Implementation of Sparse Matrix using LinkedLists:

#include<stdio.h>
struct node
{
    int row;
    int column;
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*curr=NULL;
void main()
{
    int a[10][10],m,n,i,j;
    printf("Enter Size of the matrix\n");
    scanf("%d %d",&m,&n);
    printf("Enter the values in the sparse matrix");
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
         scanf("%d",&a[i][j]);    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
        {
            if(a[i][j]!=0)
            {                temp=malloc(sizeof(struct node));
                temp->row=i;
                temp->column=j;
                temp->data=a[i][j];
                temp->next=NULL;
                if(head==NULL)
                    head=curr=temp;
                else
                {
                    curr->next=temp;
                    curr=temp;
                }
            }
        }        printf("Representation in Linked List\n");
         for(temp=head;temp!=NULL;temp=temp->next)
            printf("[%d %d]:%d\n",temp->row,temp->column,temp->data);}

Output:

Enter Size of the matrix
5
6
Enter the values in the sparse matrix
0 0 0 0 9 0
0 8 0 0 0 0
4 0 0 2 0 0
0 0 0 0 0 5
0 0 2 0 0 0Representation in Linked List
[0 4]:9
[1 1]:8
[2 0]:4
[2 3]:2
[3 5]:5
[4 2]:2

Representation of Polynomial using Linked List:

A polynomial object is a homogeneous ordered list of pairs <exponent,coefficient>, where each coefficient is unique. Operations include returning the degree, extracting the coefficient for a given exponent, addition, multiplication, evaluation for a given input.

#include<stdio.h>
struct node
{
    int coeff;
    int exp;
    struct node *next;
};
struct node *head=NULL,*temp,*curr=NULL,*temp1;
void main()
{
    int i,n;
    printf("Enter no. of terms in the polynomial equation\n ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        temp=malloc(sizeof(struct node));
        scanf("%d %d",&temp->coeff,&temp->exp);
        temp->next=NULL;
        if(head==NULL)
            head=curr=temp;
        else
        {
            curr->next=temp;
            curr=temp;
        }
    }
    printf("The polynomial equation is");
    for(temp=head;temp!=NULL;temp=temp->next)
        printf("%dx^%d+",temp->coeff,temp->exp);
    printf("0");}

Output:

Enter no. of terms in the polynomial equation
3
5 2
4 1
3 0
The polynomial equation is5x^2+4x^1+3x^0+0

Adding two polynomials using Linked List

Given two polynomial numbers represented by a linked list. Write a function that add these lists means add the coefficients who have same variable powers.

For Example,

Input:
     1st number = 5x2 + 4x1 + 2x0
     2nd number = -5x1 - 5x0
Output:
        5x2-1x1-3x0
Input:
     1st number = 5x3 + 4x2 + 2x0
     2nd number = 5x^1 - 5x^0
Output:
        5x3 + 4x2 + 5x1 - 3x0

Implementation For Addition of two polynomials using LinkedLists:

// C++ program for addition of two polynomials using Linked Lists#include <bits/stdc++.h>
using namespace std;// Node structure containing power and coefficient of variablestruct node {
      int coeff;
      int pow;
      struct node *next;
};
struct node **temp;// Function to create new node
void create(int x, int y, struct node** temp)
{
    struct node *r, *z;
    z = *temp;
    if (z == NULL) {
       r = (struct node*)malloc(sizeof(struct node));
       r->coeff = x;
       r->pow = y;
       *temp = r;
       r->next = (struct node*)malloc(sizeof(struct node)); 
       r = r->next;
       r->next = NULL;
    }     else {
        r->coeff = x;
        r->pow = y; 
        r->next = (struct node*)malloc(sizeof(struct node));
        r = r->next;
        r->next = NULL;
      }
}// Function Adding two polynomial numbers
void polyadd(struct node* poly1, struct node* poly2,struct node* poly)
{
     while (poly1->next && poly2->next) { 
            // If power of 1st polynomial is greater then 2nd, then store 1st as it is and move its pointer
          if (poly1->pow > poly2->pow) {
                poly->pow = poly1->pow;
                poly->coeff = poly1->coeff;
                poly1 = poly1->next;
           }
        // If power of 2nd polynomial is greater then 1st, then store 2nd as it is and move its pointer
           else if (poly1->pow < poly2->pow) {
                poly->pow = poly2->pow;
                poly->coeff = poly2->coeff;
                poly2 = poly2->next;
           }
       // If power of both polynomial numbers is same then add their coefficients
           else {
                poly->pow = poly1->pow;
                poly->coeff = poly1->coeff + poly2->coeff; 
                poly1 = poly1->next;
                poly2 = poly2->next;
           }
      // Dynamically create new node
      poly->next= (struct node*)malloc(sizeof(struct node));
      poly = poly->next;
      poly->next = NULL;
   }   while (poly1->next || poly2->next) {
          if (poly1->next) {
              poly->pow = poly1->pow;
              poly->coeff = poly1->coeff; 
              poly1 = poly1->next;
          }          if (poly2->next) {
              poly->pow = poly2->pow;
              poly->coeff = poly2->coeff;
              poly2 = poly2->next;
          }          poly->next = (struct node*)malloc(sizeof(struct node));
          poly = poly->next;
          poly->next = NULL;
      }
   }
// Display Linked list
void show(struct node* node)
{
     while (node->next != NULL) {         printf("%dx^%d", node->coeff, node->pow);
         node = node->next; 
         if (node->coeff >= 0) {
               if (node->next != NULL)
                        printf("+");
         }
     }
}// Driver code
int main()
{
   struct node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
   // Create first list of 5x^2 + 4x^1 + 2x^0
   create(5, 2, &poly1);
   create(4, 1, &poly1);
   create(2, 0, &poly1);
   // Create second list of -5x^1 - 5x^0
   create(-5, 1, &poly2);
   create(-5, 0, &poly2);
   printf("1st Number: ");
   show(poly1);
   printf("\n2nd Number: ");
   show(poly2);
   poly = (struct node*)malloc(sizeof(struct node));
   // Function add two polynomial numbers
   polyadd(poly1, poly2, poly);
  // Display resultant List
   printf("\nAdded polynomial: ");
   show(poly);
   return 0;
}

Output:

1st Number: 5x^2+4x^1+2x^0
2nd Number: -5x^1-5x^0
Added polynomial: 5x^2-1x^1-3x^0

Multiply two polynomials

Given two polynomials represented by two arrays, write a function that multiplies given two polynomials.

For example,

Input:  A[] = {5, 0, 10, 6} 
        B[] = {1, 2, 4} 
Output: prod[] = {5, 10, 30, 26, 52, 24}The first input array represents "5 + 0x^1 + 10x^2 + 6x^3"
The second array represents "1 + 2x^1 + 4x^2" 
And Output is "5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5"

A simple solution is to one by one consider every term of first polynomial and multiply it with every term of second polynomial. Following is algorithm of this simple method.

multiply(A[0..m-1], B[0..n01])
1) Create a product array prod[] of size m+n-1.
2) Initialize all entries in prod[] as 0.
3) Traverse array A[] and do following for every element A[i]
...(3.a) Traverse array B[] and do following for every element B[j]
          prod[i+j] = prod[i+j] + A[i] * B[j]
4) Return prod[].

Implementation:

#include <bits/stdc++.h>
using namespace std;
// A[] represents coefficients of first polynomial
// B[] represents coefficients of second polynomial
// m and n are sizes of A[] and B[] respectively
int *multiply(int A[], int B[], int m, int n)
{
   int *prod = new int[m+n-1];// Initialize the porduct polynomial
   for (int i = 0; i<m+n-1; i++)
     prod[i] = 0;// Multiply two polynomials term by term// Take ever term of first polynomial
   for (int i=0; i<m; i++)
   {
     // Multiply the current term of first polynomial
     // with every term of second polynomial.
     for (int j=0; j<n; j++)
         prod[i+j] += A[i]*B[j];
   }return prod;
}// A utility function to print a polynomial
void printPoly(int poly[], int n)
{
    for (int i=0; i<n; i++)
    {
       cout << poly[i];
       if (i != 0)
        cout << "x^" << i ;
       if (i != n-1)
       cout << " + ";
    }
}// Driver program to test above functions
int main()
{
    // The following array represents polynomial 5 + 10x^2 + 6x^3
    int A[] = {5, 0, 10, 6};// The following array represents polynomial 1 + 2x + 4x^2
    int B[] = {1, 2, 4};
    int m = sizeof(A)/sizeof(A[0]);
    int n = sizeof(B)/sizeof(B[0]);cout << "First polynomial is n";
    printPoly(A, m);
    cout << "nSecond polynomial is n";
    printPoly(B, n);int *prod = multiply(A, B, m, n);cout << "nProduct polynomial is n";
    printPoly(prod, m+n-1);return 0;
}

Output:

First polynomial is n5 + 0x^1 + 10x^2 + 6x^3n
Second polynomial is n1 + 2x^1 + 4x^2n
Product polynomial is n5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5

Stack — Using Linked List

Implementing a stack using single linked list

All the single linked list operations perform based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list.

Get Pravallika Devireddy’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

A stack can be easily implemented through the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. first node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.

The main advantage of using linked list over an arrays is that it is possible to implements a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.

Stack Operations:

push() : Insert the element into linked list nothing but which is the top node of Stack.
pop() : Return top element from the Stack and move the top pointer to the second node of linked list or Stack.
peek(): Return the top element.
display(): Print all element of Stack.

Implementation of stack using Linked List:

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*top,*temp1;void push(int data)
{temp = malloc(sizeof(struct node));
    if (!temp)
    {
        printf("\nHeap Overflow");
        exit(1);
    }// Initialize data into temp data field
    temp->data = data;// Put top pointer reference into temp link
    temp->next = top;// Make temp as top of Stack
    top = temp;
}
void pop()
{
    if(top == NULL)
        printf("Linked list is empty");
    else
    {
       // Top assign into temp
        temp = top;
        // Assign second node to top
        top = top->next;
        // Destroy connection between first and second
        temp->next = NULL;
        // Release memory of top node
        free(temp);
    }
}
void display()
{
    // Check for stack underflow
    if (top == NULL)
    {
        printf("\nStack Underflow");
        exit(1);
    }
    else
    {
        temp = top;
        while (temp != NULL)
        {// Print node data
            printf("%d->",temp->data );// Assign temp link to temp
            temp = temp->next;
        }
    }
}
void main()
{
    int ch,ele,p;
    printf("1.push 2.pop 3.display 4.exit\n");
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            push(ele);
            break;
        case 2:
            pop();
            break;
        case 3:
            display();
            printf("NULL");
            break;
        default:
            exit(0);
        }
    }
}

Output:

1.push 2.pop 3.display 4.exit
Enter Choice1Enter Element to be created12
Enter Choice1Enter Element to be created13
Enter Choice1Enter Element to be created14
Enter Choice2
Enter Choice3
13->12->NULL
Enter Choice2
Enter Choice1Enter Element to be created15
Enter Choice3
15->12->NULL
Enter Choice

Queue — Using Linked List

In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.

enQueue() This operation adds a new node after rear and moves rear to the next node.

deQueue() This operation removes the front node and moves front to the next node.

Implementation:

#include <stdio.h>
#include <stdlib.h>// A linked list (LL) node to store a queue entry
struct QNode {
    int key;
    struct QNode* next;
};// The queue, front stores the front node of LL and rear stores the
// last node of LL
struct Queue {
    struct QNode *front, *rear;
};// A utility function to create a new linked list node.
struct QNode* newNode(int k)
{
    struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->next = NULL;
    return temp;
}// A utility function to create an empty queue
struct Queue* createQueue()
{
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}// The function to add a key k to q
void enQueue(struct Queue* q, int k)
{
    // Create a new LL node
    struct QNode* temp = newNode(k);// If queue is empty, then new node is front and rear both
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }// Add the new node at the end of queue and change rear
    q->rear->next = temp;
    q->rear = temp;
}// Function to remove a key from given queue q
void deQueue(struct Queue* q)
{
    // If queue is empty, return NULL.
    if (q->front == NULL)
        return;// Store previous front and move front one node ahead
    struct QNode* temp = q->front;q->front = q->front->next;// If front becomes NULL, then change rear also as NULL
    if (q->front == NULL)
        q->rear = NULL;free(temp);
}// Driver Program to test anove functions
int main()
{
    struct Queue* q = createQueue();
    enQueue(q, 10);
    enQueue(q, 20);
    deQueue(q);
    deQueue(q);
    enQueue(q, 30);
    enQueue(q, 40);
    enQueue(q, 50);
    deQueue(q);
    printf("Queue Front : %d \n", q->front->key);
    printf("Queue Rear : %d", q->rear->key);
    return 0;
}

Output:

Queue Front : 40
Queue Rear : 50

Linear search (Sequential search)

If we want to search an element , whether it is present in the array or not, first A[1] is compared with given element. Match occurs. So the number of comparisons is only one. It is observed that search takes minimum number of comparisons, so it come under best case.

Time complexity is O(1).

Average Case: If we want to search an element 8, whether it is present in the array or not . first A[1] is compared with 8, no match occurs. Compare A[3] and A[4] with 8, no match occurs. Up to now 4 comparisons take place. Now compare A[5] and 8 so match occurs. The number of comparisons are 5. It is observed that search takes average number of comparisons. So it comes under average case. If there are n elements, then we require n/2 comparisons. Time complexity is O(n/2) which is O(n). we can neglect constant.

Worst Case : If we want to search an element 13, whether it is present in the array or not. First A[1] is compared with 13. No match occurs. Continue this process until element is found or the list exhausted. The element is found at 9th comparison. So number of comparisons are 9. It is observed that search takes maximum number of comparisons. So it comes under worst case.

Time complexity is O(n)

Note : If the element is not found in the list then we have to search entire list, so it comes under worst case.

Ex 2) Binary Search:

Best case time complexity O(1)

Average case time complexity O(log n)

Worst case time complexity O(log n)

Assume that the number of elements is considered as 2m as every time the list is divided into two halfs.

n = 2m

log (n) = log(2m )

log (n) = m log(2 )

m = log(n)/log(2)

m = log(2n) i.e. log n base 2

m = log (n)

Linear Search

#include<stdio.h>
#include<conio.h>linearsearch(a,n,x)
int a[],n,x;
{
   int found,i,pos;
   found=0;     /------------*1-found   0-not found*/
   for (i=0;i<n;i++)
       if (a[i] == x){
            found=1;
            pos=i;
            break;
   } 
   if (found)
       printf("%d found at position %d\n",x,pos);
   else
       printf("%d not found\n",x);
}
void main(){
    int a[10],i,n,target;
   //clrscr();
   printf("enter size" );
   scanf("%d",&n);
   for (i=0;i<n;i++){
        printf("enter array element ");
        scanf("%d",&a[i]);
   }
   printf("enter the target element ");
   scanf("%d",&target);
   linearsearch(a,n,target);
   getch();
}

Output

Enter size 5
Enter Array element 12 13 14 15 11
Enter Target 12
12 found at position 0

Binary Search

#include<stdio.h>#include<conio.h>binarysearch(a,n,tar)int a[],n,tar;{int low,high,mid,found;found=0;     /*1-found   0-not found*/low=0;high=n-1;while((low<=high)&&(!found)){mid = (low + high)/2;if (a[mid] == tar){found=1;break;}elseif (tar > a[mid])low=mid+1;elsehigh=mid-1;}if (found)printf("%d found at position %d\n",tar,mid);elseprintf("%d not found\n",tar);}void main(){int a[10],i,n,target;clrscr();printf("enter size" );scanf("%d",&n);printf("enter array elements in ascending order\n");for (i=0;i<n;i++)scanf("%d",&a[i]);printf("enter the target element ");scanf("%d",&target);binarysearch(a,n,target);getch();}

Output

Enter size 5
Enter Array element 12 13 14 15 11
Enter Target 12
12 found at position 0

RADIX SORT

Radix sort is one of the linear sorting algorithms for integers. It functions by sorting the input numbers on each digit, for each of the digits in the numbers. However, the process adopted by this sort method is somewhat counterintuitive, in the sense that the numbers are sorted on the least-significant digit first, followed by the second-least significant digit and so on till the most significant digit.

To appreciate Radix Sort, consider the following analogy: Suppose that we wish to sort a deck of 52 playing cards (the different suits can be given suitable values, for example 1 for Diamonds, 2 for Clubs, 3 for Hearts and 4 for Spades). The ‘natural’ thing to do would be to first sort the cards according to suits, then sort each of the four separate piles, and finally combine the four in order. This approach, however, has an inherent disadvantage. When each of the piles is being sorted, the other piles have to be kept aside and kept track of. If, instead, we follow the ‘counterintuitive’ approach of first sorting the cards by value, this problem is eliminated. After the first step, the four separate piles are combined in order and then sorted by suit. If a stable sorting algorithm (i.e. one which resolves a tie by keeping the number obtained first in the input as the first in the output) it can be easily seen that correct final results are obtained.

The sorting of numbers proceeds by sorting the least significant to most significant digit. For sorting each of these digit groups, a stable sorting algorithm is needed. Also, the elements in this group to be sorted are in the fixed range of 0 to 9. Both of these characteristics point towards the use of Counting Sort as the sorting algorithm of choice for sorting on each digit.

The time complexity of the algorithm is as follows: Suppose that the n input numbers have maximum k digits. Then the Counting Sort procedure is called a total of k times. Counting Sort is a linear, or O(n) algorithm. So the entire Radix Sort procedure takes O(kn) time. If the numbers are of finite size, the algorithm runs in O(n) asymptotic time.

Efficiency

Radix sort’s efficiency is O(k·n) for n keys which have k or fewer digits. Note that this is not necessarily better than O(n·log(n)), as k may not be independent of n. As an example, consider the ordering of a list of n different integers. Lets assume integers are coded in base B. Then there are B different possible digits and k must be at least as big as logB(n). As there are B different digits, there are B buckets needed, and each pass needs in average n·log2(B) comparisons to distribute the integers into the buckets. So we have:

· k is bigger or equal to logB(n)

· Each pass requires n·log2(B) comparisons (on average)

So, if T is the average time needed by radix sort, we have:

T ≥ logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·log2(n)

As with comparison sorts, we have T ≥ n·log2(n) for radix sort. So the complexity is Ω(n·log2(n)) = Ω(n·log n).

Definition

Each key is first figuratively dropped into one level of buckets corresponding to the value of the rightmost digit. Each bucket preserves the original order of the keys as the keys are dropped into. There is a one-to-one correspondence between the number of buckets and the number of values that can be represented by a digit. Then, the process repeats with the next neighbouring digit until there are no more digits to process. In other words:

Take the least significant digit (or group of bits, both being examples of radices) of each key.
Group the keys based on that digit, but otherwise keep the original order of keys. (This is what makes the LSD radix sort a stable sort).
Repeat the grouping process with each more significant digit.

The sort in step 2 is usually done using bucket sort or counting sort, which are efficient in this case since there are usually only a small number of digits.

An example: Original, unsorted list:

170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit (1s place) gives:

170, 90, 802, 2, 24, 45, 75, 66

Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75. Sorting by next digit (10s place) gives:

802, 2, 24, 45, 66, 170, 75, 90

Sorting by most significant digit (100s place) gives:

2, 24, 45, 66, 75, 90, 170, 802

It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.

Some LSD radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array. Consider the previous list of keys viewed in a different way:

170, 045, 075,090, 002, 024, 802, 066

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:

2 (bucket size for digits of 0: 170, 090)

2 (bucket size for digits of 2: 002, 802)

1 (bucket size for digits of 4: 024)

2 (bucket size for digits of 5: 045, 075)

1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:

2 (bucket size for digits of 0: 002, 802)

1 (bucket size for digits of 2: 024)

1 (bucket size for digits of 4: 045)

1 (bucket size for digits of 6: 066)

2 (bucket size for digits of 7: 170, 075)

1 (bucket size for digits of 9: 090)

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:

6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)

1 (bucket size for digits of 1: 170)

1 (bucket size for digits of 8: 802)

At least one LSD radix sort implementation now counts the number of times that each digit occurs in each column for all columns in a single counting pass. Other LSD radix sort implementations allocate space for buckets dynamically as the space is needed.

/*------------------ Radix Sorting Technique */
#include <stdio.h>
#include <conio.h>
void radixsort(int a[],int n)
{
   int i,b[20],m=0,exp=1;
   int bucket[10];for(i=0;i<n;i++)
      if(a[i]>m)
      m=a[i];while(m/exp>0)
   {
      for(i=0;i<10;i++)
      bucket[i]=0;for(i=0;i<n;i++)
     bucket[a[i]/exp%10]++;for(i=1;i<10;i++)
     bucket[i]+=bucket[i-1];for(i=n-1;i>=0;i--)
     b[--bucket[a[i]/exp%10]]=a[i];for(i=0;i<n;i++)
      a[i]=b[i];exp*=10;
   }
}
void main()
{
   int a[20],i,n;clrscr();
   printf("enter n ");
   scanf("%d",&n);printf("Enter Array Elements \n");
   for (i=0;i<n;i++)
      scanf("%d",&a[i]);radixsort(a,n);printf("The sorted array\n");
   for(i=0;i<n;i++)
      printf("%d\n",a[i]);getch();
}

Output

unsorted list:523 153 088 554 235sorting for Radix 0 (least significant digit)523 153 554 235 088sorting for Radix 1 (2nd. significant digit)523 235 153 554 088sorting for Radix 2 (most. significant digit)088 153 235 523 554

Binary Heap :

A heap is a binary tree that is completely filled with the possible exception of the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree.

It is easy to show that a complete binary tree of height h has between 2h and 2h+1–1 nodes.

An important observation is that because a complete binary tree is so regular, if can be represented in an array and no pointers are necessary.

For any element in array position i, the left child is in position 2i + 1, the right child is in the cell after the left child 2i+2 and parent is in position i/2 –1.

Heap Sort :

Heap Sort is simply an implementation of the general selection Sort using the input array x as a heap representing a descending priority Queue. The preprocessing phase creates a heap of size n, using the sift-up operation, and the selection phase redistributes the elements of the heap in order as it deletes elements from the priority Queue using the sift-down operation.

Phase1 — — Creating a heap.

Phase2 — — Illustrates the adjustment of the heap as x[0] is

Repeatedly selected and placed into its proper position in the array and the heap is readjusted, Until all the heap elements are processed. Note that after an element has been deleted from the heap, it remains in the array, it is merely ignored in subsequent processing.

Running time of heap sort O(n log n)

Heap Sort: 25 57 48 37 12 92 86 33

/*********************** Heap Sort Technique*/
 #include<stdio.h>
 #include<conio.h>display(a,n)
 int a[],n;
 {
  int i;
  for(i=0;i<n;i++)
  printf("%d ",a[i]);
  printf("\n");
 }
 /********************** Function to create heap */
 createheap(x,n)
 int x[],n;
 {
    int i,ele,s,f;
    for (i=1;i<n;i++)
    {
       ele = x[i];
       s = i;
       f = (s-1) / 2;
       while (s>0 && x[f]<ele)
        {
   x[s] = x[f];
   s = f;
   f = (s-1) / 2;
        }
        x[s] = ele;
   }}swap(x,i,j)
   int x[],i,j;
   {
     int temp;
     temp=x[i];
     x[i]=x[j];
     x[j]=temp;
   }
    /* Repeatedly remove x[0] and insert it in proper position
       and readjust the remaining heap */
   heapsort(x,n)
   int x[],n;
   {
     int i;
     for (i=n-1;i>0;i--)
      {
  display(x,n);
  swap(x,0,i);
  createheap(x,i);
      }
   }
 void main()
    {
       static int a[20] = { 25,57,48,37,12,92,86,33 };
       int n,i;
       clrscr();
       createheap(a,8);
       heapsort(a,8); /* function call */
       printf("the sorted array is:");
       display(a,8);
       getch();
    }/***************************************************
          Heap Sort another vertion
****************************************************/
#include <stdio.h>
#include <conio.h>
void makeheap(a,n)
int a[50],n;
{
  int i,j,val,father;
  for (i=1;i<n;i++)
    {
       val=a[i];
       j=i;
       father=(j-1)/2;
       while (j>0 && a[father]<val)
       {
  a[j]=a[father];
  j=father;
  father=(j-1)/2;
       }
       a[j]=val;
    }
}void display(a,n)
int a[50],n;
{
   int i;
   for(i=0;i<n;i++)
      printf("%d\n",a[i]);
}void heapsort(a,n)
int a[50],n;
{
   int i,k,temp,j;
   for(i=n-1;i>0;i--)
   {
      temp=a[i];
      a[i]=a[0];
      k=0;
      if ( i==1)
  j=-1;
      else
  j=1;
      if (i>2 && a[2]>a[1])
      j=2;
      while(j>0 && temp<a[j])
      {
  a[k]=a[j];
  k=j;
  j=2*k+1;
  if (j+1<= i-1 && a[j]<a[j+1])
     j++;
  if (j>i-1)
     j=-1;
      }
      a[k]=temp;
   }
}void main()
{
   int a[50], i,n;
   clrscr();
   printf("enter n ");
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
     printf("enter array element ");
     scanf("%d",&a[i]);
   }
   printf("The Un sorted array is\n");
   display(a,n);makeheap(a,n);
   printf("The heapfied array is\n");
   display(a,n);heapsort(a,n);
   printf("The sorted array is\n");
   display(a,n);
   getch();
}

About Data Structures

Programs in C — Sorting And Searching Algorithms, Linked Lists

Sorting Algorithms

Insertion Sort Algorithm:

Selection Sort Algorithm

Quick Sort Algorithm:

Merge Sort Algorithm:

Bubble Sort:

Implementation of all the Operations of a Linked List

Reverse a linked list

Stack — Using Linked List

Implementing a stack using single linked list

Get Pravallika Devireddy’s stories in your inbox

Queue — Using Linked List

Definition

An example: Original, unsorted list:

Output

Published in About Data Structures

Written by Pravallika Devireddy

No responses yet

More from Pravallika Devireddy and About Data Structures

Graphs — Introduction, DFS, BFS, Prims Algorithm, Kruskal’s Algorithm and their Implementations

A graph G consists of a set of V or vertices (nodes) and a set if edges (arcs). Vertices are nothing but the nodes in the graph. Two…

TREES- Binary Trees, Binary Search Trees, AVL Trees

A Tree is a finite set of one or more nodes such that

STACKS & QUEUES

STACK: Introduction to Stacks, Basic Stack operations, Representation of a Stack using Array, Linked list representation of stacks…

Sorting Algorithms- Insertion Sort, Selection Sort, Quick Sort, Merge Sort, Bubble Sort

Sorting:

Recommended from Medium

Should You Still Learn to Code in 2026?

The answer isn’t as obvious as I used to believe.

How to Master Data Structures and Algorithms Without Feeling Lost 😞

A beginner-friendly guide to understanding DSA deeply, building real problem-solving skills, and avoiding the surface-level learning that…

7 Coding Patterns I Stole From Senior Engineers

Most developers do not become better because they learn more syntax. They become better because they stop making code harder than it needs…

I’ll Instantly Know A Writer Used ChatGPT When I See This

It’s pretty damn obvious now that I know what to look for.

10 Websites Better Than Another Hour of Doomscrolling

Here’s to the rabbit holes worth taking!

DSA Patterns That Actually Make You Think #1: Why Two Sum Is More Than Just an Easy Interview…

Most developers solve Two Sum. Very few understand why it’s one of the best interview questions ever created.

No responses yet

More from Pravallika Devireddy and About Data Structures

Graphs — Introduction, DFS, BFS, Prims Algorithm, Kruskal’s Algorithm and their Implementations

A graph G consists of a set of V or vertices (nodes) and a set if edges (arcs). Vertices are nothing but the nodes in the graph. Two…

TREES- Binary Trees, Binary Search Trees, AVL Trees

A Tree is a finite set of one or more nodes such that

STACKS & QUEUES

STACK: Introduction to Stacks, Basic Stack operations, Representation of a Stack using Array, Linked list representation of stacks…

Sorting Algorithms- Insertion Sort, Selection Sort, Quick Sort, Merge Sort, Bubble Sort

Sorting:

Recommended from Medium

Should You Still Learn to Code in 2026?

The answer isn’t as obvious as I used to believe.

How to Master Data Structures and Algorithms Without Feeling Lost 😞

A beginner-friendly guide to understanding DSA deeply, building real problem-solving skills, and avoiding the surface-level learning that…

7 Coding Patterns I Stole From Senior Engineers

Most developers do not become better because they learn more syntax. They become better because they stop making code harder than it needs…

I’ll Instantly Know A Writer Used ChatGPT When I See This

It’s pretty damn obvious now that I know what to look for.

10 Websites Better Than Another Hour of Doomscrolling

Here’s to the rabbit holes worth taking!

DSA Patterns That Actually Make You Think #1: Why Two Sum Is More Than Just an Easy Interview…

Most developers solve Two Sum. Very few understand why it’s one of the best interview questions ever created.