An array is a simple data structure where elements of the same type are stored in a sequence.
File: "arr1.cpp"
#include <iostream>
using namespace std ;
int sum( int arr1[] , int size )
{
int result = 0 ;
if ( size == 0 )
return 0 ;
for( int i1=0 ; i1<size ; i1++ )
{
result += arr1[ i1 ] ;
} //for
return result ;
}
int main()
{
int array1[] = { 4 , 3, 2, 1, 5 } ;
cout << sum( array1, 5 ) << endl ;
}
Output:
$ g++ arr1.cpp ; ./a.exe 15
Ex1:
File: "ex+1.cpp"
#include <iostream>using namespace std ;//This function should print the max and min elements of the//arrayvoid maxMin( int arr1[] , int size ){}void printArray( int arr1[] , int size ){ for( int i1=0 ; i1 < size ; i1++ ) { cout << arr1[i1] << " " ; } cout << endl ;}void reverseArray( int arr1[] , int size ){ int i1, j1 , temp ; //Do not declarate any other variables //}int main(){ int array1[] = { 4 , 3, 2, 1, 5 } ; maxMin( array1, 5 ) ; reverseArray( array1, 5 ) ; printArray( array1, 5 ) ;}
$ g++ ex_1.cpp ; ./a.exe max:5 min:1 5 1 2 3 4
Sliding window technique
The sliding window technique involves keeping a subarray ( section of the array ) with a left index and a right index and moving it from left to right to solve a problem.
Let's say we have to find
Maximum of all subarrays of size k
Ex:
int array1[] = { 10 , 20, 30, 40, 50 } ;
We want to find the maximum sum of a subarray of length k=3 . A brute force solution produces the sums.
10+20+30 = 60
20+30+40 = 90
30+40+50 = 120
We have 120 as the maximum sum of all sub arrays of size 3. We notice that in the first sum we have 60.
10 20 30 40 50 60
<-- -->
<-- -->
If we consider the sliding window of size 3 and then move the sliding windows 1 step to the right we evaluate the new sum as:
previous old sum - 10 + 40
We do not need to compute the sum of 20 and 30. For a small k it may not seem like a great deal but if k were large and our array also large then we can save summing of those middle numbers every time.
Ex 2
The below code has the brute force approach written out for you. Complete the code for the sliding window approach.
File: "ex_2.cpp"
#include <iostream>using namespace std ;/*Maximum (Maximum of all subarrays of size k)*/ int findMaxSumOfK( int arr1[] , int lengthOfArray, int k1 ) { int maxSum = 0 ; for( int i1=0 ; i1 < (lengthOfArray - k1 + 1) ; i1++ ) { int newSum = 0 ; newSum = arr1[i1] + arr1[i1+1] + arr1[i1+2] ; if ( newSum > maxSum ) maxSum = newSum ; } //for return maxSum ; } int findMaxSumOfKUseSlideWindow( int arr1[], int lengthOfArray, int k1 ) { int maxSum = 0 ; return maxSum ; }int main(){ int array1[] = { 10 , 20, 30, 40, 50 } ; cout << findMaxSumOfK( array1, 5 , 3) << endl ; cout << findMaxSumOfKUseSlideWindow( array1, 5 , 3) << endl ;}
Output:
$ g++ ex2.cpp ; ./a.exe
120
120
Exercise 3
We have a 2 dimensional array of same width and height. We have to print out the elements in a "spiral" fashion. For the array:
1 2 3
4 5 6
7 8 9
The printout will be:
1 2 3 6 9 8 7 4 5
For the array:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
The printout will be:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
One approach is to use a variable called size that in the above case starts out at 4 . We then print the outer square with the originX and originY as 0 and 0 .
Once that is done then we work on the inner grid with the size as 4-2=2 and the originX = 1 and originY = 1 . We keep working on the inner square till the size is 0 or negative.
File: "ex_3.cpp"
#include <iostream>using namespace std ;void spiral ( int array1[][4] , int size ){ int noItems = size * size ; int sizeOfGrid = size ; int originX = 0 ; int originY = 0 ; while ( true ) { //top row //right most row //bottom most row //left most row sizeOfGrid = sizeOfGrid-2 ; originX++ ; originY++ ; if ( sizeOfGrid <= 0 ) break ; }}int main(){ // int array1[3][3] = { {1, 2,3} , {4, 5,6}, {7,8,9} } ; int array1[4][4] = { {1, 2,3,4} , {5,6,7,8}, {9,10,11,12} , {13,14,15,16} } ; spiral (array1 , 4 ) ; //cout << stackLeft.pop() << endl ;}
Exercise 4
An array has odd number of elements. An element in the array can have another matching element in the array. Find the one element that is unpaired.
int array1[] = {1, 2, 3, 2 , 1 } ;
The unpaired element is 3 . We can use the brute force approach and check if each element has a pair and the one that doesn't is the unpaired. However a more efficient operation is to use the exclusive or operator.
Say we have the 3 elements 1 3 ad 1 .
001
011
------
0 1 0
0 0 1
-------
0 1 1
We get 3 as the result. Implement both the brute force and the exclusive or approach.
#include <iostream>using namespace std ;int findUnpairedNumber( int array1[] , int size ){ //Use 2 nested loops. Brute force return ( -1 ) ;}int findUnpairedNumberEfficient( int array1[] , int size ){ //Use exclusive or ^ traverse through the array}int main(){ int array1[] = {1, 2, 3, 2 , 1 } ; cout << findUnpairedNumber( array1 , 5 ) << endl ; cout << findUnpairedNumberEfficient( array1 , 5 ) << endl ;}
Sparse Matrix
Sometimes a 2 dimensional array does not contain a lot of elements and it is better to store the elements in another way.
File: "sparse1.cpp"
#include<iostream>using namespace std;int main(){ // sparse matrix of class 5x6 with 6 non-zero values int sparseMatrix[5][6] = { {0 , 0 , 0 , 0 , 9, 0 }, {0 , 8 , 0 , 0 , 0, 0 }, {4 , 0 , 0 , 2 , 0, 0 }, {0 , 0 , 0 , 0 , 0, 5 }, {0 , 0 , 2 , 0 , 0, 0 } }; // Finding total non-zero values in the sparse matrix int size = 0; for (int row = 0; row < 5; row++) for (int column = 0; column < 6; column++) if (sparseMatrix[row][column] != 0) size++; cout << "size:" << size << endl ; // Defining result Matrix int resultMatrix[6][3]; // Generating result matrix int k = 0; for (int row = 0; row < 5; row++) for (int column = 0; column < 6; column++) if (sparseMatrix[row][column] != 0) { resultMatrix[k][0] = row; resultMatrix[k][1] = column; resultMatrix[k][2] = sparseMatrix[row][column] ; /* cout <<"--"<< row << " " << column << " " << sparseMatrix[row][column] << endl ; cout << resultMatrix[0][k] << " " << resultMatrix[1][k] << " " << resultMatrix[2][k] << endl ; */ k++; } // Displaying result matrix cout<<"Triplet Representation : size:"<< size << endl; for (int row=0; row<size; row++) { for (int column = 0; column<3; column++) cout<<resultMatrix[row][column]<<" "; cout<<endl; } return 0;}
$ g++ sparse1.cpp ; ./a.exe
size:6
Triplet Representation : size:6
0 4 9
1 1 8
2 0 4
2 3 2
3 5 5
4 2 2
Searching for a substring.
The brute force approach involves looking at each position and checking if the substring is there.
File: "str1.cpp"
#include <bits/stdc++.h>using namespace std;int isSubstring(string s1, string s2){ int M = s1.length(); int N = s2.length(); for (int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (s2[i + j] != s1[j]) break; if (j == M) return i; } return -1;}int main(){ string s1 = "for"; string s2 = "foodfor"; int res = isSubstring(s1, s2); if (res == -1) cout << "Not present"; else cout << "Present at index " << res; return 0;}