Window Sliding
Technique Window Sliding Technique
Given an array of integers of size ‘n’. Our aim is to calculate the maximum
sum of ‘k’ consecutive elements in the array.
The technique can be best understood with the window pane in bus, consider a
window of length n and the pane which is fixed in it of length k. Consider, initially
the pane is at extreme left i.e., at 0 units from the left. Now, co-relate the window
with array arr[] of size n and pane with current_sum of size k elements. Now, if we
apply force on the window such that it moves a unit distance ahead. The pane will
cover next k consecutive elements.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Window Sliding
Technique
Consider an array arr[] = {5, 2, -1, 0, 3} and value of k = 3 and n = 5
Applying sliding window technique :
1.We compute the sum of first k elements out of n terms using a linear loop and
store the sum in variable window_sum.
2.Then we will graze linearly over the array till it reaches the end and
simultaneously keep track of maximum sum.
3.To get the current sum of block of k elements just subtract the first element from
the previous block and add the last element of the current block .
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Window Sliding
Technique
This is the initial phase where we have calculated the initial window sum
starting from index 0 .
At this stage the window sum is 6.
Now, we set the maximum_sum as current_window i.e 6.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Window Sliding
Technique
Now, we slide our window by a unit index. Therefore, now it discards 5 from the
window and adds 0 to the window. Hence, we will get our new window sum by
subtracting 5 and then adding 0 to it. So, our window sum now becomes 1. Now,
we will compare this window sum with the maximum_sum. As it is smaller we wont
the change the maximum_sum.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Window Sliding
Technique
Similarly, now once again we slide our window by a unit index and obtain the new
window sum to be 2. Again we check if this current window sum is greater than the
maximum_sum till now. Once, again it is smaller so we don’t change the
maximum_sum.
Therefore, for the above array our maximum_sum is 6.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Window Sliding For this question, take the input [5, 2, 4, 6, 3, 1]
Technique as the input.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Loop Detection
Algorithm
Floyd’s Cycle-Finding Algorithm
Approach: This is the fastest method and
has been described below:
•Traverse linked list using two pointers.
•Move one pointer(slow_p) by one and
another pointer(fast_p) by two.
•If these pointers meet at the same node
then there is a loop. If pointers do not
meet then linked list doesn’t have a loop.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Loop Detection
Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
The Rabin-Karp string matching algorithm calculates a hash value
for the pattern, as well as for each M-character subsequences of
text to be compared.
If the hash values are unequal, the algorithm will determine the
hash value for next M-character sequence. If the hash values are
equal, the algorithm will analyze the pattern and the M-character
sequence.
In this way, there is only one comparison per text subsequence,
and character matching is only required when the hash values
match.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
How Rabin-Karp Algorithm Works?
A sequence of characters is taken and checked for the possibility of the presence
of the required string. If the possibility is found then, character matching is
performed.
Let us understand the algorithm with the following steps:
1.Let the text be
And the string to be searched in the above text be:
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
Let us assign a numerical value(v)/weight for the characters we will be using in the
problem. Here, we have taken first ten alphabets only (i.e. A to J).
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
m be the length of the pattern and n be the length of the text. Here, m = 10 and n = 3.
Let d be the number of characters in the input set.
Here, we have taken input set {A, B, C, ..., J}. So, d = 10. You can assume any suitable value
for d.
Let us calculate the hash value of the pattern.
hash value for pattern(p) = Σ(v * dm-1) mod 13
= ((3 * 10^2) + (4 * 10^1) + (4 * 10^0)) mod 13
= 344 mod 13
=6
In the calculation above, choose a prime number (here, 13) in
such a way that we can perform all the calculations with
single-precision arithmetic.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
For the first window ABC,
hash value for text(t) = Σ(v * dn-1) mod 13
= ((1 * 10^2) + (2 * 10^1) + (3 * 10^0)) mod 13
= 123 mod 13
=6
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
Algorithm
n = t.length
m = p.length
h = dm-1 mod q
p=0
t0 = 0
for i = 1 to m
p = (dp + p[i]) mod q
t0 = (dt0 + t[i]) mod q
for s = 0 to n - m
if p = ts
if p[1.....m] = t[s + 1..... s + m]
print "pattern found at position" s
If s < n-m
ts + 1 = (d (ts - t[s + 1]h) + t[s + m + 1]) mod q
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
Limitations of Rabin-Karp Algorithm
Spurious Hit
When the hash value of the pattern matches with the hash value of a window of the text
but the window is not the actual pattern then it is called a spurious hit.
Spurious hit increases the time complexity of the algorithm. In order to minimize spurious
hit, we use modulus. It greatly reduces the spurious hit.
Rabin-Karp Algorithm Complexity
The average case and best case complexity of Rabin-Karp algorithm is O(m + n) and the
worst case complexity is O(mn).
The worst-case complexity occurs when spurious hits occur a number for all the windows.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Rabin Karp Algorithm
Rabin-Karp Algorithm Applications
•For pattern matching
•For searching string in a bigger text
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
Maximum Subarray Problem is a famous problem in dynamic
programming. The algorithm we use to solve this problem is known as
Kadane’s algorithm
What is the Maximum Subarray Problem?
This problem requires you to find the largest possible sum of a
contiguous subarray, within a given one-dimensional array A[1…n] of
numbers.
The array will contain negative integers. If the array only contains
positive integers then the answer will be the sum of the complete
array.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
1.Initialize max_so_far = 0
Kadane’s Algorithm
The Kadane’s Algorithm 2.Initialize max_ending_here = 0
solves this problem by 3.Repeat steps 4 to 6 for each element of
traversing over the
entire array and the array
keeping two variables 4.set max_ending_here =
to track the sum so far
and overall maximum. max_ending_here + a[i]
The conditions under 5.if(max_ending_here < 0) then set
which each of the two
variables are updated max_ending_here = 0
are important. 6.if(max_so_far < max_ending_here) then
set max_so_far = max_ending_here
7.return max_so_far
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
When the variable max_ending_here becomes negative, we set it to zero. At each
iteration, we check for max_so_far < max_ending_here, if the condition is true then we
update max_so_far.
The for loop for steps 4 to 6 will be :
for (int i = 0; i < length; i++)
{
max_ending_here = max_ending_here + arr[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Kadane’s Algorithm
The maximum subarray is from i=2 to i=6. The maximum sum is 7.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Heap Sort Algorithm
Algo.
Heap Sort is a popular and efficient sorting algorithm in computer programming.
Learning how to write the heap sort algorithm requires knowledge of two types of data
structures - arrays and trees.
The initial set of numbers that we want to sort is stored in an array e.g. [10, 3, 76, 34,
23, 32] and after sorting, we get a sorted array [3,10,23,32,34,76]
Heap sort works by visualizing the elements of the array as a special kind of complete
binary tree called a heap.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
Relationship between Array Indexes and
Tree Elements
A complete binary tree has an interesting
property that we can use to find the
children and parents of any node.
If the index of any element in the array is
i, the element in the index 2i+1 will
become the left child and element in
2i+2 index will become the right child.
Also, the parent of any element at index i
is given by the lower bound of (i-1)/2.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
What is Heap Data Structure?
Heap is a special tree-based data structure. A
binary tree is said to follow a heap data
structure if
• it is a complete binary tree
• All nodes in the tree follow the property
that they are greater than their children
i.e. the largest element is at the root and
both its children and smaller than the root
and so on. Such a heap is called a max-
heap. If instead, all nodes are smaller than
their children, it is called a min-heap
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
How to "heapify" a tree
Starting from a complete binary tree, we can modify it to become a Max-Heap by
running a function called heapify on all the non-leaf elements of the heap.
Since heapify uses recursion, it can be difficult to grasp. So let's first think about how you
would heapify a tree with just three elements.
heapify(array)
Root = array[0]
Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
if(Root != Largest)
Swap(Root, Largest)
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
Now let's think of another scenario in which there is more than one level.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
The top element isn't a
max-heap but all the sub-
trees are max-heaps.
To maintain the max-
heap property for the
entire tree, we will have
to keep pushing 2
downwards until it
reaches its correct
position.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
We can combine both these conditions in one heapify function as
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
} This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
Build max-heap
To build a max-heap from any tree, we can thus start heapifying each sub-tree from the
bottom up and end up with a max-heap after the function is applied to all the elements
including the root element.
In the case of a complete tree, the first index of a non-leaf node is given by n/2 - 1. All
other nodes after that are leaf-nodes and thus don't need to be heapified.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Sorting and Searching
Algo.
How Heap Sort Works?
1.Since the tree satisfies Max-Heap property, then the largest item is stored at
the root node.
2.Swap: Remove the root element and put at the end of the array (nth
position) Put the last item of the tree (heap) at the vacant place.
3.Remove: Reduce the size of the heap by 1.
4.Heapify: Heapify the root element again so that we have the highest
element at root.
5.The process is repeated until all the items of the list are sorted.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
