Vectors in C++ ｜ Arrays Part 2 ｜ DSA Series by Shr..
Category
📚
LearningTranscript
00:00Hi everyone and welcome to the complete DSA series in which we are going to study about
00:09vectors.
00:10If you want to study any other concept in DSA, you can find it in this playlist on this
00:15channel.
00:16We can also go from here if we want.
00:20So let's start talking about vectors.
00:26Vectors is basically our next data structure which we will study in detail in today's chapter.
00:30And this data structure is very array-like.
00:32It looks exactly like an array.
00:35When we visualize it, it looks exactly like an array in which we have different blocks
00:41in which we store data.
00:43And along with that, we also have indices or indexes like arrays.
00:48So this is how we visualize our vector.
00:51What are vectors?
00:52Vectors are dynamic in nature.
00:55But by nature, I mean that they do not have a fixed size.
00:58Their size can change.
00:59This is a major difference between arrays and vectors.
01:02Now, before studying vectors, we should know one important thing which is STL.
01:07STL is Standard Template Library of C++.
01:12STL is basically a library which we can imagine as a toolbox in which a lot of data structures
01:19like stack, hash table, queue and other data structures have to be implemented in any programming
01:32language from scratch.
01:33But whenever we sit for a placement interview, internship interview or coding test, we have
01:39limited time.
01:40So we cannot implement all these data structures from scratch to solve a single question.
01:46So STL has already written its implementation in this library.
01:51So we directly pick these data structures from this library as a tool.
01:56And then we use that tool to solve our questions.
01:59So the implementation of the vector is written in this library and we just have to use the
02:04vectors directly to solve our questions.
02:07Now, we will discuss how vectors are implemented internally in this chapter.
02:11So it is not that we will skip an important part.
02:13We will also discuss the implementation.
02:16But usage is more important.
02:18Now, using STL is allowed in placements and interviews.
02:22So we are not taking a shortcut.
02:25We use STL to solve our questions in DSA.
02:29And in this STL, we have a lot of tools.
02:32One of the tools is vector.
02:35So we take the vector tool and we directly implement it.
02:38That is, we start making different vectors for ourselves.
02:41In STL, we will study the vector, queue, stack, set, and other data structures.
02:51So all these data structures are called STL containers.
02:57Containers means containers to store data.
03:02So first, let's talk about our first STL container, which is a vector.
03:07Now, we have already discussed the vector.
03:09We imagine it like an array.
03:11But the size of the array is fixed.
03:16So once we have made an array to store the information of 100 students,
03:20then if there are 1000 students in the future,
03:22then we will not be able to use this array.
03:24So to solve this problem, we have vectors.
03:27And vectors are dynamically resized after implementation.
03:31If we want, we can increase the size of our vector in the memory.
03:35There are different syntaxes to create vectors.
03:37The first syntax is this.
03:39We write vector, then in angular brackets, we write the type of the vector.
03:43What type will be stored in it?
03:45Then we tell the name of our vector.
03:47So in this way, we can declare a vector for ourselves.
03:50So let's come to the code once.
03:52And in the code, we create a vector of integers, which we have named vec.
03:57Now, when we create a vector in this way,
03:59first of all, the size of this vector will be equal to 0.
04:02Why? Because there is no element stored in it.
04:05So by default, this vector is of size 0.
04:07Also, when we create a vector in this way,
04:09then we will get an error.
04:11The error is coming because
04:13to create vectors,
04:15we have to include our vector header file.
04:19If we do not include this header file,
04:21then we will get an error.
04:23Because what is a vector?
04:25Where is its implementation?
04:27The implementation of a vector is written in STL.
04:29And that's why we have to include this header file.
04:31Now, you must have noticed in many places online
04:33that instead of this file,
04:35what do people do? .h
04:37In many places, you must have seen this header file
04:39including many students.
04:41Now, this header file,
04:43to solve questions on many coding platforms,
04:45students include this header file.
04:47But I will not advise you to include this.
04:50Why? Because generally,
04:52in interviews, you can be asked
04:54which header file is of a vector individually,
04:56which header file is of some other data structure.
04:58So we should have that knowledge.
05:01Plus, because we are starting in C++,
05:03we are learning data structures for the first time.
05:05So we should have an idea
05:07about which data structure has which header file.
05:09And generally, in any organization,
05:11if C++ code is being written,
05:13it is a better approach to include
05:15individual header files.
05:17Because if we include other things,
05:19then we can have many namespace conflicts.
05:21Or it is possible that we are including
05:23many such things together
05:25that we will not need in the code.
05:27So it is a better, cleaner approach
05:29If we are starting to learn DSA,
05:31we should include individual header files only.
05:33I have stretched this thing so much
05:35because it is important
05:37from the perspective of learning.
05:39So, in this way, we create a vector.
05:41And the red line has now disappeared
05:43because there is no error now.
05:45Now, this vector has size 0.
05:47So, if we try to cout
05:49vector of,
05:51let's suppose, 0.
05:53In that case,
05:55we will get an error like this
05:57This is called segmentation fault.
05:59Segmentation fault means that
06:01we are trying to access a place
06:03in the memory which is not possible
06:05for us to access.
06:07Why? Because when the index 0
06:09does not exist in the vector
06:11and the vector is empty,
06:13then we will get an error.
06:15Next way is to create vectors
06:17in which we declare a vector
06:19and write equal to on the right side
06:21just like we initialize array with some elements.
06:23Here also, we initialize our vector
06:25Let's suppose, 1, 2, 3.
06:27Now, the vector created is of size 3.
06:29Now, if we print vector of 0
06:31in this,
06:33we will get 1.
06:37This is equal to 1.
06:39Also, one more thing you might be noticing
06:41that I have added an additional thing
06:43in my command which is
06:45hyphen standard is equal to c++ 11.
06:47Adding this is important
06:49because if you are using vectors
06:51and there is an error in your terminal
06:53then you will have to use 11 standard
06:55of c++.
06:57That's why I have written this flag in my command.
06:59Now, how will this vector look in the memory?
07:01Our vector will look like an array
07:03in the memory
07:05whose size is equal to 3,
07:07which has elements 1, 2, 3
07:09and index 0, 1 and 2.
07:11Now, let's see the third way
07:13by which we can initialize our vector.
07:15We create a vector in the same way
07:17but we pass two values in it.
07:19The first value is
07:21the size of the vector
07:23and the second value is
07:25what should be the value
07:27on each index.
07:29So, when we define our vector in this way
07:31then we will get a 3 size vector
07:33and on each index
07:35the value of 0 will be stored.
07:37We can also test this.
07:39If we create a vector of size 5
07:41and initialize values in it
07:43then we can get cout
07:45vector of 0
07:47and similarly
07:50this will be vector of 1, 2,
07:523 and 4.
07:54So, all the values which will be printed
07:56will be equal to 0.
07:58On vectors, we generally create a special type of loop
08:00which we call
08:02a for-each loop.
08:04How does it work?
08:06We write for
08:08and we write the name of our vector in it.
08:10Let's suppose the name of our vector is VEC
08:12and we write an iterator on the left side.
08:14But this time our iterator
08:16if we use an iterator
08:18like i or j
08:20then this time it will not store the index value
08:22but this time the iterator
08:24will store the value
08:26which is stored on each index of our vector.
08:28This time i is not the index
08:30but the value on the index itself.
08:32For example,
08:34if we write int i
08:36then we will get the value
08:38stored on that index
08:40in i.
08:42Let's test it.
08:44For example,
08:46if we decide to use a for-each loop
08:48then for that if we write int i
08:50we write colon
08:52and after that the name of our vector
08:54and every time we get c out
08:56for i.
08:58And the type of this iterator
09:00will be equivalent to the type of our vector.
09:02So, we will run it
09:04and all the values will be equal to 0
09:06and will be printed.
09:08In fact, let's take one more example.
09:10Let's create a character vector
09:12in which we will store some characters.
09:14We will get b,
09:16c, d
09:18and e.
09:20So, this time the size of our iterator
09:22will be a character.
09:24So, if we print it
09:26then all the characters will be printed.
09:28Also, this i is not generally called i
09:30we can give it some other name
09:32which is more readable.
09:34We can call it value.
09:36So, we will know that we are trying to
09:38access the value of each index of our vector.
09:40So, this is the syntax
09:42for writing a for-each loop.
09:44Generally, when we are using STL containers
09:46then we are going to be frequently
09:48using these for-each loops.
09:50Now, whenever we talk about vectors
09:52we have talked about how to create empty vectors
09:54with some values
09:56with some fixed size
09:58but in vectors we can also add, delete
10:00all these operations.
10:02To do these operations
10:04we are going to learn about some vector functions.
10:06Basically, there are many different functions
10:08associated with vectors
10:11The first function is
10:13the size function
10:15which returns the size of the vector.
10:17Let us clear this.
10:19If I want to print the size
10:21of this vector
10:23then we simply do cout
10:25size equal to
10:29we write vector.size
10:31and call our function.
10:33So, in this way
10:35our size will be printed which is equal to 5.
10:37Here, if we remove a character
10:40then our size will change
10:42and size is going to be equal to 4.
10:44In the same way, we have another function
10:46called pushback.
10:48Let's suppose we have created an empty vector.
10:50Here, in this way
10:52we have created this empty vector
10:54Let's keep its type as integer.
10:56So, if we print the size
10:58then we will get
11:00size is equal to 0.
11:02And because there is no element in it
11:04then our loop will not run.
11:06But if we want to push an element in this vector
11:08then how do we push it?
11:10To push it, we use vector.push
11:12underscore back function
11:14which pushes the element
11:16at the end of the vector.
11:18For example, initially the size of the vector is 0
11:20so as soon as we push an element
11:22our vector will become
11:24of one size and
11:26let's suppose we store the value as 25.
11:28So, this 25 value will be stored here.
11:30So, let's push back 25
11:32and after that
11:34we will print the size again.
11:37After pushback
11:39this is our size.
11:41Let's clear this and run.
11:43So, size was 0 before
11:45after pushback our size is equal to 1.
11:47Here, we need to make
11:49data type integer
11:51to print the value of our vector.
11:53So, we will get 25 as well.
11:55So, in this way, our size increases
11:57as soon as we push the elements.
11:59If we want, we can push back 3 elements
12:0125, 35 and 45.
12:03So, in this case
12:05the new size of our vector
12:07is going to be equal to 3.
12:09From pushback, we can see that
12:11the order in which we pushed back
12:13the elements are being added.
12:15For example, after 25 we got 35
12:17so when we are doing pushback
12:19we are pushing the elements
12:21at the end of our vector.
12:23As we have pushback,
12:25we have this function called popback.
12:27Push means generally in programming
12:29that we are adding or inserting something.
12:31Pop means that we are deleting something.
12:34So, popback means that
12:36we want to delete the last element.
12:38As soon as we delete it,
12:40the size of our vector will be equal to 2.
12:42So, let's test this as well.
12:44We created an empty vector
12:46in which we pushed 3 elements.
12:48Now, we want to simply popback
12:50our value in the vector.
12:52When we popback,
12:54we don't need to tell the value
12:56because by default our vector knows
12:58what is its last index.
13:00So, in popback, the last index value will always pop.
13:03So, which value will be deleted from the vector?
13:0545 is going to be deleted
13:07because it is on the last index.
13:09So, when we print values in this loop,
13:1145 will not be printed.
13:13Let's print this.
13:15In the beginning, size was 3
13:17but only 25 and 35 were printed
13:19because 45 was deleted from the internal memory.
13:21Apart from this, we have another function
13:23which is called front.
13:25Front means that we want to print
13:27the value on the front of the vector.
13:29For example, if we remove this loop
13:31vector.front
13:35then we will get front value
13:39which is going to be 25.
13:41Similarly, we have back
13:43which returns the last value.
13:45So, last value is 35.
13:47Last value is 35 because we deleted 45.
13:49We have another function
13:51which is called at function.
13:53At is basically another syntax for accessing
13:55a value at a particular index.
13:57For example, we wrote
14:00So, we are going to get ith index value.
14:02The alternate way to write this is
14:04vector.at index i.
14:06So, this is going to give us
14:08the same value.
14:10vector.at 0
14:12So, we will get the value of 0th index
14:14which is equal to 25.
14:16If we want to look at the value
14:18at index 1, it is going to be 35.
14:20If we want to look at the value
14:22of index 2,
14:24it is going to give us an error.
14:26Why the error?
14:29Because the value at index 2
14:31does not exist anymore.
14:33So, we are trying to access
14:35such things again which is not possible.
14:37So, we should never access the values
14:39outside the index.
14:41Now, we have some additional functions
14:43related to vectors which we generally use
14:45when we are talking about iterators.
14:47But, we have not talked about iterators yet.
14:49In fact, it is not relevant for us now.
14:51I might make a C++ one shot
14:53for all the STL containers
14:55which we will cover later.
14:57But, for now, we do not need to know
14:59about other functions.
15:01Next, we are going to talk about
15:03static vs dynamic allocation
15:05of memory.
15:07Basically, in this section,
15:09we are going to learn how vectors
15:11are internally implemented in memory.
15:13Whenever we talk about memory,
15:15we have two types of memory.
15:17One is static memory.
15:19Static memory is allocated
15:21in compile time.
15:23Generally, when we create an array,
15:26an integer array of size 5,
15:28this memory is allocated
15:30in compile time.
15:32We have already discussed that
15:34our code runs in two stages.
15:36The first one is compilation stage
15:38in which compiler runs and checks
15:40for syntaxical errors or other things
15:42like whether all header files are included
15:44properly or not.
15:46The second stage is execution
15:48which is also known as running stage.
15:50So, static allocation of memory
15:52is basically the memory
15:55which is allocated in compile time.
15:57So, if you create an array like this,
15:59that array will be created
16:01in compile time.
16:03Dynamic allocation of memory
16:05is done in run time
16:07or execution time.
16:09Basically, when we write this code,
16:11here we have written
16:13that we have to make a vector of integer
16:15but we have not given any element in it.
16:17So, initially, in compile time,
16:19a vector of zero size will be created.
16:21In run time, this pushback function
16:23will be executed and an element
16:25will be pushed inside that vector.
16:27So, in run time, the size of that vector
16:29will increase as it has to store more elements.
16:31So, when is the new memory allocated
16:33to increase the size of the vector?
16:35It is done dynamically.
16:37So, when is it done dynamically?
16:39In run time, when our program is executing.
16:41So, the memory allocated to vectors
16:43is done dynamically
16:45in run time.
16:47That is why we said that
16:49vectors can resize.
16:52They can change their size.
16:54Whereas, the size of an array is fixed.
16:56Generally, when we do programming
16:58or DSA, in majority of cases,
17:00we need an array to resize.
17:02That is why we frequently
17:04use vectors in our codes.
17:06But the logic of vectors,
17:08the question that can be solved by vectors
17:10can also be solved by arrays.
17:12So, we are going to re-implement
17:14the same logic in the vectors chapter.
17:16Now, there is another difference
17:18in static and dynamic allocation.
17:21In static allocation,
17:23there are two types of memory.
17:25One is our stack memory
17:27where we talked about stack
17:29and function calls.
17:31The other is our heap memory.
17:33Static allocation is
17:35inside the stack memory.
17:37So, the array that is created
17:39is getting created inside the stack itself.
17:41But, dynamic allocation
17:43is inside the heap memory.
17:45In fact, the memory that is dynamically allocated
17:47in run time is allocated
17:49inside the stack.
17:51So, whenever we are asked
17:53what are the differences
17:55between static and dynamic allocation,
17:57we can tell three differences.
17:59First, it is in compile time,
18:01second, it is in stack,
18:03third, it is in heap.
18:05Now, we know that
18:07vectors are following dynamic memory allocation.
18:09But, how exactly vectors are created
18:11inside the memory?
18:13Let's suppose, we wrote
18:15vector of integer vec in our code.
18:18Now, we will have a zero size vector
18:20which means we don't have anything inside the memory.
18:22When we will pushback
18:24an element inside this vector for the first time,
18:26let's suppose, we pushbacked
18:28value 0,
18:30we will have a one size vector
18:32which will have
18:34zero value inside it.
18:36So, our vector will look like this.
18:38Now, when next time
18:40we pushback another element inside it,
18:42let's suppose, we pushbacked
18:44value 1,
18:47we will try to store this new value
18:49inside the old vector.
18:51Internally,
18:53vectors are arrays.
18:55So, the first time
18:57we created a vector of size 1
18:59to store 0,
19:01we created an array inside the memory
19:03whose size was equal to 1.
19:05So, vector is nothing,
19:07it is just an array inside the memory.
19:09Second time, when we will try to store
19:11an element, we will try to store it in this array.
19:13But, this array is full.
19:15So, when we will try to store
19:17a new element inside the old vector,
19:19we will create a new array
19:21whose size is double.
19:23For example,
19:25we created an array of size 1
19:27and now we have an array of size 2.
19:29Now, we copied the old value 0
19:31inside this array.
19:33Now, we will store the new value 1
19:35inside this array.
19:37Now, this new array
19:39will be our new vector
19:41and the old one will be deleted
19:44Similarly, we will push back
19:46a new element inside the vector 2.
19:48Now, 2 will be stored
19:50inside this array.
19:52But, there is no space in this array.
19:54So, a new array of double size
19:56will be created in the memory.
19:58This time, an array of size 4 will be created.
20:00The old values will be copied
20:02and the new value will be stored.
20:04A new vector will be created
20:06and the old array
20:08will be deleted from the memory.
20:10Now, our vector looks like this.
20:13Now, these vectors have
20:15two properties.
20:17One is the size property.
20:19Size means number of elements.
20:23The other one is the capacity property.
20:25Capacity means
20:27the number of elements
20:29which can be stored inside
20:31this internal array.
20:37In this case,
20:39the size of the vector is 3
20:41but the capacity is equal to 4.
20:43That means, one more element
20:45can be stored here.
20:47So, this thing
20:49which we talked about
20:51that whenever the size of the internal array
20:53becomes small,
20:55our internal array becomes double.
20:57How to verify this thing?
20:59We can write the same code.
21:01After writing this code,
21:03when we print the size and capacity,
21:05the size will be 3
21:07and the capacity will be 4.
21:10There is no element inside the array.
21:12After that,
21:14we are going to push back some values
21:16inside the vector.
21:18First, we pushed back 0.
21:20Then, we pushed back 1.
21:22Here, we will get 1.
21:24Here, we will get 2.
21:26After this,
21:28we want to print the vector size
21:32which is going to be equal to 3.
21:34And we want to print the capacity
21:36of the vector.
21:39The function is called capacity
21:41and the capacity of the vector is 4.
21:43We will print this.
21:45First value is 3 and second value is 4.
21:47Basically, the logic which we discussed
21:49internally in the memory,
21:51these things are happening.
21:53If we push back vector.pushback3
21:55and vector.pushback4
21:57again,
21:59what will happen in these two cases?
22:01When we push back 3,
22:033 will be stored here.
22:05But when we push back 4,
22:074 will be stored here.
22:09So, in that case,
22:114 will be stored here.
22:13So, we will create
22:15another double size array
22:17inside the memory
22:19where 0, 1, 2, 3 will be copied
22:21and 4 will be stored here.
22:23But the remaining 3 places will be empty.
22:25So, if the old capacity was 4,
22:27the new capacity will always be double.
22:29The size will not be double,
22:31but the capacity will be double.
22:33This time, the capacity will be double
22:36After writing the line,
22:38if we print the size,
22:40size is going to be equal to 5,
22:42capacity is going to be equal to 8.
22:44We can also verify this.
22:46Here, we gave two more pushback statements
22:48for 3 and 4.
22:50So, this time, size will be equal to 5
22:52and capacity will be equal to 8.
22:54So, we are getting the same values.
22:56So, this is how a vector works internally
22:58in the memory.
23:00Vector is nothing.
23:02Vector is just an array inside the memory.
23:05So that the programmers feel that
23:07the vector is magically increasing in size.
23:09But nothing is magical.
23:11Internally, automatically,
23:13this work is happening inside C++.
23:15Next, we are going to solve a problem
23:17which is called a single number.
23:19I had given you a similar question
23:21in the last chapter as a homework problem
23:23that we will have a given array.
23:25Inside this array,
23:27we have a lot of different elements
23:29like 1, 4, 5, etc.
23:31We have to print the unique elements
23:33because their copies do not exist.
23:35Now, we have a question like this.
23:37Here, the question is not very important.
23:39More important than the question is
23:41how to solve the questions.
23:43So, for the first time, we are going to see
23:45the lead code question.
23:47Whenever we are learning DSA,
23:49we will learn the concepts of DSA.
23:51We will solve a lot of questions
23:53in the lectures and in the class.
23:55But it is important to practice
23:57on the online platforms.
23:59Because the more you practice,
24:02the more you will learn.
24:04So, you should know the concepts of DSA.
24:06It is important to practice along with DSA.
24:08Because eventually, when you sit
24:10in the coding test,
24:12it is not necessary that
24:14you will get the same question.
24:16In some cases, you may get the same question.
24:18In some cases, you may get new questions.
24:20And we will learn to solve new questions
24:22only when we practice a lot of questions.
24:24So, we are starting with a very simple
24:26and easy level question.
24:28The question is problem no. 136 on lead code.
24:31Now, when we are given a problem,
24:33generally, there are three levels
24:35of easy, medium, and hard problems.
24:37We should always start by solving easy problems.
24:39Gradually, we move towards medium problems.
24:41And then, we move towards hard problems.
24:43Do not start solving medium
24:45or hard problems in the beginning.
24:47In the beginning, make a grip on easy.
24:49Feel confident in it.
24:51Then, make a grip on medium.
24:53Feel confident in it.
24:55Then, move towards hard level problems.
24:57Now, whenever we are given a question,
24:59like here, the question is
25:01given a non-empty array of integers,
25:03NUMS.
25:05NUMS is a non-empty array.
25:07NUMS is a non-empty array.
25:09Now, we are given an array.
25:11On the right side, the boilerplate code of C++
25:13has a vector.
25:15And generally, this is what happens in questions.
25:17On coding platforms,
25:19the question is of an array, but it has a use vector.
25:21So, this is a very normal practice.
25:23Every element appears twice
25:25except for one.
25:28In NUMS, every element appears twice
25:30except for one element.
25:32Find that single one.
25:34We have to find that one element.
25:36There are many examples related to this question.
25:38Let's see this example.
25:40In this example, we have 4, 1, 2, 1, 2.
25:42In this example, we have 4, 1, 2, 1, 2.
25:44So, let's draw this array.
25:46So, let's draw this array.
25:48Array is 4, 1, 2, 1, 2.
25:50Array is 4, 1, 2, 1, 2.
25:52Let's call it NUMS.
25:54NUMS is a vector.
25:56So, it appears twice.
25:58but 4 appears only once.
26:00So, its answer should be equal to 4.
26:02Now, we have to find out this answer.
26:04This unique element, we have to find out.
26:06Whenever we have to solve a question
26:08on platforms,
26:10we don't have to write a complete code.
26:12We don't have to write boilerplate code.
26:14We are given just a class.
26:16The class introduces a function.
26:18About the class, why does it appear public?
26:20We will discuss these things
26:22in the chapter of object-orientation.
26:24we have to focus only on this function
26:26let's see this function
26:28in this function there is a return type integer
26:30function name is single number
26:32all these things are already given and this vector is given by nums
26:34and the complete answer
26:36we will write in this function
26:38final answer which is
26:40going to be single number
26:42we will return it then only it is a return type integer
26:44now generally this vector
26:46given in function
26:48with this ampersand is given
26:50as we know normal vector looks like this
26:52so many students must be thinking
26:54what is this ampersand doing here
26:56basically all the containers of C++
26:58C++ container means
27:00like vector, vector is a C++ container
27:02whenever we pass them in functions
27:04they are always by default
27:06pass by value
27:08but we want that
27:10the changes in this function should reflect
27:12so we
27:14pass them by pass by reference
27:16instead of pass by value
27:18and to pass by reference
27:20we can put an ampersand
27:22in front of their name
27:24it comes in front of name
27:26or we can put it here also
27:28in both the cases
27:30we have to put an ampersand
27:32by putting ampersand
27:34our original
27:36copy
27:38our original vector
27:40this kind of vector
27:42basically an alias is created
27:44like Gangadhar's name is Shaktimaan
27:46or Tony Stark's name is Ironman
27:48so these are aliases
27:50aliases means alternate name
27:52so we create an alias
27:54create an alternate name
27:56and when we are saying nums
27:58we are talking about the same original
28:00that is why this ampersand is used to pass
28:02this vector with reference
28:04so any changes if you do in this function
28:06in this vector then it will reflect in main function
28:08so these are some basic things
28:10which we should know
28:12before we start solving any question
28:14now here we have
28:16some constraints
28:18these limits
28:20when we will read this chapter
28:22then we will understand
28:24otherwise I have already made one shot of C++
28:26which I will add in this playlist
28:28after this chapter I would advise you
28:30to go and watch that one shot
28:32that one shot is about time and space complexity
28:34for interviews
28:36in that one shot
28:38you will understand half of the lecture
28:40because it has easy things
28:42we will not understand half of the lecture
28:44because in that I have
28:46talked about later data structures
28:48and algorithms
28:50but it is important to watch
28:52so that we will get an idea about time complexity
28:54and space complexity
28:56and why these constraints are given
28:58what we calculate through these constraints
29:00so that is one thing
29:02which I am giving you as a homework problem
29:04so let's come back to the question
29:06the question is given in this way
29:08now if we want we can do this question with nested loop
29:10like I have given the homework of arrays
29:12we can also do this question with nested loop
29:14but here this line is written
29:16linear runtime complexity
29:18it means you don't have to use nested loops
29:20you have to make only one loop
29:22we have to write only one loop
29:24to solve this question with only one loop
29:26as a beginner it may look a little tricky
29:28unless and until we have already learned
29:30a lot of things about bit manipulation
29:32so this question will teach us a lot of new things
29:34one thing which this question
29:36is going to teach us is
29:38the bits which we have talked about
29:40the bit wise operators which we have talked about
29:42how they are practically used to solve questions
29:44this question is going to teach us that
29:46basically I know all these numbers
29:48I have to find a unique number from these
29:50and unique number is equal to 4
29:52so I have to print 4
29:54now before solving this problem
29:56let's make a small mindset
29:58because it is not important to solve the problem
30:00how that problem is getting solved
30:02what is the logic behind it, what is the thought process
30:04it is very important to understand that
30:06let's suppose we are given a very small problem
30:08a number is 4, a number is 1
30:10and a number is minus 4
30:12from these numbers we know that
30:14every number has a negative available
30:16and we have to find out that number
30:18so how do we find out
30:20if we have this number
30:22then we simply do 4 plus 1 minus 4
30:24this 4 minus 4 will cancel out
30:26and we will have 1
30:28so 1 will be our answer
30:30basically if it was plus minus
30:32then we know that
30:34if plus and minus are in equal magnitude
30:36then they can cancel out each other
30:38and if we would have got
30:40a bigger version of this problem
30:42like we would have got 4 plus 1 plus 2
30:44minus 1 minus 2
30:46then we would have cancelled 1 from 1
30:48and cancelled 2 from 2
30:50and we would have got 4
30:52so if we were given numbers in the form of plus minus sign
30:54then it would have become very simple for us
30:56because we just have to
30:58add everything
31:00always the value of plus will cancel out the value of minus
31:02and we will get the final answer
31:04so our logic is based on this
31:06basically
31:08we have to do something
31:10we know that every number
31:12has a duplicate
31:14given to us
31:16there is only one number which is unique
31:18so we have to find
31:20a way to cancel out
31:22the number with the duplicate
31:24and if we find this way
31:26then all the duplicates
31:28will cancel out
31:30and only unique number will remain
31:32so what is the way in programming
31:34that we can cancel out
31:36two same numbers
31:38and that way is hidden
31:40in bitwise operators
31:42specifically if I talk
31:44bitwise in XOR
31:46we have studied XOR operator
31:48what were the rules of XOR operator
31:500 XOR 0 is 0
31:521 XOR 1 is
31:540
31:560 XOR 1 is 1
31:58and 1 XOR 0 is 1
32:00so what does XOR operator do
32:02if it has same values
32:04then it cancels out the same values
32:06cancel out means
32:08it makes them 0
32:10so this is an important property which XOR brings with it
32:12now whenever we are talking about numbers
32:14like for example we take this 2 and this 2
32:16we have 2 and we have 2
32:18but what is 2 internally
32:20what is there in the computer
32:22it is a binary
32:24binary form of 2 is 1 0
32:26so for now let's see the binary forms
32:28this is first 2
32:30this is second 2
32:32now if I take XOR of these two
32:34so 1 0 XOR with 1 0
32:360 and 0 XOR is 0
32:381 and 1 XOR is 0
32:40so two numbers whose values are same
32:42their XOR will always be equal to 0
32:44means they will cancel out
32:46like plus 2 and minus 2
32:48cancel out and give 0
32:50similarly XOR with 2
32:52also cancels out and gives 0
32:54so in bits XOR performs
32:56the operation which we needed
32:58if you want
33:00let's understand this through one more example
33:02because I want you to remember this from today's class
33:04let's suppose we have a number 6
33:066 is 1 1 0
33:08take XOR of 1 1 0 with 1 1 0
33:10means 6 XOR 6
33:120 0 cancels out, 1 1 cancels out
33:141 1 cancels out, answer is equal to 0
33:16so any number
33:18if you take XOR with that number
33:20then value will always be equal to 0
33:22so if we talk about
33:24stored in numbers
33:26if we talk about these numbers
33:28so let's suppose
33:30we take XOR of 1 with 1
33:32so this value will be 0
33:34take XOR of 2 with 2
33:36so this value will be 0 and only 4 will be left
33:38now this XOR
33:40we don't know which number is in front and which number is behind
33:42so what we will do
33:44we will take XOR of entire array
33:46means we will run a loop
33:48and all the values in the array
33:50we will take XOR of all of them
33:52so when we are taking XOR of all of them
33:54basically we will take 4 XOR 1
33:56XOR 2, XOR 1, XOR 2
33:58now we know these numbers
34:00XOR means first take
34:02means first take XOR of 2 and 1
34:04then take XOR of 2 and 1
34:06final answer is always same
34:08so when we have taken overall XOR of these values
34:10so I know XOR 0 is going to come
34:12so last value of all of them will be XOR 0
34:14so 4 XOR 5 value will be left
34:16and what is 4 XOR 5
34:184 is 1 0 0
34:20so 0 XOR 0
34:220 XOR 0
34:241 XOR 1
34:26so final answer will be 4
34:28basically I am trying to show you a property
34:30now if we take any number n
34:32and we take XOR of it with 0
34:34so any bit with 0 in n
34:36when it will be XOR with 0
34:38then it will be 0
34:40it will not change
34:42and any bit with 1 in n
34:44it will always have XOR with 0
34:46and final answer will be equal to 1
34:48so all bits of n
34:50whether it is 0 or 1
34:52they will be same
34:54so we have to remember two properties
34:56first of all
34:58XOR of n with any number is 0
35:00and XOR of any number with 0
35:02it is same number
35:04these are two major learnings
35:06which we have to remember
35:08and not only in this question
35:10we can use it in many other questions
35:12so when we want to get our unique value
35:14so what we have to do
35:16we have to take XOR of all numbers
35:18and our final answer
35:20that is going to be equal to n
35:22n means our unique value
35:24and in fact we can solve it with a small example
35:26for example
35:28we have three numbers
35:30we have 4, we have 1
35:32we have 1
35:34when we take 4 XOR 1
35:36this value will be equal to 101
35:38so XOR of these two will be 101
35:40with this we will take XOR again
35:42with 1
35:44this will be equal to 101
35:46and 100 is equal to 4
35:48these two will cancel out
35:50and we have only 4 left
35:52so this is the way to get unique element
35:54from any given array
35:56where every element is repeating
35:58because XOR will cancel out repetitions
36:00and unique element will be left
36:02so what we can do
36:04we can take an answer equal to 0
36:06we can run a loop on all vectors
36:08i.e. integer which will be value on every index
36:10in the vector
36:12in nums we will run a loop on every vector
36:14and every time what will be the answer
36:16in answer I have to take XOR of every index
36:18so answer will be equal to
36:20XOR of answer
36:22on next index
36:24next index means this value
36:26so with every value we will take XOR
36:28and finally
36:30in this answer all values will cancel out
36:32only last unique value will be left
36:34we will return it from here
36:36i.e. we will return our answer
36:38so in this way
36:40you can see the logic
36:42in this we have used only one loop
36:44i.e. we have followed this linear run time complexity
36:46condition
36:48constant space means you can make single variables
36:50so we have made single variables
36:52so this constant extra space
36:54is satisfying all conditions
36:56so let's write the code
36:58this is our function
37:00we have to take an answer which we will initialize with 0
37:02then we will run a for each loop
37:04integer value in our nums
37:06answer is going to be
37:08answer XOR value
37:10and finally
37:12we will return our answer
37:14first of all let's try to run this code
37:16all test cases are passing
37:18now let's submit it
37:20after submitting our solution is accepted
37:22also this thing
37:24i.e. here
37:26we can also do this thing in short
37:28we can write it
37:30XOR equal to
37:32in this way also our code is going to be successfully compiled
37:34so I hope here
37:36we have understood two things
37:38first of all
37:40how to read and solve questions
37:42in our lead code platforms
37:44second thing
37:46we have read old things
37:48which we thought to be very simple
37:50like bit wise operators
37:52how to use those small things
37:54to solve big questions
37:56so nothing is small or unimportant
37:58everything has it's own use
38:00so we have completed this question
38:02next chapter will be erase part 2
38:04we are going to solve all these questions
38:06now we will solve those questions through vectors
38:08but we will name that chapter as erase part 2
38:10so in today's chapter
38:12we have discussed what was STL
38:14what is a vector
38:16how to use different functions
38:18in a vector
38:20static versus dynamic
38:22we have talked about memory allocation
38:24apart from that we have seen
38:26how vectors are created internally
38:28in memory
38:30plus we have seen
38:32how to solve questions
38:34in all the platforms
38:36like code forces
38:38code chef
38:40generally you will be given a question
38:42you have to complete some function
38:44and that's it
38:46in some platforms you have to write the whole code
38:48and submit the file
38:50but there won't be any problem
38:52because we have already written the code in visual studio
38:54and we have also solved this question
38:56called single number
38:58in which we have used bit or bit wise operator
39:00so we have covered all these things
39:02in today's chapter
39:04in two things i will give you a very simple homework problem
39:06first of all you have to write
39:08linear code on a vector
39:10second thing
39:12you have to write reverse code on a vector
39:14and this reverse code
39:16you have to write in function
39:18and when you will pass this function as a vector
39:20one thing you have to notice
39:22in function the vector which is being reversed
39:24will it reflect in main function
39:26and if it doesn't reflect
39:28then you have to pass by reference
39:30we have already learnt that
39:32so how you can implement that
39:34in your code
39:36so these two things you have to try
39:38as a homework problem
39:40also you can go on lead code
39:42and try to solve easy level array problems
39:44or vector problems
39:46you can try easy level problems
39:48may be you can't solve it
39:50so there is nothing to worry
39:52slowly as we will learn more data structures
39:54more things
39:56will be solved
39:58so that's all in this lecture
40:00from next chapter we will start solving
40:02our many array problems
40:04that's all for today
40:06see you in next video
40:08keep learning and keep exploring