.png)
We recommend you to go through Array - I before this blog because we covered some basic informative topics.
Window Sliding Technique
This technique shows how we can reduce time complexity in a few problems by converting nested for-loop to single for-loop.
Illustration:
Given an array of integers of size 'n'.
Our aim is to calculate the maximum sum of 'p'
consecutive elements in the array.
Input : arr[] = {10, 20, 30, 40}
p = 2
Output : 70
Input : arr[] = {10, 40, 20, 100, 230, 30, 10, 0, 200}
p = 4
Output : 390
We get maximum sum by adding subarray {40, 20, 100, 230}
of size 4.
Input : arr[] = {20, 30}
p = 3
Output : Invalid
There is no subarray of size 3 as size of whole
array is 2.The classic approach to solve this problem is to calculate the sum for each of the blocks of P consecutive elements and compare which block has the maximum sum possible.
Therefore time complexity will be O(n * p).
Technique:
The above problem is often solved in Linear Time Complexity by using the Window Sliding Technique by avoiding the overhead of calculating sum repeatedly for every block of k elements.
The technique is often best understood with the windowpane in the bus, consider a window of length n, and therefore 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 plane with current_sum of size k elements. Now, if we apply force on the window such it moves a unit distance ahead. The pane will cover the next k consecutive elements.
Consider an array arr[] = {50, 20, -10, 0, 30} and value of p = 3 and n = 5
Applying window technique :
We compute the sum of first k elements out of n terms employing a linear loop and store the sum in variable window_sum.
Then we'll graze linearly over the array till it reaches the end and simultaneously keeps track of maximum sum.
To get the current sum of the block of k elements just subtract the first element from the previous block and add the last element of the current block.
The below representation will make it clear how the window slides over the array.
This is the initial phase where we have calculated the initial window sum starting from index 0.
At this stage, the window sum is 60. Now, we set the maximum_sum as current_window i.e 60.
[50, 20, -10, 0, 3]
| |
current_sum = window_sumNow, we slide our window by a unit index.
Therefore, now it discards 50 from the window and adds 0 to the window. Hence, we will get our new window sum by subtracting 50 and then adding 0 to it.
So, our window sum now becomes 10.
Now, we will compare this window sum with the maximum_sum. As it is smaller we won't change the maximum_sum.
[50, 20, -10, 0, 30]
| |
current_sum = window_sum + (-50) + (0)Similarly, now once again we slide our window by a unit index and obtain the new window sum to be 20.
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 60.
[50, 20, -10, 0, 30]
| |
current_sum = window_sum + (-20) + (30)Iterators in C++ STL
Iterators are used to point at the memory addresses of STL containers. They're primarily utilized in a sequence of numbers, characters, etc. we will use iterators to move through the contents of the container.
They will be visualized as something almost like a pointer pointing to some location and that we can access the content at that specific location using them.
Basic Operations of iterators:-
begin(): This function is used to return the beginning position of the container.
end(): This function is used to return the after end position of the container.
C++ code to demonstrate the working of begin() and end():
#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main()
{
vector<int> arr = { 1, 2, 3, 4, 5 };
// Declaring iterator to a vector
vector<int>::iterator ptr;
cout << "The vector elements are : ";
for (ptr = arr.begin(); ptr < arr.end(); ptr++)
cout << *ptr << " ";
return 0;
}Output:
The vector elements are : 1 2 3 4 5 advance(): This function is used to increment the iterator position until the specified number mentioned in its arguments.
C++ code to demonstrate the working of advance():
#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main()
{
vector<int> arr = { 1, 2, 3, 4, 5 };
vector<int>::iterator ptr = arr.begin();
//increment iterator position points to 4
advance(ptr, 3);
cout << "The position of iterator after advancing is : ";
cout << *ptr << " ";
return 0;
}Output:
The position of iterator after advancing is : 4 next(): This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.
prev(): This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.
C++ code to demonstrate the working of next() and prev():
#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main()
{
vector<int> arr = { 1, 2, 3, 4, 5 };
vector<int>::iterator ptr = arr.begin();
vector<int>::iterator ftr = arr.end();
auto pd = next(ptr, 3);
auto pd1 = prev(ftr, 3);
cout << "The position using next() is: ";
cout << *pd << " ";
cout << endl;
cout << "The position using prev() is: ";
cout << *pd1 << " ";
cout << endl;
return 0;
}Output:
The position using next() is: 4
The position using prev() is: 3 inserter(): This function is used to insert the elements at any position in the container. It accepts 2 arguments, the container and the iterator to the position where the elements have to be inserted.
C++ code to demonstrate the working of inserter():
#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main()
{
vector<int> arr = {10, 20, 30, 40, 50};
vector<int> arr1 = {100, 200, 300};
vector<int>::iterator ptr = arr.begin();
advance(ptr, 3);
// copying 1 vector elements in other using inserter()
// inserts ar1 after 3rd position in arr
copy(arr1.begin(), arr1.end(), inserter(arr,ptr));
//new vector elements
cout << "The new vector after inserting is : ";
for (int &x : arr)
cout << x << " ";
return 0;
}Output:
The new vector after inserting is : 10 20 30 100 200 300 40 50 Implementing Arrays in Java
Arrays in Java are used to store a group of elements of the same data type at contiguous memory locations.
The general form of array declaration in Java is:
type array-name[];
OR
type[] array-name;An array declaration has two components: the type and the name. Type declares the element type of the array. The element type determines the data type of each element that comprises the array.
For Example:
// both are valid declarations
int intArray[];
or int[] intArray;
byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];Instantiating an Array: When an array is declared, only a reference of the array is created. To actually create or give memory to the array, you create an array like this:
array-name = new type [size];Here,
type specifies the type of data being allocated.
size specifies the number of elements in the array.
array-name is the name of an array variable that is linked to the array.
Example:
int intArray[]; //declaring array
intArray = new int[20]; // allocating memory to arrayArrayList in Java:
ArrayList is a part of the collection framework and is present in java.util package. It provides us dynamic arrays in Java.
Though, it may be slower than standard arrays but can be helpful in programs where lots of array manipulation is needed.
Constructors in Java ArrayList:
ArrayList(): This constructor is used to build an empty array list.
ArrayList(Collection c): This constructor is used to build an array list initialized with the elements from collection c.
ArrayList(int capacity): This constructor is used to build an array list with initial capacity being specified.
Creating a generic integer ArrayList:
ArrayList arrlist = new ArrayList();Java program to demonstrate the working of ArrayList:
import java.io.*;
import java.util.*;
class arrayli
{
public static void main(String[] args)
throws IOException
{
int n = 5;
// declaring
ArrayList<Integer> arrlist = new ArrayList<Integer>(n);
// Appending
for (int i=1; i<=n; i++)
arrlist.add(i);
System.out.println(arrlist);
// Remove element at index 3
arrli.remove(3);
System.out.println(arrlist);
// Printing elements one by one
for (int i=0; i<arrlist.size(); i++)
System.out.print(arrlist.get(i)+" ");
}
} Output:
[1, 2, 3, 4, 5]
[1, 2, 3, 5]
1 2 3 5 Vector Class in Java:
The Vector class implements a growable array of objects. Vectors basically fall in legacy classes but now it's fully compatible with collections.
Vector implements a dynamic array meaning it can grow or shrink as needed. Like an array, it contains components that will be accessed using an integer index.
They are very almost like ArrayList but Vector is synchronized and has some legacy method which collection framework doesn't contain.
It extends AbstractList and implements List interfaces.
Constructor:
Vector(): Creates a default vector of the initial capacity is 10.
Vector(int size): Creates a vector whose initial capacity is specified by size.
Vector(Collection c): Creates a vector that contains the weather of collection c.
Vector(int size, int incrmt): Creates a vector whose initial capacity is specified by size and increment is specified by incrmt. It specifies the number of elements to allocate each time that a vector is resized upward.
Java code to illustrate Vector:
import java.util.*;
class Vector_demo {
public static void main(String[] arg)
{
// Create a vector
Vector<Integer> vtr = new Vector<Integer>();
// Insert elements in the Vector
vtr.add(10);
vtr.add(20);
vtr.add(30);
vtr.add(40);
vtr.add(30);
// Print the Vector
System.out.println("Vector is " + vtr);
}
}Output:
Vector is [10, 20, 30, 40, 30]Sample Problems on Array
Problem #1: Equilibrium index of an array
Description: Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. We are given an array of integers, We have to find out the first index from left such that -
A[0] + A[1] + ... A[i-1] = A[i+1] + A[i+2] ... A[n-1]Input
[-7, 1, 5, 2, -4, 3, 0]
Output
3
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]Naive Solution: We can iterate for each index i and calculate the leftsum and rightsum and check whether they are equal.
for (i=0 to n-1)
{
leftsum = 0
for (j = 0 to i-1)
leftsum += arr[i]
rightsum = 0
for (j = i+1 to n-1)
rightsum += arr[i]
if leftsum == rightsum :
return i
}Time Complexity: O(n^2)
Auxiliary Space: O(1)
Tricky Solution: The idea is to get the total sum of the array first. Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get the right sum by subtracting the elements one by one. Then check whether Leftsum and Rightsum are equal.
Pseudo Code
// n : size of array
int eqindex(arr, n)
{
sum = 0
leftsum = 0
for (i=0 to n-1)
sum += arr[i]
for (i=0 to n-1)
{
// now sum will be righsum for index i
sum -= a[i]
if (sum == leftsum )
return i
leftsum += a[i]
}
}Time Complexity: O(n)
Auxiliary Space: O(1)
Problem #2: Largest Sum Subarray
Description: We are given an array of positive and negative integers. We have to find the subarray having a maximum sum.
Input
[-3, 4, -1, -2, 1, 5]
Output
7
(4+(-1)+(-2)+1+5)Solution: Simple idea is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of the maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive-sum compare it with max_so_far and if, it is greater than max_so_far, update max_so_far.
Pseudo Code:
//n : size of array
int largestsum(arr, n)
{
max_so_far = INT_MIN
max_ending_here = 0
for (i=0 to n-1)
{
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
return max_so_far
}
}Time Complexity :O(n)
Auxiliary Space :O(1)
Problem #3: Merge two sorted Arrays
Description: We are given two sorted arrays arr1[ ] and arr2[ ] of size m and n. We have to merge these arrays and store the numbers in arr3[ ] of size m+n.
Input
1 3 4 6
2 5 7 8
Output
1 2 3 4 5 6 7 8Solution: Idea is to traverse both arrays simultaneously and compare the current numbers from both the Arrays. Pick the smaller element and copy to arr3[ ] and advances the current index of the array, from where the smaller element is picked. When we reach the end of one of the array, Copy the remaining elements of another array to arr3[ ].
Pseudo Code:
// input arrays - arr1(size m), arr2(size n)
void merge_sorted(arr1, arr2, m, n)
{
arr3[m+n] // merged array
i=0,j=0,k=0
while(i < m && j < n)
{
if arr1[i] < arr2[j] :
arr3[k++] = arr1[i++]
else :
arr3[k++] = arr2[j++]
}
while(i < m)
arr3[k++] = arr1[i++]
while(j < n)
arr3[k++] = arr2[j++]
}Time Complexity: O(m+n)
Auxiliary Space: O(m+n)
I hope you have learned something.
Happy Coding!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.
Comentários