How Sliding window works?

Sliding window is a problem solving technique by which we can find the maximum sum of k consecutive values in an n size array or array type data structure. This method usually uses a one-way for loop.

Suppose we are given an array of size n=9 and we need to extract Here is the maximum value of 4 consecutive numbers.

n = [ 5, 7, 1, 4, 3, 6, 2, 9, 2]

If we want to solve this problem by brute force method. In that case our time complexity can be O(n2) or O(n3). Which is very time consuming.

In this case we can use sliding window technique. which can give us the expected answer in O(n) time.

As you can see from the above code, we first extract the sum of the first 4 numbers of the array and put it in max_sum. In the next loop, we add the next numbers and subtract the last number from that sum. Through which we got the sum of every 4 consecutive numbers in the loop.

Suppose, the max_sum variable contains the sum of the first four numbers [5, 7, 1, 4]. Now if we add the 5th value of n array to max_sum and subtract the 1st value. So, we can find the sum of values 2-5 of n array. Thus we will find the sum of all the k consecutive number values in the array.

Then by comparing those numbers we find out the highest sum.

Time Complexity: O(n)

Comments

Binary Search Algorithm!

Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹. Here's how it works: 1. Compare x with the middle element. 2. If x matches with the middle element, we return the mid index. 3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half. 4. Else (x is smaller) recur for the left half. This process continues until the element is found or the subarray is empty. Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n) time which is very long time. So, if an array is sorted we always use Binary search. Algorithm: int main() { optimize(); int arr[]= {1,4,5,8,10,26...

Two Pointer Technique

The two-pointer technique is a simple and effective technique that is used in competitive programming. It helps programmer to efficiently solve array problem. In two-pointer we take two pointer at the start and the end. That pointers started to iterate the whole array and solve problem according to a programmer. Suppose, we have an array n which consists m number of values. Now, if we want to sum all the element of the array then we have to iterate the whole array and sum all the element. Which will take O(n) time. n = [4, 5, 2, 4, 9, 4] But, in two-pointer technique we can solve this problem in O(n/2) time. Which is more efficient than traditional way. In the code, we used two variable st which point at first element of the array and en which point at the last element of the array. After this, we take a while loop which condition is st should be less than en. If the condition does not meet the value, then loop will break. In the loop, we summed the first value and last value that are ...

Rotated Array(Modified Binary Search)

A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very ...

Ryansblog

Search This Blog