At 23:47 my mind just got blown away. Me be like: - itna easy kese Benstocks 😂🙏. Bhai iPad ka notes ka bhi pdf dalo na . Tumaaher writing sei sab samajh mai ata hai. Boh tuf sight par itna bada article dekhne sei dar lagta hai 🙂. But you are doing amazing job bhai thank you 🙏😌.
for moving zeroes to the end we cen write it in 1 loop instead of two though time complexity is same , complexity for understanding decreases : v oid moveZeroes(vector& nums) { int j=0; for(int i=0;i
For Right Rotation of Array void rotate(vector arr, int d) { if(d>size) d = d % size; reverse(arr.begin(),arr.end()); reverse(arr.begin()+d,arr.end()); reverse(arr.begin(),arr.begin()+d); }
Timestamps: 0:00:00 - Intro 0:00:55 - Q1. Left rotate an array by 1 place 0:07:33 - Q2. Left rotate an array by D places 0:26:36 - Follow up Right rotate an array by D places 0:27:11 - Q3. Moving Zeroes to end 0:40:54 - Q4. Linear Search 0:43:01 - Q5. Union of Two Sorted Arrays 0:59:04 - Q6. Intersection of Two Sorted Arrays 1:12:22 - Outro
27:00 rotating an array left by 1 place is equal to rotating it right by n-1 places. We can use this information for rotating an array to right by d places.
Thanks a lot sir for taking out time from your busy schedule and making videos and uploading those videos in the span of 2-3 days. It takes a lot ot effort. Thanks a lot 😊😊
✦ Learn left rotation of an array by one place 00:03 ✦ Understand the difference between space used and extra space in algorithms. 06:07 ✦ Learn how to left rotate an array in C++ or Java 18:42 ✦ Left rotate an array by D places 24:15 ✦ Use two pointer approach to move zeros to the end of an array. 34:25 ✦ Summary of array problems 40:19 ✦ Implementing a pointer approach to find the union of two sorted arrays. 50:18 ✦ Union and intersection of sorted arrays 55:30 ✦ Optimize time complexity using two pointer approach 1:06:02 ✦ Optimal solution for intersection of two sorted arrays Click to expand 1:11:14
0:00 Introduction of course 01:01 Left rotate an Array by 1 Place 04:38 Pseudo code 07:17 Code-compiler 08:05 Left rotate an Array by D Places 14:38 Pseudo code 20:18 Code-compiler 27:13 Move zeroes to end 37:41 Pseudo code 40:30 Code-compiler 41:05 Linear search 42:01 Pseudo code 42:43 Code-compiler 43:04 Union of two sorted array 53:33 Code-compiler 59:05 Intersection of two sorted array 1:09:30 Code-compiler
Understood 😄. Logic used for right rotate the array k places is that instead of rotating array right by k places I have rotated it n-k places to left . so code for this is - class Solution { public: void rotate(vector& nums, int k) { int n = nums.size(); k = k % n; reverse(nums.begin(),nums.begin()+(n-k)); reverse(nums.begin()+(n-k),nums.end()); reverse(nums.begin(),nums.end()); } };
code for right-rotation: void rotate(vector& nums, int k) { int n = nums.size(); if (k > n) { k = k % n; } reverse(nums.begin(), nums.begin()+n-k); reverse(nums.begin()+(n-k),nums.begin()+n ); reverse(nums.begin(), nums.begin()+n); }
Hii brother can you pls explain me why time complexity of intersection is O(1) and not O(n), where n is the size of larger sized array. Time stamp- 1:12:01
Really your thought process is really clear and the way you write the code is awesome.For union of two arrays you have written the code in such a simpler way whereas in first go I wrote the code this way : vector < int > sortedArray(vector < int > a, vector < int > b) { // Write your code here int i = 0; int j = 0; vector ans; while(i < a.size() && j < b.size()){ if(a[i] < b[j]){ if(i == 0){ ans.push_back(a[i]); } else if(a[i] != a[i-1]){ ans.push_back(a[i]); } i++; } else if(a[i] == b[j]){ if(i == 0){ ans.push_back(a[i]); } else if(a[i] != a[i-1]){ ans.push_back(a[i]); } i++; j++; } else{ if(j == 0){ ans.push_back(b[j]); } else if(b[j] != b[j-1]){ ans.push_back(b[j]); } j++; } } while(i < a.size()){ if(ans.back() != a[i]){ ans.push_back(a[i]); } i++; } while(j < b.size()){ if(ans.back() != b[j]){ ans.push_back(b[j]); } j++; } return ans; }
can you tell me why i++ and j++ should be outside of if else loop. because for me it is not accepting the solution but accepts when i put i++ and j++ inside the if else loop
🎯 Key Takeaways for quick navigation: 00:56 🔄 *Left rotate an array by one place involves moving elements one place ahead. Optimal solution involves in-place rotation without using a new array.* 05:26 ⏰ *Time complexity of left rotation by D places is O(N+D). Extra space complexity is O(D) due to the use of a temporary array.* 12:20 🤔 *When left rotating an array by D places, D can be reduced to D mod N, as multiples of N rotations bring the array back to its original state.* 20:37 ⚙️ *Optimal solution avoids using extra space by reversing the array elements in three steps: reverse the whole array, reverse the first D elements, and reverse the remaining N-D elements.* 23:04 🔄 *The speaker explains a method to rotate an array to the left by a given number of places using three reverse operations.* 27:12 🔄 *The problem of moving zeros to the end of an array is introduced, and a Brute Force approach is discussed, involving identifying non-zero numbers, moving them to the front, and filling the remaining positions with zeros.* 33:45 🔄 *An optimal solution for moving zeros to the end is presented, using a two-pointer approach to efficiently move non-zero elements to the front while iterating through the array.* 40:57 🧐 *Linear search is introduced as the problem of finding the first occurrence of a given number in a sorted array. The speaker presents a Brute Force approach involving iterating through the array and checking for equality.* 43:04 🧑🤝🧑 *The problem of finding the union of two sorted arrays is discussed, emphasizing the need for an optimal solution. The speaker starts with a Brute Force approach involving combining both arrays and removing duplicates.* 44:40 🧭 *Brute force approach for finding the union of two sorted arrays involves using a set data structure to ensure uniqueness and sorted order.* 50:22 🚥 *Optimal approach for finding the union of two sorted arrays uses a two-pointer approach to efficiently iterate through both arrays, considering unique elements.* 53:39 🕰️ *The time complexity of the optimal approach for finding the union is O(N1 + N2), where N1 and N2 are the sizes of the two arrays.* 59:00 🤝 *Brute force approach for finding the intersection of two sorted arrays involves checking for corresponding elements and using a visited array to ensure uniqueness.* 01:05:59 🔄 *The time complexity of the brute force approach for finding the intersection is O(N1 * N2), where N1 and N2 are the sizes of the two arrays.* 01:06:13 🧠 *Brute Force approach for array intersection involves checking every element in both arrays for a match, leading to a time complexity of O(N1 * N2).* 01:07:32 🔄 *Optimal solution for intersection utilizes a two-pointer approach due to sorted arrays, resulting in a time complexity of O(N1 + N2) and no extra space usage.* 01:09:48 🤖 *Implementing the optimal solution involves iterating through both arrays, comparing elements, and building the intersection array with minimal space complexity.* Made with HARPA AI
For left rotate by D places Brute can be : TC: O(n^2) if d==n Hence the rest two solutions shown in video will be better and optimal. int n=arr.size(); while (k>0) { Integer temp=arr.get(0); for (int i = 1; i < n; i++) { arr.set(i-1, arr.get(i)); } arr.set(n-1, temp); k--; } return arr;
left rotation to right rotation: simple approach is to think oppositely to left rotation. Shift all elements right of d and add to temp and push it. Just reverse the order of the reverse statements used in left rotation!.
I always thought that the optimal solution to this code was the hashset one that you did in the middle part. It blew my mind when I saw the optimal one... And that too so easy man... Wow .. just wow to your observation ❤
@@helloworld-n1z I am not the right person but still always go back to the code after a week or so and try solving it again. Then review it after a month. That is it, it will get hard coded in your brain after that.
26:06 for right shift int n = nums.size(); k = k%n; //temp varible to store the values which are n-d from left vector temp; // int temp[]={}; for(int i = n-k;i=0;j--){ nums[j+k] = nums[j]; } //Put back the elements of" temp" int z = 0; for(int l = 0;l
🎯Course outline for quick navigation: [00:03-07:25]1. Dsa course & left rotation problem -[00:24-00:48]456 modules, 400+ problems in ds algo course, covering step 3.1 and five problems. -[01:08-01:40]In an interview, showcase step-by-step optimization of approaches for a positive impact on the interviewer. -[06:20-06:51]Clarify shuttle difference in algorithm interviews to avoid confusion. [07:25-12:28]2. Array rotation -[08:07-09:21]Left rotate array by d places, d=2: 3,4,5,6,7,1,2. d=3: 4,5,6,7,1,2,3. -[10:40-11:27]Multiple of 7 rotations always brings back original array. number of rotations = d mod array size. -[12:07-12:31]To solve for d, use modulo with n; in interviews, start with brute force approach. [12:28-22:37]3. Array rotation and shifting -[13:21-13:50]Shifted first three elements into temporary array and analyzed index shifting. -[15:15-15:43]Shifting the array will result in 4, 5, 6, 7 at new positions, and 1, 2, 3 at the end. -[16:00-16:30]If shifting array by 3 places in a 7-size array, last 3 places will be occupied, resulting in 4 remaining positions. -[16:00-16:53]Shifting array by 3 places with 7 elements, starts at index 4. -[20:10-20:35]Demonstrates shifting and putting back a temporary array, and implementing a left rotate function in c++ or java. -[19:03-21:36]The process involves shifting and storing elements in an array with time complexity of o(d) and o(n-d). -[21:57-22:26]Using beko of d to store extra space for elements, aiming to optimize into an optimal solution. [22:38-33:17]4. Array rotation and moving zeros in arrays -[23:24-24:29]Perform 3 reversals to obtain resultant array, avoiding temporary shifts and copy-pasting. -[24:47-25:15]Algorithm has time complexity of 2n, with no extra space used. -[25:37-26:25]Manually reverse array using starting and ending index if programming language lacks reverse function. -[27:25-27:53]Move all zeros to end, leaving 3 zeros. -[28:06-28:34]Start with brute force solution, pick non-zero numbers, iterate array. [33:19-42:49]5. Optimal solution and array rearrangement -[33:19-33:44]Explanation of time and space complexity for brute force solution. links provided for java and python codes. -[34:19-35:59]Using a two-pointer approach to move non-zero numbers in the array and swapping with zeros. -[37:20-38:56]Implemented single iteration to find and swap zero and non-zero elements in array, improving efficiency. -[37:24-37:50]Iterative process improved with one iteration, reaching the end, aiming for optimal solution. -[41:00-41:28]Linear search finds first occurrence of a number in an array using iteration. [42:49-49:58]6. Union and intersection of sorted arrays -[42:49-43:31]The transcript discusses solving the union and intersection of two sorted arrays. -[44:17-44:52]Interview problem: find union of two sorted arrays with unique elements using brute force approach. -[47:37-48:24]Using brute force approach, time complexity is n1 log n, or n to log n. -[48:52-49:39]Time complexity: o(n1 log n) + o(n2 log n), space complexity: o(n1 + n2) [49:58-55:18]7. Optimal approach for merging sorted arrays and finding union -[50:56-51:27]The smallest element is one, added to the union array, and the pointer moves to the next index. -[53:17-54:11]Iterate through arrays, create union array, and return it. [55:18-01:13:07]8. Union and intersection of arrays -[55:38-56:04]If union array is empty, take the first element; else, the b array element is smaller. -[56:25-57:56]Iterating through remaining elements and ensuring all are processed; ensuring error-free code submission. -[58:36-59:27]Time complexity is n1 plus n2. optimal solution for union and intersection of sorted arrays. -[01:07:11-01:07:40]Optimizing process taking n1 x n2 time and using a two-pointer approach for sorted arrays. offered by Coursnap
Actually, there is another optimal solution for moving zeroes problem. It is similar to the function we use in quicksort algorithm (quickselect part for arranging elements around pivot). void Optimal2(̀vector& nums) { int j=-1, n=nums.size(); for(int i=0; i
Brother, Actually only because of you i came to know what is coding and how to perform our own logic while writing code. Your teaching was nice and I really love it. once before viewing your videos i may code but i don't know how it works internally, but after seeing ur videos it is very easy to understand the working ❣. my first own logic: vector temp; int first = arr[0]; for(int i=1; i
26:50 Right Rotate elements of array by D places : #include using namespace std; void rightRotateByD(int arr[], int n, int d) { // d = d % n; // to handle cases where d >= n reverse(arr, arr + n); // Reverse the entire array reverse(arr, arr + d); // Reverse the first d elements reverse(arr + d, arr + n); // Reverse the remaining elements } int main() { int n; cin >> n; int arr[n]; for(int i = 0; i < n; i++) { cin >> arr[i]; } int d; cin >> d; rightRotateByD(arr, n, d); for(int i = 0; i < n; i++) { cout = d; i--) { arr[i] = arr[i - d]; } // Copying the d elements from temp array to the beginning for(int i = 0; i < d; i++) { arr[i] = temp[i]; } } int main() { int n; cin >> n; int arr[n]; for(int i = 0; i < n; i++) { cin >> arr[i]; } int d; cin >> d; rightRotateByD(arr, n, d); for(int i = 0; i < n; i++) { cout
for the first time i guessed which concept can be used it might sound like a small thing but as a beginner who is just learning to code actually implementing codes without any reference and knowing which loop is used is really HUGE for me. THANK YOU SOO MUCH
First Understanding the problem then finding approach to solve it then if I make the correct solution then codding it in vs code and moving to nxt question and if I didn't get the solution then watching striver
Great! btw in the worst case of Intersection, the space complexity would be O(n1>n2?n2:n1) because whichever one is smaller matches completely with the other array and ends. P.S.- the space is for returning the answer and not solution.
// right rotation by k places int k;// no of rotation cin>>k; int d = k%n; reverse(arr,arr+(n-d)); reverse(arr+(n-d),arr+n); reverse(arr,arr+n); for(int i: arr){ cout
I recommend everyone to solve the linked leetcode problems attached as well, as the code needs to be tweaked little bit . So u can understand and do by yourself Great approaches Striver. thanks
Reverse Approach Code for Right Rotate:- class Solution { public: void rotate(vector& nums, int k) { int n = nums.size(); k=k%n; reverse(nums.begin(),nums.begin()+n-k); reverse(nums.begin()+n-k,nums.end()); reverse(nums.begin(),nums.end()); } };
void rotate(vector& nums, int k) { int s = nums.size(); k = k % s; if(k == 0) return; reverse(nums.end()-k,nums.end()); reverse(nums.begin(),nums.end()-k); reverse(nums.begin(),nums.end()); }
In the brute force approach of union of arrays, you could have directly returned the set instead of taking a temp vector and copying it all over, because the set would only take the single copies of the elements are the time of insertion
bro you are right but most of the time they i.e., dsa practicing websites expect you to return the result in the form of array(for c++ vector and for Java ArrayList).
i think this will give wrong answer because if a element is present in both and twice for eg 1 2 2 and 6 2 2 then it will not take last two 2s as they are already in set.
One thing striver..... In the sheet for the same question as we know there is a link attached for the gfg version and for the leetcode version but in some cases leetcode version is harder and sometimes gfg version. So please pick the hard problem for that
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. class Solution: def rotate(self, arr: List[int], d: int) -> None: n = len(arr) d%=n
I guess I have an approach for "better" solution for "Move zeroes to end" ( 27:13 ) , correct me if i'm wrong but this is what I got, with T.C O(N+C) int count = 0; for(int i=0;i
I am keeping my promise, if you see am covering 5 problems in one video. So recording such a long video, then editing it, then uploading it takes time. I can upload daily, if you want me to to cover one video.
for rotaing by right: void rotateR(vector&arr, int k){ int n = arr.size(); reverse(arr.begin(),arr.begin()+n-k); reverse(arr.begin()+n-k,arr.end()); reverse(arr.begin(),arr.end()); }
Right rotate array by d places is equivalent to left rotate array by n-d places. void rightRotateArrayOptimal(int arr[],int n,int d){ d = d%n; d = n-d; reverse(arr,arr+d); reverse(arr+d,arr+n); reverse(arr,arr+n); }
Hey striver wonderful video. I have a query. The code will be applicable only if the vector or array is sorted in the intersection part. So do we need to sort it again or is there any other optimal approach ?
We will have 2 solution one is talking the first 3(in case of d is 3) elements in the temporary array and then making the last 4 elements to the left most and then put back the first 3 elements in the temporary array to the array as you did And the another solution will be FIRST storing the LAST FOUR(which means for(i=d; i
20:30 Rotate array to the rigth by k steps def rotate(self, nums: List[int], k: int) -> None: #Brute force approach n = len(nums) k = k % n # Temporary array to store the last k elements temp_nums = [] for i in range(n-k,n): temp_nums.append(nums[i]) # Shift the first n-k elements to the right by k positions for i in range(n-k-1,-1,-1): nums[i+k] = nums[i] for i in range(k): nums[i] = temp_nums[i]
How do you know if the first index i.e. i=0, will always going to be zero? Also you cannot initiate j from 0, if arr[] = {1,2,3,0}, both I and j will point to 1 and since they both are non zero elements, you are swapping them with themselves only.
Incase somebody need the code for right rotate , it is in Leetcode rotate array Solution : void rotate(vector& nums, int k) { int n = nums.size(); k = k % n;
conscise solution for move zeroes to end class Solution { public: void moveZeroes(vector& nums) { int n = nums.size(); int j = 0; for (int i = 0; i < n; i++) { if (nums[i] != 0) { swap(nums[i], nums[j]); j++; } } } };
Left rotate an Array by D places 20:31 The last loop seems a little complicated you can go with: //temp element into org array for (int i = 0; i < temp.length; i++) { arr[d+i] = temp[i]; }
Hey, 33:27 , For shifting all zeros to the left we can do like this as well, hehe found something good vector moveZeros(int n, vector a) { vector temp; for(int i=0;i
rotate array by d places for right void rotate(vector& nums, int k) { int n = nums.size(); k = k % n; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin()+k); reverse(nums.begin()+k, nums.end());
Assignment for left:K then for same right=N-K Leetcode Solution : class Solution { public: void rotate(vector& arr, int K) { int N=arr.size(); reverse(arr.begin(),arr.begin()+K); reverse(arr.begin()+K,arr.begin()+N); reverse(arr.begin(),arr.begin()+N); } };
29:34 #include using namespace std; // another brute force // overall time complexity of this code is O(nlog (n)) void move_Zeros(vector &arr, int n) { sort(arr.begin(), arr.end()); reverse(arr.begin(), arr.end()); } int main() { int n; cin>>n; vector arr(n); for(int i=0; i>arr[i]; } move_Zeros(arr, n); for(int i=0; i
Let's march ahead, and create an unmatchable DSA course! ❤
Timestamps someone please :)
Use the problem links in the description.
At 23:47 my mind just got blown away. Me be like: - itna easy kese Benstocks 😂🙏. Bhai iPad ka notes ka bhi pdf dalo na . Tumaaher writing sei sab samajh mai ata hai. Boh tuf sight par itna bada article dekhne sei dar lagta hai 🙂. But you are doing amazing job bhai thank you 🙏😌.
appreciable !!
Please upload the next video.
@takeUforward
class Solution {
public:
void rotate(vector& nums, int k) {
int n = nums.size();
k =k%n;
int temp[k];
for (int i = n - k; i < n; i++)
{
temp[i - n + k] = nums[i];
}
for(int i=n-k-1;i>=0;i--)
{
nums[i+k]=nums[i];
}
for(int i=0;i
for moving zeroes to the end we cen write it in 1 loop instead of two though time complexity is same , complexity for understanding decreases : v oid moveZeroes(vector& nums) {
int j=0;
for(int i=0;i
Who is grinding their head with DSA in their summer vacation?? Heartly thanks to striver for making us understand dsa in such depth :)
Me😃
me too lol
bro this course from his website is completely free for now right ? ... or it has premium paid version as well ?
What do u mean by summer vacation 😢?
not summer anymore, i guess. and vacations, sadly I am in corporate.
For Right Rotation of Array
void rotate(vector arr, int d)
{
if(d>size)
d = d % size;
reverse(arr.begin(),arr.end());
reverse(arr.begin()+d,arr.end());
reverse(arr.begin(),arr.begin()+d);
}
Timestamps:
0:00:00 - Intro
0:00:55 - Q1. Left rotate an array by 1 place
0:07:33 - Q2. Left rotate an array by D places
0:26:36 - Follow up Right rotate an array by D places
0:27:11 - Q3. Moving Zeroes to end
0:40:54 - Q4. Linear Search
0:43:01 - Q5. Union of Two Sorted Arrays
0:59:04 - Q6. Intersection of Two Sorted Arrays
1:12:22 - Outro
27:00 rotating an array left by 1 place is equal to rotating it right by n-1 places. We can use this information for rotating an array to right by d places.
Perfect thought!
great
Bhai leetcode pa left rotation question reverse .end() and begin() use karna pad Raha hai but gfg ma nahi why
@@himanshukaushik9223 in case of vector we use stl function like begin() and end() but in case of array we don't use it for example in gfg
@@bhargavanand7325 thanks bro
at 39:57
int j=0;
for (int i = 0; i < n; i++) {
if(arr[i]!=0){
swap(arr[i],arr[j]);
j++;
} for moving zeros to end also o(n)
Thanks a lot sir for taking out time from your busy schedule and making videos and uploading those videos in the span of 2-3 days. It takes a lot ot effort. Thanks a lot 😊😊
Move zeroes question another approach with O(1) space
int j=0;
// Firstly taking all non- zeroes number
for(int i=0;i O(1)
Right Shift Solution(Leetcode 189):
k = k % arr.length;
reverse(arr, 0, arr.length-1-k);
reverse(arr, arr.length-1-k+1, arr.length-1);
reverse(arr, 0, arr.length-1);
Just do k=k%n, k=n-k!! as simple as that
not only your dsa knowledge is good also your communication skill, voice tone , body movement is superb 🥰🥰
Agreed. He's so smart and confident, definitely a role model to students!
That's why he got into google
✦
Learn left rotation of an array by one place
00:03
✦
Understand the difference between space used and extra space in algorithms.
06:07
✦
Learn how to left rotate an array in C++ or Java
18:42
✦
Left rotate an array by D places
24:15
✦
Use two pointer approach to move zeros to the end of an array.
34:25
✦
Summary of array problems
40:19
✦
Implementing a pointer approach to find the union of two sorted arrays.
50:18
✦
Union and intersection of sorted arrays
55:30
✦
Optimize time complexity using two pointer approach
1:06:02
✦
Optimal solution for intersection of two sorted arrays
Click to expand
1:11:14
Rotate right ---->>>>
void rotate(vector& nums, int k) {
vector temp(nums.size());
for(int i=0; i< nums.size(); i++)
{
temp[(i+k)%nums.size()] = nums[i];
}
nums=temp;
}
0:00 Introduction of course
01:01 Left rotate an Array by 1 Place
04:38 Pseudo code
07:17 Code-compiler
08:05 Left rotate an Array by D Places
14:38 Pseudo code
20:18 Code-compiler
27:13 Move zeroes to end
37:41 Pseudo code
40:30 Code-compiler
41:05 Linear search
42:01 Pseudo code
42:43 Code-compiler
43:04 Union of two sorted array
53:33 Code-compiler
59:05 Intersection of two sorted array
1:09:30 Code-compiler
Thank you Paras!
@@takeUforward Welcome and thanks for this amazing course.
I have written this approach for rotating the array to the right by k steps : void rotate(vector& nums, int k) {
k%=nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin()+k, nums.end());
}
Understood 😄.
Logic used for right rotate the array k places is that instead of rotating array right by k places I have rotated it n-k places to left .
so code for this is -
class Solution {
public:
void rotate(vector& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums.begin(),nums.begin()+(n-k));
reverse(nums.begin()+(n-k),nums.end());
reverse(nums.begin(),nums.end());
}
};
hey, me also applied same approach
same here
Exactly right
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
u can do this also.
Striver please bring string series. Much needed
Striver is the lion of this community
code for right-rotation:
void rotate(vector& nums, int k) {
int n = nums.size();
if (k > n) {
k = k % n;
}
reverse(nums.begin(), nums.begin()+n-k);
reverse(nums.begin()+(n-k),nums.begin()+n );
reverse(nums.begin(), nums.begin()+n);
}
Hii brother can you pls explain me why time complexity of intersection is O(1) and not O(n), where n is the size of larger sized array. Time stamp- 1:12:01
Really your thought process is really clear and the way you write the code is awesome.For union of two arrays you have written the code in such a simpler way whereas in first go I wrote the code this way :
vector < int > sortedArray(vector < int > a, vector < int > b) {
// Write your code here
int i = 0;
int j = 0;
vector ans;
while(i < a.size() && j < b.size()){
if(a[i] < b[j]){
if(i == 0){
ans.push_back(a[i]);
}
else if(a[i] != a[i-1]){
ans.push_back(a[i]);
}
i++;
}
else if(a[i] == b[j]){
if(i == 0){
ans.push_back(a[i]);
}
else if(a[i] != a[i-1]){
ans.push_back(a[i]);
}
i++;
j++;
}
else{
if(j == 0){
ans.push_back(b[j]);
}
else if(b[j] != b[j-1]){
ans.push_back(b[j]);
}
j++;
}
}
while(i < a.size()){
if(ans.back() != a[i]){
ans.push_back(a[i]);
}
i++;
}
while(j < b.size()){
if(ans.back() != b[j]){
ans.push_back(b[j]);
}
j++;
}
return ans;
}
can you tell me why i++ and j++ should be outside of if else loop. because for me it is not accepting the solution but accepts when i put i++ and j++ inside the if else loop
if you are geting confused in last loop at 18:55
i.e
for(int i=n-d; i
Bro the answer is fkn wrong has no one noticed it at all
@@siddiqabr7110Yes bro, i also got it wrong, when referred from video!
Thank you for all the tutorials,
Please keep supporting from starting to get good placement by the help of your tutorials!
🎯 Key Takeaways for quick navigation:
00:56 🔄 *Left rotate an array by one place involves moving elements one place ahead. Optimal solution involves in-place rotation without using a new array.*
05:26 ⏰ *Time complexity of left rotation by D places is O(N+D). Extra space complexity is O(D) due to the use of a temporary array.*
12:20 🤔 *When left rotating an array by D places, D can be reduced to D mod N, as multiples of N rotations bring the array back to its original state.*
20:37 ⚙️ *Optimal solution avoids using extra space by reversing the array elements in three steps: reverse the whole array, reverse the first D elements, and reverse the remaining N-D elements.*
23:04 🔄 *The speaker explains a method to rotate an array to the left by a given number of places using three reverse operations.*
27:12 🔄 *The problem of moving zeros to the end of an array is introduced, and a Brute Force approach is discussed, involving identifying non-zero numbers, moving them to the front, and filling the remaining positions with zeros.*
33:45 🔄 *An optimal solution for moving zeros to the end is presented, using a two-pointer approach to efficiently move non-zero elements to the front while iterating through the array.*
40:57 🧐 *Linear search is introduced as the problem of finding the first occurrence of a given number in a sorted array. The speaker presents a Brute Force approach involving iterating through the array and checking for equality.*
43:04 🧑🤝🧑 *The problem of finding the union of two sorted arrays is discussed, emphasizing the need for an optimal solution. The speaker starts with a Brute Force approach involving combining both arrays and removing duplicates.*
44:40 🧭 *Brute force approach for finding the union of two sorted arrays involves using a set data structure to ensure uniqueness and sorted order.*
50:22 🚥 *Optimal approach for finding the union of two sorted arrays uses a two-pointer approach to efficiently iterate through both arrays, considering unique elements.*
53:39 🕰️ *The time complexity of the optimal approach for finding the union is O(N1 + N2), where N1 and N2 are the sizes of the two arrays.*
59:00 🤝 *Brute force approach for finding the intersection of two sorted arrays involves checking for corresponding elements and using a visited array to ensure uniqueness.*
01:05:59 🔄 *The time complexity of the brute force approach for finding the intersection is O(N1 * N2), where N1 and N2 are the sizes of the two arrays.*
01:06:13 🧠 *Brute Force approach for array intersection involves checking every element in both arrays for a match, leading to a time complexity of O(N1 * N2).*
01:07:32 🔄 *Optimal solution for intersection utilizes a two-pointer approach due to sorted arrays, resulting in a time complexity of O(N1 + N2) and no extra space usage.*
01:09:48 🤖 *Implementing the optimal solution involves iterating through both arrays, comparing elements, and building the intersection array with minimal space complexity.*
Made with HARPA AI
I did not only enjoy the lecture but loved it too. Thanks Striver Bhaiya for explaining so lucidly. ❤
bhai ki pehli video lgayi h ye mene. bohut maja aya, dil garden garden hogya bilkul. thanku bhai.😁
What a wonderful video, it was vey good. Your way of teaching concepts through questions is best.
For left rotate by D places Brute can be : TC: O(n^2) if d==n
Hence the rest two solutions shown in video will be better and optimal.
int n=arr.size();
while (k>0) {
Integer temp=arr.get(0);
for (int i = 1; i < n; i++) {
arr.set(i-1, arr.get(i));
}
arr.set(n-1, temp);
k--;
}
return arr;
Understood and what an explanation
Love your explanation bro, just continue doing what you are doing for the coding community
Amazing person
Your are best amongst all I found on internet hatsoff to you sir.
Thanks for providng such amazing course for completely free. We are intended to you.
left rotation to right rotation: simple approach is to think oppositely to left rotation.
Shift all elements right of d and add to temp and push it.
Just reverse the order of the reverse statements used in left rotation!.
I always thought that the optimal solution to this code was the hashset one that you did in the middle part. It blew my mind when I saw the optimal one... And that too so easy man... Wow .. just wow to your observation ❤
he never skips anything, Patience is next level!!
me first getting the optimal solution and then finding the brute 🤣🤣
mee too😂
#me2 moment
how to remember logic ,i always forget nd cant able to code
@@helloworld-n1z I am not the right person but still always go back to the code after a week or so and try solving it again. Then review it after a month. That is it, it will get hard coded in your brain after that.
Bro me too 😢
Isi wajah se easy problem solve krne me v time lgta h 😂😂 dimag me bs chlta h ki optimal hi krna h
26:06 for right shift
int n = nums.size();
k = k%n;
//temp varible to store the values which are n-d from left
vector temp;
// int temp[]={};
for(int i = n-k;i=0;j--){
nums[j+k] = nums[j];
}
//Put back the elements of" temp"
int z = 0;
for(int l = 0;l
Salute to this consistency.
😆😆
@@rohandhalpe9084 😡😡😡
@@saurabhtiwari9614 kya hua bhai 😔
@@rohandhalpe9084 Bhai aaisa face kyo bnaya h.
void rotateright(vector& nums, int k) {
k = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
}
Your course is awesome wish I could have found your course a year before currently I am in 3rd year of my clg 😊
From which college u r
@@anshu59kumari Techno International New Town West Bengal
🎯Course outline for quick navigation:
[00:03-07:25]1. Dsa course & left rotation problem
-[00:24-00:48]456 modules, 400+ problems in ds algo course, covering step 3.1 and five problems.
-[01:08-01:40]In an interview, showcase step-by-step optimization of approaches for a positive impact on the interviewer.
-[06:20-06:51]Clarify shuttle difference in algorithm interviews to avoid confusion.
[07:25-12:28]2. Array rotation
-[08:07-09:21]Left rotate array by d places, d=2: 3,4,5,6,7,1,2. d=3: 4,5,6,7,1,2,3.
-[10:40-11:27]Multiple of 7 rotations always brings back original array. number of rotations = d mod array size.
-[12:07-12:31]To solve for d, use modulo with n; in interviews, start with brute force approach.
[12:28-22:37]3. Array rotation and shifting
-[13:21-13:50]Shifted first three elements into temporary array and analyzed index shifting.
-[15:15-15:43]Shifting the array will result in 4, 5, 6, 7 at new positions, and 1, 2, 3 at the end.
-[16:00-16:30]If shifting array by 3 places in a 7-size array, last 3 places will be occupied, resulting in 4 remaining positions.
-[16:00-16:53]Shifting array by 3 places with 7 elements, starts at index 4.
-[20:10-20:35]Demonstrates shifting and putting back a temporary array, and implementing a left rotate function in c++ or java.
-[19:03-21:36]The process involves shifting and storing elements in an array with time complexity of o(d) and o(n-d).
-[21:57-22:26]Using beko of d to store extra space for elements, aiming to optimize into an optimal solution.
[22:38-33:17]4. Array rotation and moving zeros in arrays
-[23:24-24:29]Perform 3 reversals to obtain resultant array, avoiding temporary shifts and copy-pasting.
-[24:47-25:15]Algorithm has time complexity of 2n, with no extra space used.
-[25:37-26:25]Manually reverse array using starting and ending index if programming language lacks reverse function.
-[27:25-27:53]Move all zeros to end, leaving 3 zeros.
-[28:06-28:34]Start with brute force solution, pick non-zero numbers, iterate array.
[33:19-42:49]5. Optimal solution and array rearrangement
-[33:19-33:44]Explanation of time and space complexity for brute force solution. links provided for java and python codes.
-[34:19-35:59]Using a two-pointer approach to move non-zero numbers in the array and swapping with zeros.
-[37:20-38:56]Implemented single iteration to find and swap zero and non-zero elements in array, improving efficiency.
-[37:24-37:50]Iterative process improved with one iteration, reaching the end, aiming for optimal solution.
-[41:00-41:28]Linear search finds first occurrence of a number in an array using iteration.
[42:49-49:58]6. Union and intersection of sorted arrays
-[42:49-43:31]The transcript discusses solving the union and intersection of two sorted arrays.
-[44:17-44:52]Interview problem: find union of two sorted arrays with unique elements using brute force approach.
-[47:37-48:24]Using brute force approach, time complexity is n1 log n, or n to log n.
-[48:52-49:39]Time complexity: o(n1 log n) + o(n2 log n), space complexity: o(n1 + n2)
[49:58-55:18]7. Optimal approach for merging sorted arrays and finding union
-[50:56-51:27]The smallest element is one, added to the union array, and the pointer moves to the next index.
-[53:17-54:11]Iterate through arrays, create union array, and return it.
[55:18-01:13:07]8. Union and intersection of arrays
-[55:38-56:04]If union array is empty, take the first element; else, the b array element is smaller.
-[56:25-57:56]Iterating through remaining elements and ensuring all are processed; ensuring error-free code submission.
-[58:36-59:27]Time complexity is n1 plus n2. optimal solution for union and intersection of sorted arrays.
-[01:07:11-01:07:40]Optimizing process taking n1 x n2 time and using a two-pointer approach for sorted arrays.
offered by Coursnap
Actually, there is another optimal solution for moving zeroes problem. It is similar to the function we use in quicksort algorithm (quickselect part for arranging elements around pivot).
void Optimal2(̀vector& nums) {
int j=-1, n=nums.size();
for(int i=0; i
Exceptionally concise👏
can u explain how the swap function works here. we want to move all the zeroes in the end how nums[++j]; ????
u wanna see my solution??
void Zero_at_last(int arr[], int n){
int i=0;
for (int j = 1; j < n; j++)
{
if(arr[i]==0 ){
if(arr[j]==0){
continue;
}
swap(arr[i], arr[j]);
}
i++;
// cout
One more approach can be:
void moveZeroes(vector& nums) {
int n=0;
for(int i=0;iO(N)
SC->O(1)
similar but less code
Concise solution for move zeroes to end:
int p = 0;
for (int i = 0; i < n; i++)
if (arr[i])
swap(arr[p++], arr[i]);
Brother, Actually only because of you i came to know what is coding and how to perform our own logic while writing code.
Your teaching was nice and I really love it. once before viewing your videos i may code but i don't know how it works internally, but after seeing ur videos it is very easy to understand the working ❣.
my first own logic:
vector temp;
int first = arr[0];
for(int i=1; i
Thank you so much for sharing the content free of cost!! very nicely explained too😘
26:50 Right Rotate elements of array by D places :
#include
using namespace std;
void rightRotateByD(int arr[], int n, int d)
{
// d = d % n; // to handle cases where d >= n
reverse(arr, arr + n); // Reverse the entire array
reverse(arr, arr + d); // Reverse the first d elements
reverse(arr + d, arr + n); // Reverse the remaining elements
}
int main()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
int d;
cin >> d;
rightRotateByD(arr, n, d);
for(int i = 0; i < n; i++)
{
cout = d; i--)
{
arr[i] = arr[i - d];
}
// Copying the d elements from temp array to the beginning
for(int i = 0; i < d; i++)
{
arr[i] = temp[i];
}
}
int main()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
int d;
cin >> d;
rightRotateByD(arr, n, d);
for(int i = 0; i < n; i++)
{
cout
for the first time i guessed which concept can be used it might sound like a small thing but as a beginner who is just learning to code actually implementing codes without any reference and knowing which loop is used is really HUGE for me. THANK YOU SOO MUCH
same for me. feels like a big leap
hi in which question u implemented the code yourself? i am having a hard time in writing code for right rotate an arrray ky k places on my own...
my motivation are your efforts, wont let them go in vain, thankyou STRIVER
Guys i just wanna ask something....r u guys doing all these problems on your own or like just watching the lectures
First Understanding the problem then finding approach to solve it then if I make the correct solution then codding it in vs code and moving to nxt question and if I didn't get the solution then watching striver
Learning a lot outta this guy..
Great! btw in the worst case of Intersection, the space complexity would be O(n1>n2?n2:n1) because whichever one is smaller matches completely with the other array and ends. P.S.- the space is for returning the answer and not solution.
done the assignment and understood each and every concept . Sir appreciate your hardwork
Thank You Striver for such an effort.
Your explanations and teaching is really amazing.
Its really Valuable /priceless content :)
// right rotation by k places
int k;// no of rotation
cin>>k;
int d = k%n;
reverse(arr,arr+(n-d));
reverse(arr+(n-d),arr+n);
reverse(arr,arr+n);
for(int i: arr){
cout
This much consistency is all we needed bhaiya🤞🤞🤞kudos to you
I recommend everyone to solve the linked leetcode problems attached as well, as the code needs to be tweaked little bit . So u can understand and do by yourself
Great approaches Striver. thanks
class Solution {
public void rotate(int[] nums, int k) {
int n=nums.length;
k=k%n;
reverse(nums,n-k,n-1);
reverse(nums,0,n-k-1);
reverse(nums,0,n-1);
}
void reverse(int arr[],int start,int end)
{
while(start
Reverse Approach Code for Right Rotate:-
class Solution {
public:
void rotate(vector& nums, int k) {
int n = nums.size();
k=k%n;
reverse(nums.begin(),nums.begin()+n-k);
reverse(nums.begin()+n-k,nums.end());
reverse(nums.begin(),nums.end());
}
};
Why bro Why, Brute force->better-> optimal, Its really a big effort. thanks for such wonderful video series. Love the way u explain.
void rotate(vector& nums, int k) {
int s = nums.size();
k = k % s;
if(k == 0) return;
reverse(nums.end()-k,nums.end());
reverse(nums.begin(),nums.end()-k);
reverse(nums.begin(),nums.end());
}
In the brute force approach of union of arrays, you could have directly returned the set instead of taking a temp vector and copying it all over, because the set would only take the single copies of the elements are the time of insertion
bro you are right but most of the time they i.e., dsa practicing websites expect you to return the result in the form of array(for c++ vector and for Java ArrayList).
59:05
Intersection of Arrays(Brute Force approach)
void find_In(int arr1[], int arr2[], int n1,int n2){
set st;
for(int i=0;i
i think this will give wrong answer because if a element is present in both and twice for eg 1 2 2 and 6 2 2 then it will not take last two 2s as they are already in set.
One thing striver.....
In the sheet for the same question as we know there is a link attached for the gfg version and for the leetcode version but in some cases leetcode version is harder and sometimes gfg version.
So please pick the hard problem for that
vector rotateArray(vectorarr, int k) {
reverse(arr.begin(),arr.begin()+k);
reverse(arr.begin()+k,arr.end());
reverse(arr.begin(),arr.end());
return arr;
}
Striver check it !
Not good way to in interviews rounds
Bhaiyaa ji please upload videos as fast as possible .Our placement season starting soon in June.💫💫💫💫💫💫💫💫💫💫💫💫💫💫
best teacher i have ever found in internet
I gonna fainted..after watching at last that this was easy section..what will happen god in future..bcz I m beginner and finding difficulties 😢😢
Me too bro similar situation 😢
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
class Solution:
def rotate(self, arr: List[int], d: int) -> None:
n = len(arr)
d%=n
def reverse1(i,j,arr):
while i
"THERE IS A ONLY ONE KING IN DSA"
I guess I have an approach for "better" solution for "Move zeroes to end" ( 27:13 ) , correct me if i'm wrong but this is what I got, with T.C O(N+C)
int count = 0;
for(int i=0;i
Bro requesting you please upload videos alternatively as promised bcoz completely relaying on you for placements🥺🥺
Yes you are right, striver bro please we are requesting you please upload the video as promised by you 🙏
I am keeping my promise, if you see am covering 5 problems in one video. So recording such a long video, then editing it, then uploading it takes time. I can upload daily, if you want me to to cover one video.
@@takeUforward ok brother thanks for helping us .we are waiting for upcoming videos ☺️
True
@@takeUforward understood ur pain bro thanks for everything.
for rotaing by right:
void rotateR(vector&arr, int k){
int n = arr.size();
reverse(arr.begin(),arr.begin()+n-k);
reverse(arr.begin()+n-k,arr.end());
reverse(arr.begin(),arr.end());
}
Right rotate array by d places is equivalent to left rotate array by n-d places.
void rightRotateArrayOptimal(int arr[],int n,int d){
d = d%n;
d = n-d;
reverse(arr,arr+d);
reverse(arr+d,arr+n);
reverse(arr,arr+n);
}
It's wrong it should be
d=n%d
reverse(a,a+n)
reverse (a,a+n-d)
reverse (a+n-d,a+n)
59:05 Intersection of two sorted array
1:09:30 Code-compiler (Intersection of two sorted array
Hey striver wonderful video. I have a query. The code will be applicable only if the vector or array is sorted in the intersection part. So do we need to sort it again or is there any other optimal approach ?
We will have 2 solution one is talking the first 3(in case of d is 3) elements in the temporary array and then making the last 4 elements to the left most and then put back the first 3 elements in the temporary array to the array as you did
And the another solution will be FIRST storing the LAST FOUR(which means for(i=d; i
Hi Striver can you please please upload the notes which you are explaining it will be very helpful 🙏🙏
Take your own notes
move zero at end can be also done optimally BY -
vector moveZeros(int n, vector a) {
// Write your code here.
int b=0;
for(int i =0;i
Munnawar Faaroqi explaining dsa questions...😂😂😂😂😂
??
Aisa hai kaide me raho
@@DeepakKumar-e2s5q Ooye Chomu😂
tujhe pta to hai kya bolna chaha rha h tu
20:30
Rotate array to the rigth by k steps
def rotate(self, nums: List[int], k: int) -> None:
#Brute force approach
n = len(nums)
k = k % n
# Temporary array to store the last k elements
temp_nums = []
for i in range(n-k,n):
temp_nums.append(nums[i])
# Shift the first n-k elements to the right by k positions
for i in range(n-k-1,-1,-1):
nums[i+k] = nums[i]
for i in range(k):
nums[i] = temp_nums[i]
Hey Striver,
Won't this work fine for the Move Zero's to the end :
void moveZeroes(vector& nums) {
int i=0;
for(int j=0;j
How do you know if the first index i.e. i=0, will always going to be zero?
Also you cannot initiate j from 0, if arr[] = {1,2,3,0}, both I and j will point to 1 and since they both are non zero elements, you are swapping them with themselves only.
Incase somebody need the code for right rotate , it is in Leetcode rotate array
Solution :
void rotate(vector& nums, int k) {
int n = nums.size();
k = k % n;
vector temp;
for (int i=n-k ; i=0 ; i--){
nums[i+k] = nums[i];
}
int j = 0;
for (int i=0 ; i
Thanku
Bhaiya kab tk poora hoga 🥲
In a previous post bhaiya said that he will try to cover this course in the next 3 months.
In move zeroes to end problem we can use this also...,
int y=0;
for(int i=0;i
27:17 'Move all Zeros to End' can be implemented much easily and effectively as:
void Zero_at_last(int arr[], int n){
int i=0;
for (int j = 1; j < n; j++)
{
if(arr[i]==0 ){
if(arr[j]==0){
continue;
}
swap(arr[i], arr[j]);
}
i++;
// cout
Alternative solution to move zeroes to end -
void moveZeroes(vector& nums) {
int i = 0, j = 0;
while(j < nums.size()){
if(nums[j] == 0){
j++;
}
else{
swap(i, j, nums);
i++;
j++;
}
}
}
can you explain the logic behind this please
Love your explanation sir!You always make things simpler
Really it is world biggest best dsa course. 😊😊
conscise solution for move zeroes to end
class Solution {
public:
void moveZeroes(vector& nums) {
int n = nums.size();
int j = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
swap(nums[i], nums[j]);
j++;
}
}
}
};
You are making easy for us to understand DSA!! Heartfully Thanks to Striver Brooo
Left rotate an Array by D places
20:31
The last loop seems a little complicated you can go with:
//temp element into org array
for (int i = 0; i < temp.length; i++) {
arr[d+i] = temp[i];
}
Hey, 33:27 ,
For shifting all zeros to the left we can do like this as well, hehe found something good
vector moveZeros(int n, vector a) {
vector temp;
for(int i=0;i
Thank you for making such great and useful videos by taking out time from your busy schedule.
class Solution {
public:
void rotate(vector& nums, int k) {
k=k % nums.size();
vector temp(nums.size());
for(int i=0;i
rotate array by d places for right
void rotate(vector& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
Assignment for left:K then for same right=N-K
Leetcode Solution :
class Solution {
public:
void rotate(vector& arr, int K) {
int N=arr.size();
reverse(arr.begin(),arr.begin()+K);
reverse(arr.begin()+K,arr.begin()+N);
reverse(arr.begin(),arr.begin()+N);
}
};
I have reached here , sir . By following your A to Z DSA course . Thanks a lot sir..
Can u tel me is that a fee course or free course?
Understood! Fantastic explanation as always, I've enjoyed the video. Thank you very much!!
Rotate to right
class Solution {
public:
void rotate(vector& nums, int k) {
int n=nums.size();
k=k%n;
if(n==1){
return;}
else{
reverse(nums.begin(),nums.end()-k);
reverse(nums.end()-k,nums.end());
reverse(nums.begin(),nums.begin()+n);
}
// return nums;
}
};
Clear explanation and amazing teaching.
you can also solve the move zeroes to end with this approach in a single loop :
int i=0;
int j=-1;
while(i
29:34
#include
using namespace std;
// another brute force
// overall time complexity of this code is O(nlog (n))
void move_Zeros(vector &arr, int n) {
sort(arr.begin(), arr.end());
reverse(arr.begin(), arr.end());
}
int main() {
int n;
cin>>n;
vector arr(n);
for(int i=0; i>arr[i];
}
move_Zeros(arr, n);
for(int i=0; i