Must Learn Competitive Programming Algorithms

Hi everyone here i am going to tell you about the major algorithms that are used to solve problems in our competitive coding environment as well as beneficial for the placement exams by applying them on questions.

So these are the following algorithms that i am going to explain with example of the a coding problem , and will try to make it as simple as possible to get you guys grasp easily.

1. Two Pointer Approach
2. Sliding Window Approach
3. Kadane’s Algorithm

# Two pointer Approach

So this kind of approach is generally used in many array problems sets. It is very easy as well as it is space efficient and time efficient , than our brute approaches.

For example , take this question into account,

Q) Given a sorted array A , having N integers find if there exist any pair of elements (A[i] ,A[j]) such that there sum is equal to some value K which is given.

Input : A(5 12 15 20 30 40 70) k=50

output:true

Sol) Lets first see the naive /Brute Force approach that generally come into our mind, by seeing the problem at first instinct ,

1. By using two for loops we just try to find all the pairs of two values that can be possibly sum up to K.
2. As you can see due to two loops here the time complexity is O(n^2), and this is very high if the test cases comes like N:(2 x 10^5).

Now we will discuss about the two pointer approach,

Steps:

A) Initialize the two pointer i=0(pointing at first element)and j=n-1(pointing at last element).

B) Then move the both the pointer according to this condition , if A[i]+A[j] < k then increase the start pointer by one because it is sorted , and we can only find the value k by going on higher values.

C)If the value of sum is more , then decrease the end pointer.

Here you can see clearly that the code is running only once , through the whole array . So time complexity for this code is O (n) which is far more better than the brute force approach when large values are taken into account.

# Sliding Window Approach

By seeing the above image you might have got the idea of how the approach is going to be , yes we will slide a window according to the requirement of the question. This type of approach is generally used in arrays as well as strings problems.

For example , take this question into account,

Q) Given a string s and a non-empty string p, find all the start indices of s’s anagrams in p.

Input: p( “abcdebacb”) , s(“cab”)

Output: {0,5,6}

Sol) Let’s first see the brute force approach that is going to come in our mind , instantly i.e ,

1. Sort the string s.
2. Loop through the p string and take every three character string , sort it , and check it with s string every time.
3. If found add in an array otherwise continue till p’s length.

Now we will discuss about the sliding window approach,

Steps:

A) First we will make the two vectors , total_hash and window_hash and both will be of size 26( because our question only contains small case letters)

B) Then first we will make a window of s string by looping through right = 0 till window’s length , as shown in code.

C) Then till the whole p’s length we will traverse with length 3 and the new character will be added in total_hash and one element from the front will be eliminated because total size can only be three in this case.

D) If at any point if both the hash are the same then increase the count.

Here you can see clearly that the code is running only once , through the whole string . So time complexity for this code is O (n) which is far more better than the brute force approach when large strings are taken into account.

#Kadane Algorithm

The above image might have given you a idea about what are we going to do. So we are going to add every value of the array and then check with some certain conditions according to the problem statement.

This looks simple but it is also a very important approach to decrease the time complexity.

For example , take this question into account,

Q) Given an array of integer , find the maximum possible sum you can from one of its contiguous sub arrays.

Input : -2 -3 4 -1 -2 1 5 3

Output : 7

Sol) Let’s first see the brute force approach that is going to come in our mind , instantly i.e ,

1. Run two for loops till the end.
2. Check for each and every possibility for the maximum sum.

Now we will discuss about the Kadane’s approach,

Steps :

1. We create two variable max_end_here=0 , and max _so_far = INT_MIN.
2. Then we iterate the whole array once and will check the above two defined values according to the conditions.
3. First check for the condition max_end_here<a[i] if a[i] is greater then replace it with max_end_here.
4. Then check for the condition max_end_here<max_so_far if max_so_far is greater then replace it with max_so_far.

5. After doing all these steps we will be having our final max possible sum. This code also works if all the values are negative.

Here you can see clearly that the code is running only once , through the whole array . So time complexity for this code is O (n) which is far more better than the brute force approach when large arrays are taken into account.