what is time and space complexity for this code: vector<int> nsl(vector<int> arr,int n){…
- User
what is time and space complexity for this code: vector nsl(vector arr,int n){ stacks; vectorv; // int pseduoindex=-1;
for (int i = 0; i < n; i++) { if (s.size()==0) { v.push_back(-1); } else if (arr[s.top()]<arr[i]) { v.push_back(s.top()); } else { while (s.size()!=0 and arr[s.top()]>=arr[i]) { s.pop(); } if (s.size()==0) { v.push_back(-1); } else { v.push_back(s.top()); } } s.push(i); } return v;}
vector nsr(vector arr,int n){ stacks; vectorv(n);
for (int i = n-1; i >=0; i--) { if (s.size()==0) { v[i]=n; } else if (arr[s.top()]<arr[i]) { v[i]=s.top(); } else { while (s.size()!=0 and arr[s.top()]>=arr[i]) { s.pop(); } if (s.size()==0) { v[i]=n; } else { v[i]=s.top(); } } s.push(i); } return v;}
int getMaxArea(vector arr, int n) { vector right=nsr(arr,n); vector left=nsl(arr,n); vector width(n);
for (int i = 0; i < n; i++) { width[i]=right[i]-left[i]-1; } int maxArea=INT_MIN; for (int i = 0; i < n; i++) { int area= arr[i]*width[i]; maxArea=max(area,maxArea); } return maxArea;}
int maxArea(int M[MAX][MAX], int n, int m) { vector v; for (int j = 0; j < m; j++) { v.push_back(M[0][j]); }
int ans=getMaxArea(v,v.size()); for (int i = 1; i < n; i++) { for (int j = 0; j < m; j++) { if (M[i][j]==0) { v[j]=0; } else { v[j]=v[j]+M[i][j]; } } ans=max(getMaxArea(v,v.size()),ans); } return ans;}
- Assistant
The time complexity for this code is O(nm), and the space complexity is O(nm).
Here's the breakdown:
-
In the getMaxArea() function, the nsr() and nsl() functions are called, both of which have a time complexity of O(n) due to the for-loop. Since these loops don't intersect and they are executed consecutively, their combined time complexity is still O(n).
-
The getMaxArea() function itself contains several for-loops, but since they don't intersect (i.e., they are not nested), their combined time complexity is also O(n).
-
In the maxArea() function, there are nested loops: one iterates 'n' times and the other 'm' times. And since getMaxArea() is called inside the nested loop with combined time complexity O(n), the total time complexity becomes O(n*m).
In terms of space complexity, the code uses several vectors (v, right, left, width) which can have at most 'n' elements each, and the getMaxArea() function is called inside a nested loop 'm' times. Therefore, the space complexity is also O(n*m).
-