struct Stack
{
int Data;
struct Stack *next;
}*top;
void popStack()
{
struct Stack *temp = top;
if(temp == NULL)
printf("\nStack Empty")
else{
top = top->next;
free(temp);
}
}
void pushStack(int value)
{
struct Stack *temp;
temp=(struct Stack *)malloc(sizeof(Stack Node));
temp->Data=value;
if (top == NULL)
{
top=temp;
top->next=NULL;
}
else
{
temp->next=top;
top=temp;
}
}
void display()
{
struct Stack *var=top;
if(var == NULL)
printf("Stack is Empty");
else
{
while(var!=NULL) {
printf("%d \n",var->Data);
var=var->next;
}
}
}
Category Archives: Algorithms
Stack using array
#define size 10
struct stack {
int s[size];
int top;
} st;
int stfull() {
if (st.top >= size - 1)
return 1;
else
return 0;
}
void push(int item) {
st.s[st.top++] = item;
}
int stempty() {
if (st.top == -1)
return 1;
else
return 0;
}
int pop() {
int item;
item = st.s[st.top];
st.top--;
return (item);
}
void display() {
int i;
if (stempty())
printf("\nStack Is Empty!");
else {
for (i = st.top; i >= 0; i--)
printf("\n %d", st.s[i]);
}
}
Remove duplicate from unsorted linked list
METHOD 1 (Using two loops)
struct node
{
int data;
struct node *next;
};
void removeDuplicates(struct node *start)
{
struct node *ptr1, *ptr2, *dup;
ptr1 = start;
while(ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;
while(ptr2->next != NULL)
{
if(ptr1->data == ptr2->next->data)
{
dup = ptr2->next;
ptr2->next = ptr2->next->next;
free(dup);
}
else
{
ptr2 = ptr2->next;
}
}
ptr1 = ptr1->next;
}
}
Time Complexity: O(n^2)
METHOD 2 (Use Sorting)
In general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)
Please note that this method doesn’t preserve the original order of elements.
Time Complexity: O(nLogn)
METHOD 3 (Use Hashing)
void deleteDups(LinkedListNode n)
{
Hashtable table = new Hashtable();
LinkedListNode previous = null;
while (n != null) {
if (table.containsKey(n.data))
previous.next = n.next;
else {
table.put(n.data, true);
previous = n;
}
n = n.next;
}
}
Time Complexity: O(n) on average
Find k largest(or smallest) elements in an array. No sorting allowed
Min Heap method
- Build a Min Heap of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
- For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of min heap.
If the element is greater than the root then make it root and call heapify for min heap.
else ignore it. O((n-k)*logk) - Finally, min heap has k largest elements and root of the min heap is the kth largest element.
O(k + (n-k)Logk) without sorted output. - If sorted output is needed then O(k + (n-k)Logk + kLogk)
void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void minHeapify(int a[], int size, int i)
{
int l = 2*i + 1; //using zero based arrays
int r = 2*i + 2;
int smallest = i;
if(l<size && a[l]<a[smallest])
smallest = l;
if(r<size && a[r]<a[smallest])
smallest = r;
if(smallest!=i)
{
swap(&a[i],&a[smallest]);
minHeapify(a,size,smallest);
}
}
void buildMinHeap(int a[], int size) {
for(int i=size/2;i>=0;i--)
minHeapify(a,size,i);
}
int kthLargest(int a[], int size, int k)
{
int minHeap[k];
int i;
for(i=0;i<k;i++)
minHeap[i] = a[i];
buildMinHeap(minHeap,k);
for(i=k;i<size;i++)
{
if(a[i]>minHeap[0])
{
minHeap[0]=a[i];
minHeapify(minHeap,k,0);
}
}
return minHeap[0];
}
Heap Tree
A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1
Heap of height h
- The levels above the lowest level form a complete binary tree of height h -1 and 2h -1 nodes.
- minimum number of nodes possible in a heap of height h is 2h.
- maximum number of nodes is 2h+1 -1 nodes.
Four basic procedures on heap are
- Heapify, which runs in O(log n) time.
- Build-Heap, which runs in linear time.
- Heap Sort, which runs in O(n log n) time.
- Extract-Max, which runs in O(log n) time
Median of the two sorted arrays of different sizes
Overall run time complexity should be O(log (m+n)).
int find_kth(int a[], int b[], int size_a, int size_b, int k)
{
if(size_a > size_b)
return find_kth(b, a, size_b, size_a, k);
if(size_a == 0)
return b[k-1];
if(k ==1)
return min(a[0], b[0]);
// K should be less than the size of array
int i = min(size_a, k/2);
int j = min(size_b, k/2);
if(a[i-1] > b[j-1])
// Now we need to find only K-j th element
return find_kth(a, b+j, size_a, size_b -j, k-j);
else
return find_kth(a+i, b, size_a-i, size_b, k-i);
return -1;
}
int find_median(int a[], int b[], int size_a, int size_b)
{
int left = (size_a + size_b +1)/2;
int right = (size_a + size_b +2)/2;
return ((find_kth(a,b, size_a,size_b, left) +
find_kth(a,b, size_a,size_b, right))/2);
}
Median of two sorted arrays of same size
Algorithm
- If length of both arrays is 1, take average and return the value.
- If length of both arrays is 2, then return following value (max(array1[0], array2[0]) + min(array1[1], array2[1]) )/2
- If length is greater than 2, follow steps below
- Find median of array1 and array2 individually. Let them be M1 and M2
- If M1 == M2 return M1
- If M1 < M2 follow step 1 onwards with array1[mid…N] and array2[0, mid-1]
- If M2 < M1 follow step 1 onwards with array2[mid…N] and array1[0, mid-1]
int getMedian(int ar1[], int ar2[], int n)
{
int m1;
int m2;
if (n == 1)
return (ar1[0] + ar2[0])/2;
if (n == 2)
return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
m1 = median(ar1, n);
m2 = median(ar2, n);
if (m1 == m2)
return m1;
/* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
if (m1 < m2)
{
if (n % 2 == 0)
//If no. of elements are even, then do not include the middle element in next step
return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1);
else
//If no. of elements are odd, then include the middle element in next step
return getMedian(ar1 + n/2, ar2, n - n/2);
}
/* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
else
{
if (n % 2 == 0)
return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1);
else
return getMedian(ar2 + n/2, ar1, n - n/2);
}
}
/* Function to get median of a sorted array */
int median(int arr[], int n)
{
if (n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}
Fixed Point in a given sorted array
Fixed Point in an array is an index i such that arr[i] is equal to i
int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
return -1;
}
Find index of a peak element
int findPeakUtil(int arr[], int low, int high, int n)
{
int mid = (low + high)/2;
if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
(mid == n-1 || arr[mid+1] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid-1] > arr[mid])
return findPeakUtil(arr, low, (mid -1), n);
else return findPeakUtil(arr, (mid + 1), high, n);
}
find minimum element in a sorted and rotated array
Need to handle duplicates also
#include <stdio.h>
int min(int x, int y) { return (x < y)? x :y; }
int findMin(int arr[], int low, int high)
{
// incase when array is not rotated
if (high < low) return arr[0];
// If there is only one element left
if (high == low) return arr[low];
// Find mid
int mid = (low + high)/2;
// Check if element (mid+1) is minimum element. Consider the cases like {1, 1, 0, 1}
if (mid < high && arr[mid+1] < arr[mid])
return arr[mid+1];
// This case causes O(n) time
if (arr[low] == arr[mid] && arr[high] == arr[mid])
return min(findMin(arr, low, mid-1), findMin(arr, mid+1, high));
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return arr[mid];
// Decide whether we need to go to left half or right half
if (arr[high] > arr[mid])
return findMin(arr, low, mid-1);
return findMin(arr, mid+1, high);
}
Learn By Coding 