7 Basic Algorithms Every Newbie Coder Should Know: Part 3
Greeting learners! So this article will be the conclusion of my small series “7 Basic Algorithms Every Newbie Coder Should Know”. Today we will be talking about two very interesting and widely used algorithms in problem-solving but before that, I would like you all to go and check the previous two parts of this series if you have not checked them yet. Here’s a look at the plan for the series :
- Algorithms Introduction: Part 1
- Searching & Sorting Algorithms: Part 2
- Two Pointer & Sliding Window: Part 3
Coming straight to the point today we’ll be learning two of the most widely used algorithms/techniques: Two Pointer & Sliding Window, so let’s learn them in an easy yet interesting way.
TWO POINTER ALGORITHM
It will not be wrong to say that the two-pointer technique is one of the most important tools in any software developer’s kit or even for a beginner it is a must-learn technique as it will assist anyone & everyone throughout their journey & even in their technical interviews. We will understand this technique by asking three questions to ourselves which are: What, Why, How?.
What is the Two Pointer Technique?
The name (Two Pointer) states we use two pointers or markers in this technique to traverse on an iterable like list/array to perform searching operations using two pointers/markers in a single loop on data structures such as lists/arrays, strings, linked lists. Let’s now talk about the variants of two pointer technique :
- Opposite-Directional: In this, each pointer/marker is placed at opposite ends of the array and they move towards each other while traversing until they meet or some other condition satisfies.Questions based on this variant Two Pointer :
- Equi-Directional: In this, each pointer/marker starts from the beginning, one being a slow traverser while the other one is the faster one moving in the same direction until a certain condition is met. Question based on this variant of Two Pointer :
Why use the Two Pointer Technique?
The most prominent reason behind using this technique is to reduce the time complexity of a problem from O(n3) or O(n2) to O(n) or O(nlogn) depending upon whether the array is sorted or not.
How to use the Two Pointer Technique?
Let’s understand this by going through the same question mentioned above, Two Sum (Sorted Array). So the problem is as follows :
Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1,index2 = 2.
We may deduce from the preceding problem that we have been given a sorted array and a number; we must traverse the array and locate two such numbers that add up to the provided number, and then return the indexes of those numbers. Now let's talk about the approaches which can be used to solve this problem :
1. Brute Force | Time Complexity: O(n2)
2. Two Pointer Technique | Time Complexity: O(n)
The first approach is very simple in nature but it takes a lot of time still, I will be explaining both of them just to point out the obvious (time complexity).
Brute Force Approach: In brute force, we use two loops, the outer one iterating over every element one by one & the inner one doing the same but for every single jump over the element of the outer loop the inner loop completes the whole iteration of the array. In this approach, we check the sum of every element of the array with every other element and then compare it with the given sum checking for equality. Code for the same is provided below.
Two Pointer Technique: We use two pointers/markers in this method to discover the elements in the sorted array that add up to the desired value. We begin by initializing two pointers, one to the leftmost index: start = 0 and the other to the end of the array: end = length(array)-1. Now we’ll loop through the array until the start is smaller than the finish, and then add the elements referred to by the pointers to see if they match the required number. We can return the start and end variables if the sum is equal to the number; if the sum is larger than the needed number, we decrement the end variable by one; otherwise, we increment the start by one. Because the array is sorted, we can take advantage of the fact that if we decrease the variable end, the number pointed by it will be smaller than the one before it, lowering the overall sum & the same goes for start increasing it will increase the overall sum. The code for the same has been attached below.
SLIDING WINDOW ALGORITHM
So after the Two Pointer algorithm, we will be talking about the Sliding Window algorithm as after the two-pointer technique it is also one of the most important tools in any software developer’s kit or even for a beginner, it is a must-learn technique as it will assist anyone & everyone throughout their journey & even in their technical interviews. We will understand this technique by asking three questions to ourselves which are: What, Why, How?.
What is Sliding Window Algorithm?
Problems involving linear sequences, such as arrays, can be solved using the sliding window approach. A contiguous sequence that is part of an array is called a window. The window is slid over the array, as the name implies. The window is slid further when some operations are performed on the elements within it. There are various variants of this algorithm but we will not cover all of them in this article, as for this article we will be talking about the most general one out there. Below is a question in which this algorithm can be used.
Why use Sliding Window Algorithm?
This algorithm helps us by reducing the time complexity just like the Two Pointer algorithm & a wide variety of questions and variations of this algorithm are used by a large fraction of the dev community.
How to use the Sliding Window algorithm?
Let’s understand this by going through the same question mentioned above, Substring of Size Three with distinct characters. So the problem is as follows :
You are given an integer array nums consisting of n elements, and an integer k.Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.Example:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
We can derive from the above challenge that we are given a numerical array and a number (k), and we must discover a continuous subarray of length (k) that has the largest average & return the largest average. Now let’s talk about the approaches which can be used to solve this problem :
1. Brute Force | Time Complexity: O(n2)
2. Sliding Window Technique | Time Complexity: O(n)
The first approach is very simple in nature but it takes a lot of time & for this problem I would like you all to try this on your own as it’s very simple. We will be discussing the Sliding Window approach for this problem.
Sliding Window Approach: The main idea is to establish a window of size k, then traverse that window across the array, adding the later element and discarding the preceding one, and then dividing it by k to find and compare the average to get the largest average subarray. So we create two variables: Current Sum and Max Sum, and we store the sum of the first k elements in the current sum before setting Max Sum equal to Current Sum. Now we start looping through the array, starting at index k and going all the way to the end, updating the current sum by adding the later element and removing the preceding one, until we reach the greatest sum corresponding to window size k, and we simply divide it by k to get the average. The code for this can be found below.
Overview: We learned about two very useful algorithms, basic yet highly helpful algorithms in this part of the series “7 Basic Algorithms Every Newbie Coder Should Know” which will assist you out in problem-solving in the themes array/list, linked list, string & in technical interviews too. Also, this marks the end of this series.
Editors Note: First and foremost, thank you for sticking with the article until the finish; please applaud and follow if you learnt something new.
