Sliding Window Technique

Are you also tired of using two for loop or nested loop, so there is a magic technique known as Sliding window technique which reduces your problem in only one for loop and reduce your program time complexity

Let’s learn it by example

Given a set of array element's
You need to find the maximum sum of 'm' consecutive element's
Suppose 
arr[] ={1,3,2,5,6};
and m = 3;
So, the maximum sum of 3 consecutive elements is 2+5+6 = 13

Let’s try it firstly with brute force technique,

We run our loop starting from index – 0 and run up to index n-m-1 and for every index we check sum of it’s next m elements and if sum is maximum we update our variable,

Here is the code

int maxSumBrute(int arr[],int n,int m)
{
  int currSum = 0,maxSum;
  for(int i = 0;i<n-m-1;i++)
   {
     for(int j = i;j<m+i;j++)
       currSum = currSum+arr[j];
     if(maxSum<currSum)
       maxSum = currSum;
     currSum = 0;
   }
  return maxSum;
}


As you can see above code is nested loop code and time complexity is O(n*m)

Can we solve this in linear Time, Yes Using window sliding technique it is possible. Practice Here

Sliding window technique

Now, Imagine this technique as a Train, where train is array and every window is array element and also there is pane which we slide

Train represent Array

Window represent Element’s

sliding window technique
sliding window technique

See above, Pane is allow to slide and window is fixed, i.e array element.

Pane length is of 3 size and total windows are 5. We start our pane from the 0th index and cover the first 3 elements and calculate sum which is 6

Now, we slide our Pane to next index like this,

Now, Pane length is of again 3 sizes and what we do is, add the next index element covered in the pane and subtract the 0th index(released index). So, sum is 6+5-1=10

10 is maximum element till now, hence we update our variable and now maxSum is 10

We again slide our pane to next window

sliding window technique

Same as above, we add next element covered in pane and subtract released element from left side. Hence sum = 10+6-3 which is 13

13 is greatest element till now and we update our maxSum to 13

Here is the code

int maxSum(int arr[],int n,int m)
{
    
  
    int sum = 0; 
    for (int i=0; i<m; i++) 
       sum += arr[i]; 
   
    int maxSum=sum;
	int in=0;
	for(int i=m;i<n;i++)
	{
		sum=sum+arr[i]-arr[i-m];
		if(sum>maxSum)
		maxSum=sum;
	}
  
    return maxSum; 
}

Practice section – Easy Question, Medium Question on Sliding window

What is sliding window technique

This is a technique used to reduce the time complexity to linear

Where sliding window techniques is used

It is mostly used in competetive programming

Tagged :

Vector in C++ STL

Vector in C++

We Already know how to declare array in our previous post. In this post we focus how to declare array as vector using c++ STL library. Most importantly we discusse the c++ header library to make array of dynamic size in this post.

However, Some of the most commonly used classes for implementing sequential lists or arrays are

Vector

List

Let’s look at vector in this post in details.

Vector

A vector in C++ STL is a class that represents a dynamic array. The advantages of vector over normal arrays are,

  • We do not need to pass size as an extra parameter when we pass a vector.
  • Vectors have many in-built functions for erasing an element, inserting an element, etc.
  • Vectors support dynamic sizes, we do not have to initially specify the size of a vector. However, resizing of vector also be done.
  • There are many other functionalities vector provide.

Vectors are dynamic Array

Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. To clarify, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens but Inserting and erasing at the beginning or in the middle is linear in time. In short , vectors are purely dynamic array.

To use the Vector class, include the below header file in your program:

#include< vector >


Declaring Vector:

vector< Type_of_element > vector_name;

For example, Type_of_element can be any valid C++ data type,
or can be any other container also like Pair, List etc.

Important Function in Vector

  • begin() – Returns an iterator pointing to the first element in the vector.
  • end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector.
  • size() – Returns the number of elements in the vector.
  • capacity() – Returns the size of the storage space currently allocated to the vector expressed as the number of elements.
  • empty() – Returns whether the container is empty. In other words, it gives you boolean value.
  • push_back() – It pushes the elements into a vector from the back.
  • pop_back() – Poping from the back is done by pop_back function
  • insert() – It inserts new elements before the element at the specified position.
  • erase() – It is used to remove elements from a container from the specified position or range.
  • swap() – It is used to swap the contents of one vector with another vector of the same type and size.
  • clear() – It is used to remove all the elements of the vector container.
  • emplace() – It extends the container by inserting a new element at the position.
  • emplace_back() – It is used to insert a new element into the vector container, but, the new element is added to the end of the vector.



// C++ program to illustrate the above functions

#include <iostream> 
#include <vector> 

using namespace std; 

int main() 
{ 
    vector<int> v; 
    
    // Push elements 
    for (int i = 1; i <= 5; i++) 
        v.push_back(i); 

    cout << "Size : " << v.size(); 
    
    // checks if the vector is empty or not 
    if (v.empty() == false) 
        cout << "\nVector is not empty"; 
    else
        cout << "\nVector is empty"; 

    cout << "\nOutput of begin and end: "; 
    for (auto i = v.begin(); i != v.end(); ++i) 
        cout << *i << " "; 
        
    // inserts at the beginning 
    v.emplace(v.begin(), 5); 
    cout << "\nThe first element is: " << v[0]; 
  
    // Inserts 20 at the end 
    v.emplace_back(20); 
    int n = v.size(); 
    cout << "\nThe last element is: " << v[n - 1]; 
  
    // erases the vector 
    v.clear(); 
    cout << "\nVector size after erase(): " << v.size();     

    return 0; 
}

