First Negative Number in every Window of Size K | Sliding Window
Вставка
- Опубліковано 30 жов 2020
- Patreon Link: / adityaverma
Video Pdf Notes And Code: / 43359058
Playlist Link: • Sliding Window Algorit...
Problem Description: practice.geeksforgeeks.org/pr...
Given an array and a positive integer k, find the first negative integer for each and every window(contiguous subarray) of size k.
Example:
Input:
2
5
-8 2 3 -6 10
2
8
12 -1 -7 8 -15 30 16 28
3
Output:
-8 0 -6 -6
-1 -1 -7 -15 -15 0 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Can someone confirm if they received a notification for this video or not?
I too!
I got !
Oh good Thanks :) I thought the option for notifying people was off.
Which Drawing Tool / Software are you using I want to use the same while solving the problem.
Sorry but I didn't get the notification actually
For those who are looking for the implementation i have done both the brute force and the optimised method using Python
1) Brute Force Method
def return_arr(arr , k):
final_list = []
l=0
r = k-l-1
count = 0
while(count < len(arr)-k+1):
temp_arr = arr[l:r+1]
for i in temp_arr:
if i < 0:
final_list.append(i)
break
if temp_arr[-1] == i:
final_list.append(0)
count+=1
l+=1
r+=1
return final_list
2) Optimised method
def return_ans(arr , k):
l = 0
r = 0
temp_store = []
final_ans = []
while(r < len(arr)):
if arr[r] < 0:
temp_store.append(arr[r])
if r - l + 1 != k :
r+=1
elif r - l + 1 == k :
if len(temp_store) == 0 :
final_ans.append(0)
else:
final_ans.append(temp_store[0])
if arr[l] < 0:
temp_store.pop(0)
r+=1
l+=1
return final_ans
Let me if have any doubts
Thanks
This is really good but.. len is O(n) and pop(0) is also O(n)
@@gouthamtadali5072 yes this might not be the optimal solution, here we could use Queue
@@gouthamtadali5072 len function in Python is O(1) -> when you add elements in a list, it modifies the len attribute as well. So when you calculate the length, it's usually an O(1) lookup.
For the OP's solution, the final list can be a deque (double ended queue) where appends and deletions on the ends (0 and n-1 index) is optimised for O(1) times.
queue = deque(final_list) would work - and queue.appendleft() and queue.popleft() will be O(1).
Hope this helps
I am a 2020 grad grinding on DSA to get into product based companies and your videos work like magic!
I am 2020 grad too grinding leetcode to get out of service company I end up in. If you are not aware try Striver's SDE sheet, I found it very helpful.
@@nidhishprasad2506 yes striver's sheet really helps
I m 2023 grad, i thought it's too late for me.
But you guys motivated me today. Thanks, and best wishes.
@@raunakgiri21 Thanks! I am glad you know it early enough. Tier 3 college + service company is just worst combination for your career.
@@raunakgiri21 +1
Gist of the logic used:-
1. We're creating a list to store all the negative elements of a current window. At a particular point of time, the list holds negative numbers which are there in the current running window and not all the negative elements in the array. So, that we can retrieve first negative number from the current window.
2. When we reached the window size, we need to perform two operations:-
-> First, we have to retrieve the answer that is the first negative number from the current window. We're checking if the list is empty or not. If it is empty, then there is no negative number in the current window. In that case we'll push 0 in the vector.
If it's not empty, then the first element in the list is the first negative number of the current window., pushing that into the vector.
-> Second, we need to slide the window. For that we need to remove the first element of the current window, and add the next element from the array to the window. But before removing the first element, we need to check whether it belongs to the list or not. If it belongs to the list, we need to remove it from the list, as it will not be a part of our next window. So, if the first element is found to be a negative number, then we have to remove it from the list, and this number is happened to be the front element of the list. Then, incrementing the values of i and j to slide the window.
Thanks for the explanation....really helped!!!
thank you😃
Wonderfull() ++;
@@741ibrahim2 Thanksss
@@kirtikhohal5025 💜✨✨
public class SlidingWindow2 {
public static void main(String[] args) {
System.out.print("inter array size n > ");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("enter arr values > ");
for(int i=0;i
Verrrrry Good Solution
In Case you want code:- vector printFirstNegativeInteger(long long int A[] , long long int N, long long int K) {
int start=0,end=0;
deque ans;
vector res;
while(end < N){
if(A[end] < 0){
ans.push_back(A[end]);
}
if(end-start+1 < K){
end++;
}
else if(end-start+1 == K){
if(ans.size()==0){
res.push_back(0);
}
else{
res.push_back(ans.front());
if(A[start]
Thankyou bhai❤️
if(A[start]
@@tennetisaisarath2349 this condition is for removing the i th element. If the i th element is the one in the front of the list (i.e it is a negative number) then it will be removed. In other case the i th element may be positive and not in the list then we dont have to do anything.
@@tennetisaisarath2349 if should be like : if(ans.front() == A[i])
{
ans.pop();
}
because while removing element from our queue we have to compare it with element of start of array
Sir please upload more videos under this playlist soon.
We cant wait for such amazing content you have been putting.
I tried implementing in Python and seems correct what sir has explained.
def firstNegativeNumber(arr, n, k):
start = 0
end = 0
neg_nums = []
result = []
#start till end pointer is less then n
while end < n:
#If we found negative then add it to neg num list
if arr[end] < 0:
neg_nums.append(arr[end])
#increase end pointer till we did not reach window size
if((end - start + 1) < k):
end += 1
#if window size
elif ((end - start + 1) == k):
#check that list of neg nums greater then 0 then add first element
if len(neg_nums) > 0:
result.append(neg_nums[0])
#to remove all calc check first element with start pointer
if arr[start] == neg_nums[0]:
neg_nums.pop(0)
else:
result.append(0)
start += 1
end += 1
return result
arr = [12, -1, -7, 8, -15, 30, 18, 28]
n = len(arr)
k = 3
ans = firstNegativeNumber(arr, n, k)
print(ans)
This is really good.. but pop(0) is also O(n).. can we use 2 pointers here for this queue..
Great explanation.
BTW, this can be solved without using queue(or any other DS), if we slide the window from right to left.
GFG sol :
vector printFirstNegativeInteger(long long int a[],
long long int n, long long int k)
{
vector ans;
int i = n-1, j = n-1;
int neg = 0, ind=n;
while(i>=0){
if(a[i]
But the time complexity matters when you submit the code in geeksforgeeks. Hence the queue.
@@UdayKumar-ye8th complexity to same hai dono ki ek hi baar traverse kra hai bhay
Awesome
These are best videos in the world, I am a mechanical background candidate trying to learn algorithms. Trust me I have watched all videos in the youtube trying to get the logic. But none of them as clear as these. You are a AlgoGod. Thank you so much for the videos.
I am a civil engineering graduate. As you are from mech and learning algorithms just like me, Can i know what are you doing now. Your replies helps me a lot🙏🙏
@@predatorgaming895 Hi i too belong civil Engineer now i am working as an Associate software engineer at MNC Virtusa
@@nirobkrdas9210 which batch bro?
@@predatorgaming895 2019
it tookstwo days to do the problem by myself . i know its so long days but i'm enough confident that i can do any problems of such type
thank you bhaiya
you have given so much that I have to make strategy to watch your vdos
bro u are amazing, I have learned so much and it's all thanks to you. Can you please make a series on backtracking as you told us after this. We are eagerly waiting for it. And thanks for this amazing content.
Welcome backkkk!!!!!! I thought u were gonna gift us backtracking series with your comeback … Nevermind we will be waiting :)
That would have been funny XD
Please don't tell @niveditha, You are still waiting!
@@avinashmodi5230 Hahaha.. I have graduated in 2021. Hope he at least release backtracking series for my first job switch
@@niveditha-7555 which conpany
your way of explanation is at another level !
Sir big fan of yours..... you're god ....best teacher I have ever seen for coding......❤️❤️❤️👑👑👑👑
Truly speaking , wonderful explanation you have given .
No words to express your teaching level
You are just amazing
This can be solved using many DS.
Iterate from back and push negatives element indices in stack
Iterate from start and do same with a queue
Or you can use a deque
Normal queue
PLEASE also teach Tree and Graph.......I just loved your all DP-50 Videos........I'm working professional and Preparing for DS & ALGO.
yess bro i received it..
and really bhai jitnaa baannaa sakte ho vidoes baanaa de bhai tu ...
dec se interviews hai
plzzzz bhai lgwa do khi bhi placements
We can use dequeue also !!! As we are requiring only insertion deletion operation and can be done in O(1) time....!
Sir your way of letting us understand is really very good...
Aa gayi baat samajh me ! Behtareen tarike se samjhaya, Bahut Bahut Dhanyawaad Guru Ji !
concept smajh k khud se code kr liya...thanks bro
Hello bhaiya, I know that it's difficult for you to take your time out to make these videos but still I request you that if it's tougher to start a new series like backtracking, then please complete the DP playlist so that we know all the variations of it and are fully comfortable in it. No one anywhere taught DP better than you.
Nobody can spoon-feed you every single thing.You need to start doing questions after completing the xisting dp playlist.Its enough for you to get a basic understanding.
@@soumilmaitra9466 buddy it was just a minor request to him. More about the pattern recognition in questions, as his insights are very helpful. Please don't comment if you don't have anything constructive to add and next time understand the intention behind a request just don't barge in and act like a bigger person.
@@soumilmaitra9466 toxic af
@@soumilmaitra9466 Gyaan chodne wale bahot hai bc
@Ujjwal Gupta plz send the link....🙏
Bhaiya yaar plz...greedy...backtracking...graph😔
😢
Still waiting for that SPECIAL thing u are working on... btw great job
Thank you so much for your efforts, you are really a life saviour. I know it must be hard for you to take out time for this but please can you upload playlists for backtracking, greedy algorithms, graphs, strings etc. Or if that's not possible can you just provide the base/parent questions for each topic so that atleast we can follow the approach you taught us in those questions also. I know I'm asking for a lot but we'll be really grateful if you can do that.
yes.. we need videos for these topics too
Thanku bhaiya for such a crisp and clear explanation
Instead of vector use a queue , remove and adding is O(1) even if window size is big
Sir your videos are so intuitive that i never have to see code.
Hello Aditya! I tried writing a brute force for the first negative number. But I feel even after implementing 2 loops, my code doesn't do a repetitive checking of elements for their negativity. I am wondering if it's a brute force... Following is my code:
public static int[] FirstNegativeInEveryWindow_BruteForce(int[] numList, int windowSize)
{
//Input => 12, -1, -7, 8, -15, 30, 16, 28
//Output => -1, -1, -7, -15, -15, 0
List returnList = new List();
for (int start = 0; start
sir printing permutations of a string when we have duplicate character kaise kre if for non duplicate it is solvable for me
Simple solution in python:
def slide2(a,k):
q=[] # empty queue
i=j=0
while j
🔴🔴🔴🔴🔴🔴
MAY YOU PLEASE DISCUSS THE TIME COMPLEXITY FOR SOLUTIONS IN UPCOMING VIDEOS! IT WOULD BE HELPFUL AS REST OF THE CONTENTS ARE.
🔴🔴🔴🔴🔴🔴
finally, i was waiting for it
Thank you very much. You are a genius.
Best explanation ever 👍❣️
ap insaan nahi god ho coder ke liye
thanku so much bahiya
Great explanation Thanks. I think storing index in the Queue would be better than storing the Element as we can handle Duplicates Also.
also why is there need to check if arr[i]==l.front(). just check if num
@@hasansyed1004Also this condition can fail when the last element is the First negative it will not add that element or remove it.. I didn't understand this logic of comparing worth first element of window
This series is addictive !
I have one question, why do we have used another vector for a final answer since in the list we are storing all the -ve numbers so can't we just return the list itself
very nice explanation thank u so muchh
Bro, please make Graphs' playlist now, I think everyone is waiting for it more than any other topic, after watching the DP series, and it is the placement season as well so it will be very handy for us if you can make it now asap.
how was ur placement bro??
Thank You bhaiya................
Window set krne ke baad calculations thodew alag he ise easy calulations ho sakta he kya ??
Great Explaination man LOVE LOVE LOVE
we donot even need extra space !!! please always show the most efficient solution
Great explanation 🔥🔥
Sir will you be coming up with Two Pointer playlist ?
Sir please cover the remaining dp problems
Javascript implementation for this question
function negativeNumber(arr, k) {
let i = 0,
j = 0,
list = [],
ans = [];
while (j < arr.length) {
if (arr[j] < 0) list.push(arr[j]);
if (j - i + 1 < k) j++;
else if (j - i + 1 === k) {
ans.push(list[0] || 0);
// If the first negative number is at the leftmost position, remove it from the list
if (arr[i] === list[0]) list.shift();
j++;
i++;
}
}
return ans;
}
console.log(negativeNumber([5, -2, 3, 4, -5], 2));
ls.pop_front() time comp. is n ..so total tc would be n*n ..what's the point of using sliding window then
Bhaiya.... R u planning for backtracking.., if u see do let us know
Bhaiya nice video, but really missing your pen and paper explanation 😘
Please upload more video as soon as possible.
i think using queue here is also a great decision like having all negative values in window are in queue and as per window changing it will also changes
solution :-
vector printFirstNegativeInteger(long long int A[],
long long int N, long long int K) {
vectorans;
dequelist;
long long i=0,j=0;
while(j
sono sharingan omaewa doko mate mereiteru !!!!
@@malkeetsapien4852 wow Japanese sardaar?
Arigato Na ! Itachi of the Sharingan !
@@malkeetsapien4852 回溫觀念不同程度不同飽腹代餐餅干
thanks bro
In the scenario where the numbers are repeating in itself, it might be possible that the negative number matches and then the answer might get removed from the queue.
public long[] printFirstNegativeInteger(long A[], int N, int K)
{
//n of sliding window will made in array length N is (N-k+1)
int size=N-K+1;
long[] res= new long[size];
int p=0;
ArrayList neg=new ArrayList();
for(int i=0;i
Sir please make video on graph data structures
welcome back brother....! i am facing issue regarding revising the previous questions like if i complete array section today and look at same questions after 15 days i will forget the approach how i solved it that time! how to do that.
and moreover i am facing confidence issue like suppose i go for interview and suddenly interviewers asks question how to remeber so many approaches for 1 question like first we need to do in O(n^2) then bring it down to O(n) or something i mean there are multiple approaches for 1 question and combine it with 500 questions. total approaches = 500*3 = 1500, it is lot to remember
@@CasanovianKing don't just solve the problem and move on also make sure you don't look at the solutions immediately. Try to spend time thinking at problem and solving in notebook or something, try to come up with various approaches and find their complexities and it will take time so don't lose hope. happy coding!!!
@@vaibhavsaharan7898 but imagine you are preparing array topic and you find that question is tagged in array section because of O(n^2) approach and a stack based approach is of O(n) which the interviewer is going to ask in the end so how my brain gonna switch and think suddenly in between array questions to apply stack!!!
@@CasanovianKing bro kaisa gya interview
i am also in same state as you were
welcome back sir
now our expectations have increased we want this tyoes of vdos on every ds like first identification then some famous prblms this approach is lit
thaank you bhrata :)
Code of GFG question -
vector printFirstNegativeInteger(long long int A[], long long int N, long long int K) {
queue q;
vector ans;
long long i = 0,j = 0;
while(j
can anybody tell me the name of the song that he is using in the start and end of the vedio
why don't we consider time complexity for popping the first element from list or queue. If we consider that then for array with all negative integers we need to pop from list for every sliding step. So time complexity becomes O(nk) because time complexity for removing front element from list is o(k)
No, time complexity for adding element in the end of the list and deleting element from the front of the list is O(1), constant time and not O(K).
Can we just iterate for loop from 0 to (len-k) and print negative number ....?
If a -ve element is present in more than one window then how it'll be printed.. coz if you run just a loop , it simply print all -ve no once . Hope you got it !
NICE SUPER EXCELLENT MOTIVATED
Thanks aditya boss
Never thought someone could make coding so easy
class Solution:
def solve(self,arr,k):
i,j,=0,0
ans=[]
q=[]
while j
Bro, when you will be taking care remaining 8 questions 👍
Thank you so much...
please share the brute force code as well
Without credit card..how can we make payment in patreon??
pls tell
It would have been a lot better if you had posted a screenshot of a working code at the end.
Boss , Bahut dino baad lecture aaya
Love you bhai, aise gayab mat hojaaya karo
Complete Java code:-
static ArrayList list=new ArrayList();
public static void main (String[] args) {
Scanner s1=new Scanner(System.in);
int T=s1.nextInt();
while(T>0){
int N=s1.nextInt();
int arr[]=new int[N];
for(int i=0; i
what is T?
@@greenergrass1371 testcases
please put complete code on some github page , this will be helpful.
Please work on Graphs and Trees
Excellent.
Sir please write full codes on the screen as well while teaching for the people who can't join Patreon, like you used to do earlier
bro u can easily find the code from the comment box
vector printFirstNegativeInteger(long long int A[],
long long int N, long long int K) {
vectorans;
int i=0;
int j=0;
queueq;
while(j
@@vikashkumargupta4792 Thank you
At 29:27 instead of writing this we can also write
if(arr[i] < 0) list.pop_front()
Since i represent the start of window and if it is negative then it will be the first negative of current window in that case it will be present in the front of the list
So by directly checking the above if arr[i] < 0 we can directly remove the arr[i] from the list
Bhaiya please upload graph, greedy and backtracking also
Bohot jyada hi detailed explanation hai bhai 🥱
should have used queue , the push and pop takes only O(1)
thnx for this video
Wat an explanation!! Anyone can understand this kind of explanation...
bro , iska similar que ka leetcode ka link dedo please
if you use sliding window from end you don’t need extra queue.?
how?
code of the problem
#define ll long long
vector printFirstNegativeInteger(long long int A[],
long long int N, long long int k) {
queue q ;
ll i =0, j =0 ;
vector sol ;
while( j =k )
{
if(q.size() == 0) sol.push_back(0) ;
else
{
sol.push_back(q.front()) ;
if(A[i] == q.front()) q.pop() ;
}
i++;
}
j++ ;
}
return sol ;
}
Java solution but we traverse from the back..The idea is to replace the previous negative value if we find a new one as we do not need to keep the negative values that are to the left side of first naegative value.And now when i crosses this index we will reset the pair val to 0 and index to j.
class Compute {
public long[] printFirstNegativeInteger(long arr[], int n, int k){
int i = n-1 , j = n-1;
long[] ans = new long[n-k+1];
int len = ans.length-1;
pair pr = new pair(0,j);
while(j >= 0){
if(arr[j] < 0){
pr.val = arr[j];
pr.key = j;
}
if(i-j+1 == k){
ans[len] = pr.val;
i--;
j--;
len--;
}else{
j--;
}
if(pr.key > i){
pr.val = 0;
pr.key = j;
}
}
return ans;
}
}
public class pair {
public long val;
public int key;
public pair(long val, int key) {
this.val = val;
this.key = key;
}
}
try to dry run the code on a paper and try to understand the solution.
i have a doubt
in array 3, -1, -5, 6, -4, 9, 10
k=3
In first window, 1st -ve number is -1,
In second window also, 1st -ve number is -1
I want to put whatever 1st -ve number
How to do using sliding window.
So the time complexity is o(n) and space complexity is o(k)
Can we use queue instead of arraylist? @Aditya Verma
Yes we can use queue, but there also space complexity is O(n) - worst-case in which all the elements are -ve
@@bestsaurabh we keep removing elements from queue as we slide window so number of elements in the queue can be atmost K at any time
@@tejaswigutta9017 yes you are right!! It will be O(k)
Hey bro. A small suggestion, please try to minimise your video length. 32mins for a sliding window problem is too much.
what if the array is 1 2 -3 4 -5 7....the negative element would be -3 -3 -3 -5...so how to print -3 three times ?
hello shreya , what we will do is we will not pop the element from the queue until it is equal to a[i] which is 3 in this case (so eg for case like 1 2 -3 it pushes -3 when we find 1 is positive and then for 2 if finds out it is positive we again push 3) and also we will push a[i] inside the vector if it is negative(to cover the case -3 4 -5).....hope you understood my logic... if not i can share the code if you want
@@devendunegi247 yes please share the code
@@devendunegi247 thanks you bro I was also dealing with the same problem 🙂
@@utkarshraj5475 static int firstneagtive(int arr[], int k) {
int i = 0;
int j = 0;
ArrayList arrli = new ArrayList();
while (j < arr.length) {
if (arr[j] < 0) {
arrli.add(arr[j]);
}
if (j - i + 1 < k) {
j++;
} else {
if (j - i + 1 == k) {
if (arrli.size() == 0) {
System.out.println(0);
} else {
System.out.println(arrli.get(0));
if (arr[i] == arrli.get(0)) {
arrli.remove(0);
}
}
}
i++;
j++;
}
}
return 0;
}
Is there anyone who's having complete notes for this and binary search playlist
great video
Code using sliding window + queue:
#include
using namespace std;
int main()
{
vector a = {12,-1,-7,8,-15,30,16,28};
int k = 3;
int n = a.size();
vector ans;
queue q;
int left = 0;
int right = 0;
while(right