Apna College - Array Data Structure - Part1 ｜ DSA Series by Shrad..
Category
📚
LearningTranscript
00:00Hi everyone and welcome to the complete DSA series in which we are going to do our next
00:09chapter which will be regarding Arrays.
00:11Now in DSA concepts if you want to read any other topic then it will be available in this
00:16playlist on this channel.
00:18We can also read from here if we want.
00:25Now when we talk about Arrays, it is basically the first data structure that we are going
00:31to study.
00:32So when we are going to study Data Structures and Algorithms, so first of all let us understand
00:36what exactly are Data Structures and Algorithms.
00:39So when we talk about Data Structures, Data Structures are basically structures in our
00:44code when we are programming which are used to store data.
00:49The coding, programming that we are learning, there is only one motive behind it that we
00:53will be able to build real-life systems one day and whenever we talk about real-life systems
00:58like our websites, our apps, our softwares, every system is run on data.
01:05Data is the fuel for development, for coding, for programming.
01:09So we should know how to handle data.
01:11So basically while programming in coding, while writing C++ code, if we have to store
01:17a lot of information in some way then we store it in the form of different data structures
01:23and this data can be of different categories.
01:26Some data can be linear which can be imagined in the form of a single line.
01:32Some data can be hierarchical, hierarchical means that hierarchy is formed in that data.
01:39So we store different types of data in different data structures.
01:43So slowly throughout the series we are going to discover a lot of different types of data
01:48and also different types of data structures.
01:50Along with this, there is one more word that I will get to hear again and again which is algorithms.
01:55Algorithms are basically ways of performing operations on data, efficient operations.
02:01For example, if we want to find out data from a data structure, want to search data in it,
02:08then the process of searching can be called an algorithm.
02:11If we want to sort that data, that is, if we want to arrange it in ascending or descending order,
02:16then we will have different algorithms for that.
02:18So in the same way, the different operations that we perform on data,
02:22we call these operations our algorithms.
02:24And throughout this series, we are going to study a lot of different data structures and algorithms.
02:29So first of all, let's talk about what an array is.
02:33Whenever we have to store marks of 5 students in the code,
02:38then how will we store these marks with the existing C++ knowledge?
02:42Obviously, we will create some variables.
02:44For example, this will be our marks1 variable.
02:46This will be our marks2 variable.
02:48This will be our marks3 variable.
02:50And similarly, we are going to create 5 different variables that are going to store marks of 5 students.
02:58But in the future, the situation may also come that there are not 5 students in our class,
03:02but there are 100 students in our class.
03:04So to store the marks of 100 students, we are going to create 100 different variables.
03:09Now, let's create these 100 different variables, but there are two problems in this.
03:13First of all, it's going to be very hectic for a programmer to create 100 different variables.
03:17And secondly, it's going to be very difficult to track 100 different variables in a code.
03:22And that is why, and this number does not stop at just 100.
03:25For example, we are building Instagram.
03:27Now, we have millions of users in Instagram.
03:30So will we store the data of each user under a separate variable?
03:33Not at all.
03:34So to solve this problem, we have an array data structure.
03:38Array says that we can build a structure like this.
03:42Arrays are visualized in such a way that we can build a structure like this,
03:46which we imagine like a block of data.
03:49And inside each structure, there is some information that we can store.
03:55And we name this whole structure as Array.
03:59And this whole structure has a single name, which is a single variable that we need to track.
04:04Now here, because I had to store the marks of 5 students, what did I do?
04:07I built a structure of 5 sizes.
04:09But tomorrow I have to store the marks of 100 students, so I don't have to do anything.
04:13I just have to build a big structure.
04:16But we will not give the name of different variables to this whole structure.
04:19There will be only one name of this whole structure, which I need to track.
04:23So arrays solve the problem of multiple variables.
04:27Now whenever we talk about arrays, there are some specific properties that come with arrays.
04:32First of all, we can store the same type of data inside an array.
04:36If we want to store an integer inside this block of code,
04:39then we will store an integer value inside every single block of code.
04:43Additionally, arrays are contiguous in memory.
04:48We will understand this more if we read the chapter on pointers.
04:52But basically, when arrays are created in memory,
04:55then all the data is stored together.
04:59Plus, arrays are also linear.
05:02Linear means, we can imagine an array as a straight line structure,
05:05which arranges the data one by one.
05:09Now let's suppose I have to store the marks of 5 students.
05:12So I can create an array for myself, which I will call marks.
05:17I don't have to make a variable like marks1, marks2, marks3.
05:21As soon as I create an array called marks,
05:24the syntax to create it is, I will write integer marks of size 5.
05:32This is all I have to write to create an array.
05:35First of all, I have to tell what type of data each block of the array will store.
05:40So we wrote integer value in it.
05:42After that, we have to tell the name of our variable, which is going to be marks.
05:45We will call the entire array as marks.
05:48After that, inside the square brackets, I need to convey the size of my array.
05:52So we are telling the size of all the blocks and variables inside the array.
05:58It's very similar to creating a normal variable.
06:01If I have to make an integer variable, I will write marks1.
06:04Instead of single marks1, I have to tell the size of the total number of blocks.
06:10And each block occupies the same memory as an integer.
06:16One int can be stored inside this, one int can be stored inside this, one int can be stored inside this.
06:22So the entire array stores the same type of data.
06:25Plus, what does it mean to be contiguous in memory?
06:28Contiguous in memory means, let's suppose the address of this block is 100.
06:32If we are looking at the form of 100 bytes, then I know that if this block of code starts from 100,
06:38if this block starts from 100, then this block will take 4 bytes of memory.
06:42So the next block of code will start from 104.
06:45Then it will take 4 bytes of memory again.
06:47Then the next block of code will start from 108.
06:50This will take 4 bytes of memory.
06:52And this will start from 112.
06:54And similarly, this block is going to start from 160.
06:57So in this way, the data is stored inside the memory in a continuous manner.
07:02It's not that the data is scattered.
07:03Data is stored in a contiguous manner in the same way.
07:06Contiguous means continuous manner.
07:08And this is linear because we have imagined our data in a straight line.
07:11So let's create an array inside our code.
07:14To create an array, we have to tell the type of the array.
07:17Then we need to convey the array name marks.
07:19And we want to store marks of 5 students in this.
07:22If tomorrow we want to store marks of 100 students,
07:25then we can simply replace this 5 with 100.
07:28If we want to make a double array, let's suppose we have 100 items or we have 65 items,
07:34then we can store the price of each item.
07:37So in this way, we need to create a price array whose size is going to be equal to 65.
07:42Now there are multiple ways to create an array.
07:44The first way is this, in which we have only told the size of the array.
07:48So this type of array would have been created inside the memory.
07:50But there are no elements inside that array.
07:52If we want to define such an array,
07:54from which we can initialize with some values,
07:57then how will we define it?
07:59To define it, we can simply write in our code,
08:04And in this way, we can assign our 5 values inside the curly braces.
08:10So let's suppose the marks of the first student are 99, then 100, 54, 36, and 88.
08:17So in this way, we have stored the marks of 5 students.
08:20So inside each box, 99 will be stored here, 100 will be stored here, 54, 36, and 88.
08:27So this type of array would have been created inside our memory.
08:30Also, when we initialize an array with some data,
08:33and we want the size of the array to be equal to the size of the data,
08:36then we can skip the size from the left side.
08:40Let's suppose I have created an array with a price,
08:42and inside the price, I have to store the price of only 3 items.
08:45One is 98.99, one is 105.67, let's make it of type double,
08:53and one is 30.00.
08:57So in this way, as soon as we store 3 items,
09:01automatically our price array has been created of 3 sizes inside the memory.
09:05But when we initialize an array in this way, it is not necessary.
09:09If I write 50 here, then the array created inside the memory will be of 50 size.
09:14We have already defined the initial 5 values.
09:17So if we want, we can give a size,
09:20or if the size is equivalent to the data on the right side, then we don't really need to give a size.
09:24So in this way, we create our array and we can initialize it with data.
09:29Now whenever we want to access the data of the array,
09:32access means whenever we want to change the data of the array in any place,
09:37in any box, we want to print the data,
09:40then for that we use something called array index.
09:45Index means position.
09:47Every box inside the array has an assigned fixed position.
09:51The positions of the array start from 0.
09:54This box is at 0th position.
09:56This box is at 1st position.
09:58This is at 2nd position.
09:59This is at 3rd position.
10:00This is at 4th position.
10:01And from here, we will understand the logic that when we practiced for loop,
10:04we were starting our loops from 0.
10:07Because the data structures like array, which we will read as a string later,
10:10their position or index starts from 0.
10:13So if we want to put a loop on these data structures,
10:16then we need to start that loop from this index value 0.
10:19So it becomes a simpler loop.
10:21So if we write marks at index 0,
10:26we put a square bracket like this and write an index value inside,
10:29then we are talking about this position.
10:32If we write marks at index 3,
10:35then we are talking about this position.
10:38The index of the array always goes from 0 to size-1.
10:43So the size of this array is equal to 5.
10:45And the last index will be equal to 4 i.e. size-1.
10:48So let's use the index once in the code.
10:51In our marks array, we have created this marks array,
10:54in which we have 5 different marks.
10:56If we want, we can see out the marks of any position.
10:59Let's suppose we have seen out the marks of 0th position.
11:02And let's also give an end line here.
11:05Along with that, if we want, we can print the marks of all positions
11:09by accessing different index values.
11:13So we have printed here.
11:15So we have printed all the marks.
11:17And this marks bracket index,
11:20we can treat it as a single variable.
11:23Let's suppose if I want to change the value,
11:26instead of 99, we will print 101.
11:29So that is also possible.
11:32So when we print the marks, we will get 101.
11:35Now we know that the valid index for an array
11:38always goes from 0 to size-1.
11:41So if we try to print the value outside the size,
11:44let's suppose on the 5th index,
11:46in that case, we will get a warning.
11:49Warning is that array index 5 is past the end of the array.
11:52End of the array is at size-1.
11:54But you are trying to print the value of size, which does not exist.
11:58Or if I write minus 1 here, which is smaller than 0,
12:01in that case, we are going to get the same error.
12:04Array index minus 1 is before the beginning of the array.
12:07So in this way, we always have to access the values of the array within the limit.
12:11If we write invalid index, we can get garbage values.
12:14Next, we are going to learn how to run a loop on an array.
12:18Now when we run a loop on an array,
12:21for example, here we printed the elements
12:24by writing 5 cout statements.
12:26But generally, if the size of the array is 100,
12:28then we will not write 100 cout statements.
12:30So generally, to perform operations on an array,
12:33we use loops.
12:35And how do we use loops?
12:37We run a loop that goes from index 0 to index size-1.
12:42So for the loop from 0 to size-1, we need this size.
12:46So the size of the array is generally already given in a variable called size.
12:50Or we can also calculate it.
12:53How do we calculate it?
12:55Let's suppose I want to calculate my size.
12:57So we do it by writing sizeof.
13:00So from this, we will get the size of the array.
13:03What happens with sizeof?
13:05If we have this array,
13:07then we will get the total size of how many bytes of memory this array occupies.
13:12For example,
13:14in this array, one box occupies 4 bytes of memory.
13:17And we have 5 indices.
13:19So 4 into 5 occupies 20 bytes of memory.
13:24So the size of the array will print 20 bytes.
13:29We can also verify this.
13:31If we do cout,
13:33sizeof marks.
13:37In that case, we are going to get 20.
13:40So we get 20 here.
13:42Now this is the total size of the array.
13:44But we know that every index of an array has an integer of memory.
13:47So when we divide this value to size of int,
13:51we get the size of the array, which is equal to 5.
13:54So in this way, we write the name of any array and get its size.
13:57If we divide it by sizeof, we get the total size of the array.
14:01Generally, the size of an array is already given in another variable.
14:05But we can calculate it ourselves.
14:07Now we have to run a loop, which goes from 0 to size-1.
14:10So we can run a loop, which starts from 0.
14:13i is equal to 0.
14:14i goes to less than size.
14:16i++.
14:17This is a very simple loop.
14:19We have done many loops in the pattern.
14:21And every time we can cout the value of index number i in the marks.
14:28Index value will be 0, then 1, then 2, then 3.
14:31In this way, marks of 0, marks of 1, marks of 2 will be printed.
14:35And if we try to print it, all the elements will be printed in this way.
14:39So we have output all the values from the loop.
14:42If we want, we can take all the values as input in the form of a loop.
14:46So let's suppose we didn't initialize our array.
14:49We just told that we have an array whose size is equal to 5.
14:52In fact, we can write the size above.
14:55And we can write the size variable here.
14:57Now to take all the values as input, we can run a similar loop.
15:02Which goes from i is equal to 0 to size.
15:05And here we can cout the marks of i.
15:08So marks of i, marks of index, is basically a variable.
15:12Which can be input, output, or changed.
15:15So the value of 5 marks that we enter, will be stored in our array.
15:20And that will be printed for us.
15:21So let's save it and run it.
15:24Let's suppose the value that we have entered is 12, 13, 14, 15, and 16.
15:30We have entered these 5 values.
15:32So we have printed these 5 values.
15:34So in this way, we can run a loop on an array.
15:37And we can perform our required operations on the index of each array.
15:44So let's use these loops and solve a small question based on arrays.
15:47We have to find out the smallest and the largest number in an array.
15:52For example, in the beginning, we will find out the smallest number.
15:56Let's suppose we have an array, which has 5, 15, 22, 1, minus 15, and 24.
16:08So in this way, we have different values and we have to find out the smallest value.
16:13To find out the smallest value, we know that we have to check every single value of the array.
16:20So to check every single value, let's run a loop.
16:23And where does that loop start?
16:25Array loops generally start from 0 and go to size-1.
16:28So first, we will go to this index and check what is the smallest value here.
16:32Next, we will check what is the smallest value here.
16:35We will go to the next index and keep checking the same thing until we reach the last index of the array.
16:40Now whenever we want to check the smallest value, we have to compare it with a value.
16:46So what we can do is, we can make a variable int smallest.
16:49And we can initialize this variable with plus infinity.
16:54Plus infinity means the largest possible value.
16:57If I initialize it with the largest possible integer value,
17:01then whenever any value compares with this value,
17:03for example, if we compare 5 and plus infinity,
17:06then what will be the smallest?
17:08Obviously, the smallest will be 5.
17:09So 5 will be the answer.
17:11Later, when we compare 1 with 5,
17:14here when 5 comes, we will compare 1 with 5.
17:17So what will 1 do again?
17:18If 1 is smaller than 5, then 1 will be the answer here.
17:21So this is how comparisons start whenever we have to find out the smallest value.
17:25We start comparisons with the largest possible number so that this number loses in every comparison.
17:31Because we never want this answer.
17:33We want another valid answer to come to us.
17:35So plus infinity in programming, in C++, we call it integer underscore max.
17:42We write this in capital in the uppercase.
17:45And this means plus infinity in C++.
17:48Plus infinity means the largest possible value for any integer number.
17:53We will call it plus infinity.
17:55So we started with int max.
17:57Now first of all, we will go to the first index.
17:59We will compare 5.
18:01Now when we compare 5 with plus infinity,
18:03obviously 5 will be smaller.
18:05And how will we know this?
18:07Either we can use an if-else.
18:09That is, if any of our numbers,
18:11let's call this array nums.
18:13If the value of nums of i,
18:15if the value of nums of i in any index becomes smaller than smallest,
18:20smallest means whatever our answer is,
18:22then what we will do is,
18:24we will update smallest to nums of i.
18:28I hope we understood this logic.
18:30As soon as we get a smaller value than plus infinity,
18:33then what will come in smallest?
18:35That small value will come in smallest.
18:37For example, here we will get 5.
18:39Now next time when we update,
18:41then 15 will be compared with this 5.
18:44Because in smallest, we have 5.
18:46And nums of i is 15.
18:48So if 15 is not less than 5,
18:50then we don't have to perform any operation.
18:52Now we will update our index again.
18:54We will compare 22 with 5.
18:56We don't have to perform any operation.
18:58When we compare 1 with 5,
19:001 is smaller than 5.
19:02So we will remove 5 and write 1 in answer.
19:04Because this condition will work.
19:06After that we will increase index to minus 15.
19:08Minus 15 is smaller than 1.
19:10So here we will get minus 15.
19:12Again we will increase index.
19:14Because we need to check till end.
19:16Because we don't know,
19:18what if last index is minus 24?
19:20Then this will be the answer.
19:22So we check till last index,
19:24when we have to find out smallest or largest.
19:26When we compare 24 with minus 15,
19:28then minus 15 is smaller.
19:30So it will remain same.
19:32And final answer will be in smallest variable.
19:34Which is going to be equal to minus 15.
19:36So let's convert this logic into code.
19:38First of all,
19:40let's create an array called nums.
19:42In nums,
19:44we have different numbers stored.
19:465, 15,
19:4822, 1, minus 15
19:50and 24.
19:52These numbers are stored.
19:54Let's write their size also.
19:56Size is going to be equal to 6.
19:58Now if we want to find smallest,
20:00then we will store it in some variable.
20:02So let's initialize smallest
20:04with int max.
20:06i.e. positive infinity.
20:08Now we will run a loop
20:10for integer i equals 0.
20:12i less than size i plus plus.
20:14Every time we will compare
20:16if value of nums of i is less than
20:18value of nums of i is less than smallest.
20:20If smallest is smaller than
20:22smallest, then no need to change.
20:24But if nums of i is less than smallest,
20:26then value of smallest will be updated
20:28to nums of i.
20:30And at last,
20:32after loop is over, we can print
20:34smallest
20:36is equal to
20:38smallest value
20:40end of line.
20:42If we run this, we will get
20:44answer as minus 15.
20:46If we had minus 24 instead of minus 15,
20:48then our answer would have been minus 24.
20:50So this is how we calculate
20:52the smallest value with the help
20:54of a loop inside an array.
20:56And not only smallest, if we want
20:58largest, sum of all values, product of
21:00all values, basically any such
21:02operation in which it is required
21:04to go to every index and
21:06compute that thing.
21:08For that, we can use our loops in this way.
21:10Also, one more thing
21:12which I would like to teach you here,
21:14that is the min function.
21:16Basically, we have two functions in C++
21:18min and max. Whenever we have to
21:20find out minimum of two numbers,
21:22for that, we can use min.
21:24For example, I want to know
21:26which is the smallest value
21:28from nums of i and smallest.
21:30For that, I will take
21:32min function. This is implicit function.
21:34It is already available with us.
21:36Its logic is already written.
21:38This is min function in which we pass two arguments
21:40nums of i and smallest.
21:42And it will return us the value which is
21:44small. And whatever small value it is,
21:46we can write it in smallest.
21:48So, the whole if which we have written,
21:50the shorter way to write it is
21:52a single statement in which
21:54we can use min function.
21:56And it will return us minimum of these two values
21:58which we will store in smallest.
22:00So, this is also
22:02the way.
22:04It will return us the same answer.
22:06So, this was the logic for finding
22:08the smallest value. If we want to find
22:10the largest value, then we have to reverse everything.
22:12Basically, this time we will take
22:14integer largest.
22:18As we initialized smallest with
22:20plus infinity.
22:22This time, we will initialize
22:24our largest with
22:26minus infinity.
22:28Because we want
22:30largest to win with any number.
22:32So, we will make the largest
22:34the smallest possible value
22:36so that it never wins
22:38when there are comparisons.
22:40And minus infinity is
22:42min in C++.
22:44So, here we are going to
22:46write int min.
22:48Now, we will do comparisons of int min.
22:50So, here when we are doing comparisons
22:52in for loop, we can find largest with smallest
22:54as max of
22:56nums of i and
22:58largest.
23:00And lastly, we can
23:02print smallest and largest.
23:04So, basically, to find largest
23:06I don't have to put any separate loop.
23:08I can find both values in single loop.
23:10Because, eventually
23:12whether we have to find smallest or largest,
23:14we are finding on each index.
23:16So, for this
23:18particular array, smallest value
23:20is minus 24 and largest value is
23:2222. So, in this way,
23:24we can find smallest and largest values.
23:26After pausing here,
23:28you have to solve a homework problem.
23:30Basically, what you have to do is
23:32you have to find smallest
23:34and largest values
23:36on the index
23:38which are stored on index.
23:40You have to print that index.
23:42So, this is one thing that you have to do.
23:44This time, not the value.
23:46For example, if minus 15 is smallest,
23:48then I need index of minus 15 which is
23:50equal to 4. So, I have to print 4.
23:52I don't have to print minus 15.
23:54How will we print this?
23:56How will we initialize values for it?
23:58What will be the comparisons?
24:00You have to think about it yourself.
24:02So, this thing I am giving you as a homework problem.
24:04Next thing which we are going to study is
24:06pass-by-reference.
24:08We have already seen pass-by-value.
24:10In functions chapter, we have studied pass-by-value.
24:12Pass-by-value means
24:14the variables of primitive data types.
24:16If we pass a function like an argument,
24:18let's suppose this is my main function
24:20in which I have made a variable x
24:22in which value is stored as 10.
24:24If main function is calling
24:26another function which is change x,
24:28then in that,
24:30another copy of this x is going to be made
24:32which I highlight with different color.
24:34And in that, this same value
24:36is going to be copied.
24:38Now, if we change something here
24:40instead of 10, if we change it to 15,
24:42then that change will not reflect in main function.
24:44This was pass-by-value.
24:46Now, we are going to study opposite of this
24:48which is pass-by-reference.
24:50Reference means address.
24:52And addresses,
24:54the whole concept of reference,
24:56we will understand in detail in chapter on pointers.
24:58So, when we talk about pass-by-reference,
25:00what do we exactly do?
25:02What do we do in pass-by-reference?
25:04In pass-by-reference,
25:06the whole data structure
25:08is used for non-primitive data types.
25:10For example, array.
25:12Array is a non-primitive data type.
25:14Primitive means simple.
25:16Arrays are not that simple in memory.
25:18So, we call them non-primitive.
25:20So, whenever we do pass-by-reference,
25:22we pass the address of our whole data structure
25:24to any function.
25:26And whenever you have any address
25:28in programming,
25:30you can change it
25:32in the same original copy.
25:34For example,
25:36whenever we pass an array to any function,
25:38the array will always be pass-by-reference.
25:40Implicitly. Automatically.
25:42For example,
25:44let's take an example of a simple array.
25:46We have an integer array
25:48of size 3, which has values
25:501, 2, 3.
25:52Now, if we create a function,
25:54let's call it void
25:56changeArray.
25:58In this function, we will have an integer array
26:00and its size.
26:02And in this function,
26:04from i equals 0 to
26:06i less than size, i plus plus,
26:08we will double the value of each index
26:10of our array.
26:12We will make it 2 into array of i.
26:14So, from here,
26:16we will call the function
26:18changeArray,
26:20in which
26:22we will pass the array
26:24and pass the size as 3.
26:26Now, we will run a loop
26:28to print the values of the array.
26:30Here, we will make it
26:32cout
26:34in main.
26:38And here, we will make it cout
26:40in function.
26:42Here, the size will be equal to 3.
26:44And here,
26:46we will make it cout
26:48array of
26:50i
26:52end of line.
26:54When we run this code,
26:56we will see an interesting thing.
26:58The original elements of the array
27:00were 1, 2, 3. Then, changeArray
27:02was called. ChangeArray doubled
27:04each element. Now, in this function,
27:06the values will be doubled. But,
27:08when we come back to the main function,
27:10what would have happened if it was a pass-by value?
27:12Our original values would have been 1, 2, 3.
27:14But, here, the values have been updated
27:16to 4 and 6. That means,
27:18the change that happened in the array,
27:20is reflected in the main function.
27:22And, this is called
27:24pass-by reference. Because,
27:26internally,
27:28when we created an array,
27:30when we created an array
27:32in the memory,
27:34a 3-size array was created
27:36in which 1, 2, 3 were stored.
27:38Now, let's suppose
27:40the address of this array is 100,
27:42104, 108.
27:44So, the interesting thing
27:46in C++ is that
27:48the name of the array
27:50is implicitly
27:52a pointer. We will learn
27:54what a pointer is later. But,
27:56basically, a pointer is
27:58something that stores the address.
28:00Address means the array.
28:02The name of my array is
28:04basically storing this 100 value.
28:06It stores
28:08the starting address of the entire array.
28:10And, whenever you get
28:12the starting address, if you get 100,
28:14and you know that it is an integer array,
28:16you will add 4 to it and get
28:18the next index.
28:20If you add 4 to it, you will get 108.
28:22If you add 4 to it, you will get 112.
28:24So, whenever
28:26we get the starting index of the array,
28:28we can traverse the entire array
28:30if we get the type of the array
28:32and the size of the array.
28:34So, who stores the starting address here?
28:36It stores the name of the array.
28:38It stores the variable of the array.
28:40So, whenever in a function,
28:42let's suppose we created an array in the main function.
28:44Now, if this main function
28:46calls another function,
28:48let's suppose it calls the change array.
28:50So, in the change array,
28:52the entire copy will not be created again.
28:54It will be changed by value.
28:56In the case of array,
28:58the starting address of the array
29:00is stored here.
29:02In this new array,
29:04the starting address is 100.
29:06So, whenever we are changing
29:08something in the change array function,
29:10we will go to this address and change it.
29:12So, where is this address?
29:14It takes us back to the original array.
29:16So, pass-by-reference means
29:18we are sending a reference.
29:20We are sending the address,
29:22which is the starting address of this array.
29:24So, when we go to this address and
29:26replace 1 with 2,
29:28it will reflect in the original.
29:30It will reflect in the original here
29:32and here also.
29:34So, all the changes are reflected
29:36in the original array because
29:38no copy is created like pass-by-value.
29:40So, in C++,
29:42reference means address
29:44and pass-by-reference means
29:46we are making all the changes
29:48in the original.
29:50So, whenever we pass an array to a function,
29:52we have to pass it carefully
29:54because if that function has made any changes,
29:56it will reflect in the main function
29:58or calling function.
30:00So, I hope you understood the concept of pass-by-reference.
30:02We will study pass-by-reference,
30:04addresses and pointers in more detail
30:06in the chapter on pointers.
30:08The next concept we will discuss
30:10is called linear search.
30:12Linear search is
30:14a fixed algorithm.
30:16The method of doing linear search
30:18is also fixed.
30:20For example, we have this array.
30:22Let's visualize this array.
30:24This array will look like this in memory.
30:26We have different elements
30:288, 1,
30:302 and 5.
30:32So, we have different elements
30:34and here
30:36our array is starting.
30:38Let's write the index values
30:400, 1, 2, 3, 4, 5 and 6.
30:42So, the size of the array is
30:44equal to 7.
30:46If we are given an array like this
30:48with a target
30:50that I have to search this target value
30:52in this array and
30:54I have to return the value on the index.
30:56This is a simple problem
30:58that we are given.
31:00There are multiple ways to solve this problem.
31:02Basically, we have to
31:04perform a search operation
31:06on the index.
31:08If we get the value
31:10then we have to return the index.
31:12Let's suppose
31:148 is replaced by 80.
31:1680 does not exist in this array.
31:18In that case, we want to return minus 1.
31:20Returning minus 1 means
31:22invalid index because
31:24minus 1 is not an index.
31:26If we return from 0 to 6,
31:28then minus 1 means invalid index.
31:30It could be minus 2 or minus 5.
31:32If we get the value,
31:34we have to return the index or
31:36return minus 1.
31:38Basically, we have to search
31:40the target value in the entire array.
31:42There are multiple ways to search.
31:44One of them
31:46is called
31:48Linear Search Algorithm.
31:50It is very simple.
31:52Linear Search Algorithm says
31:54to apply a loop
31:56on the index
31:58and check
32:00whether the target exists
32:02or not.
32:04On the next index, check
32:06whether the target exists
32:08or not.
32:10As soon as the target exists,
32:12we get 8.
32:14We got 8.
32:16Now, we have to return the value
32:18of the index.
32:20If the index is on 3, then we return the value of 3.
32:22Let's suppose we have to search 80.
32:2480 does not exist in this array.
32:26It does not exist in the entire array.
32:28As soon as we reach the last index,
32:30we get to know that
32:32it does not exist.
32:34In that case, we have to return
32:36minus 1.
32:38What will be the overall flow?
32:40What will be the logic
32:42to perform Linear Search?
32:44It will be a very simple logic.
32:46In fact, Linear Search
32:48is one of the most simple
32:50and easiest algorithm
32:52for programming.
32:54We have to run a loop
32:56for integer i equals 0,
32:58i less than size, i plus plus.
33:00We have to run a loop.
33:02Every time, I have to check
33:04whether my target exists
33:06in the array of i.
33:08To check, we have to write
33:10if my array of i
33:12equals my target.
33:14If the value
33:16is true, then I got the match.
33:18Then, I have to simply
33:20return the value of the index.
33:22For example, if I am on this index,
33:24the target matches here.
33:26Then, I have to return value 3.
33:28What is the index?
33:30It is equal to i.
33:32We can make a function
33:34whose return type is integer
33:36in which we are trying to perform Linear Search.
33:38That is why I am using the
33:40return i statement.
33:42If you are doing it in the main function,
33:44you can simply break it.
33:46You can take an extra variable
33:48and store i in that answer.
33:50I am going to use function
33:52because it is going to be simpler.
33:54If it does not match,
33:56then we do not have to do anything.
33:58We have to move forward.
34:00The loop will automatically increase.
34:02We do not have to write any other code.
34:04If we move forward
34:06and reach the last index
34:08and still, I did not get my target 80.
34:10In that case, I know
34:12that I have to return minus 1.
34:14We simply return
34:16minus 1 in the last.
34:18We will reach the last
34:20when there is no i return.
34:22Only then we will be able to reach the statement.
34:24I told you in the functions
34:26that there is no execution after the return statement.
34:28As soon as the return i
34:30is there, the loop will stop.
34:32We will never reach the statement.
34:34If the return i is there,
34:36the answer is returned.
34:38If the return i is not there,
34:40we return minus 1 in the last.
34:42Let us convert the entire logic
34:44into the code of Linear Search.
34:46For the code of Linear Search,
34:48we are going to write a function
34:50called
34:52Integer
34:54Linear
34:56Search.
34:58In Linear Search, we are going to get an array
35:00plus the size of that array.
35:02We can create
35:04our array here.
35:06Integer array is going to be equal to
35:084, 2, 7,
35:108,
35:121, 2, 5
35:14and its size
35:16is going to be equal to 2.
35:18From here, we are going to call
35:20Linear Search Algorithm.
35:22We are going to pass the array and its size.
35:24For this algorithm,
35:26we are going to run a loop.
35:28For Integer i equals 0,
35:30i less than size,
35:32i plus plus.
35:34Whenever the value of the array of i
35:36is equal to the value of the target.
35:38For Linear Search, we have to send the target as well.
35:40Let us create
35:42an Integer target
35:44which is going to be equal to 8.
35:46Here, we have another parameter
35:48which is Target. If the value of the array of i
35:50is equal to the value of the target,
35:52we have found the value
35:54and from here, we are going to return
35:56the index which is equal to i.
35:58But the entire loop is running
36:00and still we did not get the value.
36:02In that case, we are going to return minus 1.
36:04Minus 1 indicates that we have not found
36:06the value. So, whichever answer
36:08is returned, when we call
36:10Linear Search, we can get it
36:12cout directly.
36:14Also, let us update the size to 7.
36:16Because size will not be 2,
36:18size is equal to 7. Now, when we
36:20run it, we will get the index
36:22which is equal to 3. Similarly, let us
36:24suppose we want to search for this 5.
36:26When we search for 5,
36:28let us make the target 5.
36:30In that case, we are going to get index 6
36:32which is the last index of this array.
36:34If we try to search for 50,
36:36in this case, we will get minus 1
36:38because 50 does not exist
36:40in the array. So, in this way,
36:42our Linear Search algorithm works.
36:44The basic concept of Linear Search is
36:46that we have to go to every index and
36:48try to search our target.
36:50So, on this logic, our algorithm
36:52works. Also, the students
36:54were already familiar with the concept of
36:56Time Complexity. If you already
36:58know about Time Complexity,
37:00if you do not know, then we will study it later.
37:02But the students who have already done it,
37:04the Time Complexity of Linear Search algorithm is
37:06equal to O of n. And
37:08it is called Linear Search because
37:10its Time Complexity is linear.
37:12O of n is called Linear Time Complexity.
37:14That is why it is called Linear Search.
37:16As we have Linear Search,
37:18later on, we will study another
37:20way of searching in an array
37:22which is called Binary Search.
37:24The Time Complexity of Binary Search is
37:26equal to O of n. But,
37:28these are complex things which we do not
37:30have to pay much attention to.
37:32Later on, we will study Binary Search in detail.
37:34So, this was all about
37:36Linear Search. Next, we are going to talk
37:38about how to reverse an array.
37:40So, we have been given this array and
37:42we have to reverse all the elements of this array.
37:44That means, the final
37:46array should have all the
37:48elements in reverse order
37:50like this.
37:52So, if the elements were
37:544, 2, 7, 8, 1, 2, 5, 4,
37:56now they will be in reverse order
37:584, 2, 7, 8, 1, 2, 5, 4.
38:00For this change, we do not have to make a copy
38:02of the second array. We have to
38:04change it in the original array.
38:06That means, the elements of the original array
38:08should be in reverse order like this.
38:10So, how will we
38:12solve this problem?
38:14Before solving,
38:16let us visualize
38:18all the elements of our array
38:20in the form
38:22of our array structure.
38:24So, this is the array in which
38:26I have to reverse all the elements.
38:28There are many different ways of reversing.
38:30We are going to use
38:32something called Two Pointer Approach.
38:34Two Pointer Approach
38:36is not something that
38:38we will use only for this question.
38:40Two Pointer Approach is a very important approach.
38:42We can think of it as an algorithm.
38:44We will use it in the coming chapters.
38:46In fact, the logic that we will use
38:48to solve this question is a very important logic.
38:50With the same logic,
38:52we will solve many questions of strings
38:54when we will read the chapter on strings.
38:56In many algorithms,
38:58the same logic is applied.
39:00In fact, almost the same logic
39:02applies to the recursion algorithm.
39:04Now, we want our array to reverse.
39:06In the reverse array,
39:08the starting element
39:10should be at the last position
39:12and the last position element
39:14at the starting position.
39:16Going in this direction,
39:18the next position element
39:20should be at the second last position
39:22and the third element
39:24at number 2nd should be
39:26at the third last position
39:28and the last position element
39:30so why don't we swap the first and last elements
39:37swap means to swap the elements from each other
39:41swap means here we have 5 and instead of 5 we have 4
39:46so this is called swapping
39:47and to swap two values we have a swap function in C++
39:52in which first we pass our value 1 and then our value 2
39:56so these two values change from each other
39:59so why don't we swap the first and last value
40:03after that we will swap the second and second last value
40:08so here we will have 2 and here also we will have 2
40:12then we will swap the third and third last value
40:16so here we will have 1 and here we will have 7
40:19and then we will come here similarly we will come here
40:22now here because there is only one value so we don't need to swap it
40:26and if we want to swap then we will write 8 instead of 8
40:30so this will be our final state after swapping the pairs
40:34in which if we notice then our entire array is reversed
40:385 2 1 8 7 2 4 similarly 5 2 1 8 7 2 4
40:43so basically what we have to do, what is our overall approach
40:45how will we solve this problem
40:47we will start from two positions
40:49one position is going to be our starting position
40:52one position is going to be our ending position
40:54I have to increase this start from 1 again and again
40:57then it will become second, then it will come on third position
41:00then it will come on fourth position
41:02or we can say that this start
41:05we will start it from 0
41:07this is basically starting index
41:09which will start from 0
41:11after that this starting index will be updated to 1
41:14after that this starting index will be updated to 2
41:18so what can start be?
41:19start can be a variable
41:21I have called this variable as a pointer
41:24so we will start the value of start from 0
41:27because this is a variable which will start from 0 and will increase
41:31similarly this last variable we will call it as end
41:35start and end basically we will use to track the positions
41:39and the value of my ending variable will keep on decreasing
41:43in last what is the ending value?
41:45this is index 0 1 2 3 4 5 and 6
41:48so ending value is 6
41:49after that in next iteration
41:51ending value will be 5
41:53after that in next iteration
41:55ending value will be 4
41:57so my end is basically
41:59starting from my size minus 1
42:01means from last index
42:03every time I have to do start as plus plus
42:05and what I have to do for end?
42:07I have to do end as minus minus
42:09only then start will move forward and end will move backward
42:12so if I have a start and I have an end
42:15so what I have to do?
42:16I have to swap the values of both
42:18I have to swap again and again
42:20my array of start
42:22with array of end
42:25this is my operation which I want to perform again and again
42:28swapping values at two different positions
42:31this is called two pointer approach
42:34two pointer means start and end
42:36we are taking two pointers
42:37one we are moving forward
42:38second we are moving backward
42:39and then we are doing some work
42:41what are we doing?
42:42we are doing work of swapping values
42:44but till when we have to do this work?
42:46till when we have to keep on swapping values?
42:47we have seen that
42:48when our start will move forward
42:50when our end will move backward
42:52so there will be a point
42:53when start and end will be at same position
42:56means
42:57let's take an example of even array
42:59example of even size array
43:01let's take an example of odd size array
43:03let's suppose I have an array
43:05which has 4 values
43:07I have an array which has 3 values
43:11here this is my start
43:13this is my end
43:15what will happen in next iteration?
43:17start will be here
43:18end will be here
43:19what will happen in next iteration?
43:21start will be here
43:23and end will be here
43:25so basically in next iteration
43:27start will move forward than end
43:30this is one case
43:31second case may be
43:33this is my start
43:34this is my end
43:35in next iteration
43:37start will be here
43:38end will be here
43:39so in case of odd size array
43:41I have to stop swapping value
43:43start equal to my end and in even case, I have to stop my swapping when my start is greater than my end.
43:51If start is greater than end, then I don't need to reverse because if end is here, start is here and I reverse them.
43:58If my start comes here, if my end comes here and I swap 1 and 7, then we will go back to the original array.
44:05So we have to swap until these two conditions become true.
44:10So what will be the reverse of these two conditions?
44:12If we mix these two conditions, then it is basically start greater than equal to end.
44:16When start is greater than equal to end, then we have to stop.
44:19So how long should the loop run?
44:21The loop should run until my start is less than my end.
44:28Our loop will run only until the value of start is less than end.
44:33Otherwise, the values will not reset to original again.
44:36So this is our overall approach to reverse an array.
44:40In fact, we can also do dry run on an array.
44:43If we take an array with some elements like 1, 2, 3 and 4.
44:49Now from here, we started our start with value 0.
44:52From here, we started our end with value equal to 3.
44:56So these are our starting values.
44:57Now we will check whether our start is less than end.
45:00Is this start less than end?
45:02Definitely, it is.
45:03So I have to swap the values of both.
45:05So at start, the value was 1.
45:07Now at end, it will be 1.
45:09At start, it will be 4.
45:11After that, I have to do plus plus for start and minus minus for end.
45:16So we can do the same thing in the loop.
45:18We will do plus plus for start and minus minus for end.
45:24If we do plus plus for start, then the value of start will be updated.
45:28It will be 1 instead of 0.
45:30So we will remove 0 and make it 1.
45:33If we do minus minus for end, then the value of end will be updated.
45:36It will be 2 instead of 3.
45:38Now we will check again in the loop whether start is less than end.
45:42Start is less than end.
45:44So we will swap the values again.
45:46This time, we swapped the values.
45:48So here, it will be 3 instead of 2.
45:50Here, it will be 2 instead of 3.
45:52After that, I have to do plus plus for start and minus minus for end.
45:54As soon as start is plus plus, start will be here.
45:58As soon as end is minus minus, end will be here.
46:02So let's update the value of start and make it 2.
46:06So this will be my start, which will come on this index.
46:09And my end will come on this index,
46:11where its value will be updated and become equal to 1.
46:14So start was 1 before,
46:16it became 2 after increasing.
46:17End was 2 before,
46:18it became 1 after decreasing.
46:19Now we will check again in the loop whether start is less than end.
46:22Start is not less than end now.
46:24That means I don't have to perform any operation now.
46:26Now we will get out of this loop.
46:28And at the end, when we see our values,
46:31We started with 1, 2, 3, 4.
46:33Now we have values 4, 3, 2, 1.
46:35So in this way, we can reverse any given array with this particular logic.
46:39And this logic is of our two-pointer approach,
46:41in which we use these two pointers.
46:43This logic is important
46:45because in the coming chapters,
46:47based on this same logic,
46:49we are going to solve many different algorithms
46:51and many different questions.
46:53So let's write our code for this logic.
46:55In the code, let's create a function
46:57void
47:00reverse
47:02array
47:04We are going to pass our array
47:06along with the size of the array.
47:12For two-pointer approach,
47:14we have to create a start.
47:16Start is going to be 0 and end is going to be size-1.
47:18We will run a loop
47:20until the value of start is less than size.
47:24Because we don't have to write equal to here.
47:26Whenever we write while loops,
47:29we should always know
47:31in which case we have to write less than
47:33and in which case we have to write less than equal to.
47:35Why we don't have to write equal to?
47:37Because start and end will be equal
47:39only in the case when the size of the array is odd.
47:41The odd size of the array means
47:43let's suppose I have three elements in my array.
47:45First, start will be here and end will be here.
47:47Next time, start will be here
47:49and end will also be here on this index.
47:51In this case, both will not be equal.
47:53In this case, we don't have to change anything.
47:55And when start is bigger than end,
47:58we don't have to change anything.
48:00So, the loop will run only until
48:02start is less than size.
48:04If we write equal to here,
48:06there will be no error as such.
48:08But we don't need it.
48:10What we have to do every time?
48:12We have to swap array of start
48:14with array of end.
48:18Here, start will be less than end
48:20and not less than size.
48:22And we will make start plus plus
48:24and end minus minus.
48:26So, this is our logic to reverse an array.
48:28When we call this function,
48:30let's call reverse array
48:32in which we will pass
48:34our array and the size.
48:38And then we are going to print
48:40the elements of our array.
48:42After calling the function,
48:44size i plus plus,
48:46cout, array of i
48:48with some space
48:50and let's put cout here
48:52end of line.
48:55So, this is our logic.
48:57And we will run it.
48:59So, the elements are in reverse order.
49:01This was our original array.
49:03Elements are in reverse order.
49:05Let's suppose we have values
49:071, 2, 3, 4 and 5.
49:09Size of array is equal to 5.
49:11So, this time, opposite of this,
49:135, 4, 3, 2, 1 will be printed.
49:15So, in this way, we can reverse any array.
49:17For students who have idea of time complexity,
49:19for this particular logic,
49:21the time complexity is also going to be linear
49:24which is O of N.
49:26So, finally, let's talk about the summary.
49:28In this chapter,
49:30we have only done the introduction of array.
49:32We have learned some basic things.
49:34In the coming chapters,
49:36we are going to solve many questions related to array.
49:38In fact, there are some questions
49:40which are not only related to arrays.
49:42In future, we will study the concept of hashing.
49:44So, when we will study hashing,
49:46then we will solve the questions related to arrays.
49:48In future, we will study dynamic programming
49:50then we will solve the questions related to arrays.
49:53So, the data structure of arrays is not necessary.
49:55It is only related to arrays.
49:57It can be related to any other data structure
49:59or any other algorithm.
50:01So, this is what we should know.
50:03So, in today's chapter,
50:05we have covered what is array?
50:07How can we create an array?
50:09How does the concept of index work in an array?
50:11How can we input and output an array?
50:13How can we run loops on an array?
50:15How can we find the minimum and maximum
50:17with the help of loop in an array?
50:19How can we find the minimum and maximum
50:21with the help of loop in an array?
50:23Also, we have covered linear search.
50:25How can we reverse the elements of an array?
50:27How can we reverse the elements of an array?
50:29These are all the important things
50:31which we should know.
50:33Now, whenever we go to any coding platform
50:35or generally whenever we have coding tests,
50:37online assessments, OAs for companies,
50:39then whenever there is a question related to array,
50:41then instead of array,
50:43generally in questions,
50:45we have to use vectors.
50:47Vectors are very similar to arrays.
50:49They work like an array.
50:51We use index in vectors also.
50:53They are almost created like an array.
50:55There is a small difference between array and vector.
50:57So, in coding platforms like LeetCode,
50:59Codeforces, Codeshift,
51:01to solve questions on them,
51:03we need vectors.
51:05Because in majority of the questions,
51:07vectors are used and arrays are not used.
51:09And that question is called an array question.
51:11But vectors are used in it.
51:13So, before solving questions on platforms,
51:15it is very important to learn vectors.
51:17So, in the next chapter,
51:19we will learn vectors.
51:21And after that, we will learn
51:23how to solve questions on different coding platforms
51:25using different data structures and algorithms.
51:27Also, at the end of this chapter,
51:29I would like to give you some homework problems.
51:31Write a function to calculate sum and product
51:33of all numbers in an array.
51:35This is going to be very simple.
51:37Write a function to swap
51:39the maximum and minimum number of an array.
51:41This is also going to be very simple.
51:43Write a function to print
51:45all the unique values in an array.
51:47To solve this question,
51:49you have to use
51:51a nested loop.
51:53So, this question might be
51:55difficult for you as a beginner.
51:57So, unique values means that
51:59if we are given an array 1, 2, 3,
52:011, 2, 3 and 4,
52:03then there is only unique value 4 in it
52:05which I have to print.
52:07Now, how will we check whether any value is unique or not?
52:09So, basically, if we want to check for this index,
52:11then for this index,
52:13we have to run a loop on the array
52:15to check whether 1 repeats in the remaining array or not.
52:17Same thing for 2.
52:19For 2, we have to check
52:21whether 2 repeats in the remaining array or not.
52:23Similarly, for 4,
52:25we have to check whether 4 repeats in the remaining array or not.
52:27If 4 does not repeat,
52:29then it is unique and we have to print it.
52:31It is not necessary to have only one unique element.
52:33There can be multiple unique values in an array.
52:35We have to print all of them.
52:37This logic might be difficult for you as a beginner.
52:39Still, you have to try to solve it
52:41to improve your nested loop
52:43and logical understanding.
52:45Next is to write a function to print
52:47intersection of two arrays.
52:49For example, I am given an array
52:511, 2, 3, 4, 5
52:53and another array is 6, 7, 3, 1.
52:55Now, I have to find out the intersection
52:57i.e. I have to print
52:59common elements of both the arrays.
53:01For this,
53:03we have to use a nested loop.
53:05By the way, the nested loop
53:07is not the most optimized way
53:09to solve homework problems.
53:11Later, we will study about hash table.
53:13We can solve these two questions
53:15in an easier way using hash table.
53:17For now, we do not know what is hash table
53:19and what is hashing.
53:21For now, you have to use a nested loop.
53:23Common elements of both the arrays
53:25i.e. intersection of two arrays
53:27are 3 and 1.
53:29Our final output should have 1 and 3 printed.
53:31You do not have to make a new array.
53:33You just have to print 1 and 3.
53:35These are the four questions
53:37that you have to solve as part of your homework problem.
53:39I hope that from today's chapter,
53:41we have learnt a lot about arrays
53:43which we will be applying in the next classes.
53:45Finally, we have started
53:47the journey of our data structures and algorithms.
53:49We can start making notes
53:51from this chapter and next chapter.
53:53If you have completed this chapter successfully,
53:55you can write to me in the comments.
53:57You can also share your progress
53:59on Twitter.
54:01You can find the link in the description box.
54:03That's all for today. See you in the next lecture.
54:05Thank you for watching and keep exploring.