Output:
Size : 5
Vector is not empty
Output of begin and end: 1 2 3 4 5 
The first element is: 5
The last element is: 20
Vector size after erase(): 0

Example 1 – Try Hand on this Leetcode problem

Tagged : / /

Linear Search in C/C++

Linear Search

Linear Search in C/C++ means to sequentially traverse a given list or array and check if an element is present in the respective array or list. The idea is to start traversing the array and compare elements of the array one by one starting from the first element with the given element until a match is found or the end of the array is reached.

Examples :

Input : arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
          key = 110;
Output : 6
Element 110 is present at index 6

Input : arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
           key = 175;
Output : -1
Element 175 is not present in arr[].

Problem in Linear Search

Given an array arr[] of N elements, write a function for Linear Search in C to search a given element X in arr[].

Algorithm:

  • Start from the leftmost element of arr[] and one by one compare X with each element of arr[].
  • If X matches with an element, return the index.

If X doesn’t match with any of elements and end of the array is reached, return -1

// Function to linearly search the element X in the 
// array arr[] of N elements
int search(int arr[], int N, int X) 
{    
    // Pointer to traverse the array
    int i; 

    // Start traversing the array
    for (i = 0; i < N; i++) 
    {   
        // If a successful match is found,
        // return the index
        if (arr[i] == X) 
            return i; 
    }

    // If the element is not found,
    // and end of array is reached
    return -1; 
}

Time Complexity

O(N). Since we are traversing the complete array, so in worst case when the element X does not exists in the array, number of comparisons will be N. Therefore, worst case time complexity of the linear search algorithm is O(N).

Tagged : /

Array in C| All You Need To Know

Introduction To Array in C

An array in c is a collection of items of the same data type stored at contiguous memory locations. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

For simplicity, we can think of an array as a fleet of stairs where on each step is placed a value (let’s say one of your friends). Here, you can identify the location of any of your friends by simply knowing the count of the step they are on.

Remember: “Location of next index depends on the data type we use

Array By GeeksToCode
Arrat in C

Defining an Array in C:

Array’s definition is similar to defining any other variable. There are two things need to be kept in mind, the data type of the array elements and the size of the array. The size of the array is fixed and the memory for an array needs to be allocated before use, the size of an array cannot be increased or decreased dynamically.

                                                                 ARRAY OF INTEGER’S

          3         4        6         8         9   1     10

   200               202            204                 206             208              210             212

Declaring Array             

Data Type   arrayName[size of array];

Initializing Array            –     

   Data Type arrayName[size of array] = {values separated by comma};

Accessing array elements:

Arrays allow accessing elements randomly. Elements in an array can be accessed using indexes. Suppose an array named arr stores N elements. Indexes in an array are in the range of 0 to N-1, where the first element is present at 0-th index and consecutive elements are placed at consecutive indexes. Element present at ith index in the array arr[] can be accessed as arr[i].

#include<iostream>
using namespace std;
int main()
{
    int arr[10]= {1,2,3,4,5,6,9,7,8,10};  // Declaring an array of Integers // Initializing array
    for(int i = 0;i<10;i++)
    cout<<arr[i]<<" ";
    return 0;
}

Output - 1 2 3 4 5 6 9 7 8 10
#include<iostream>
using namespace std;
int main()
{
    char arr[5]= {'a','g','h','i','j'};  // Declaring an array of Character // Initializing array
    for(int i = 0;i<5;i++)
    cout<<arr[i]<<" ";
    return 0;
}
Output a g h i j

Memory Assigning in Array

Memory assigned in array in linear fashion Here is a simple example

Note – 1 When you print the name of the array, you indirectly accessing the first element of the array

#include<iostream>
using namespace std;
int main()
{
    int arr[10]= {1,2,3,4,5,6,9,7,8,10};  
  
    for(int i = 0;i<10;i++)
    cout<<arr+i<<" ";
    return 0;
}

When you run this program, You will see the address of each element of the array is incremented by 4. Here 4 is the size of Integer

So, we can conclude that the next index of the array have the address of previous index + size of data type used

Address of index 1 = Address of index 0 + size of (data type);

Do the same for character array and see the result

Advantages of using arrays:

Arrays allow random access of elements. This makes accessing elements by position faster.

Arrays have better cache locality that can make a pretty big difference in performance.

Disadvantages of Arrays

The number of elements to be stored in an array should be known in advance.

An array is a static structure (which means the array is of fixed size). …

Insertion and deletion are quite difficult in an array as the elements are stored in consecutive memory locations and the shifting operation is costly.

Topics To Be Discussed

  1. Searching
  2. Sorting
  3. Sliding Window Technique
  4. Prefix Sum Technique
Tagged : /