Space Complexity(in hindi)

How to find space complexity of any program plz tell me ? i had searched this prevoius on codechef but i doesnt understand

I’m sure you didn’t googled it.

4 Likes

i had google’d but doesn’t understand

check this. If still, you can’t understand then wait for some time and then try it again.

hey bro i just want to calculate space complexity of any program would u help me

if it isn’t from an ongoing contest then post it. Maybe I’m not, but someone will help you.

“”“its an article from gfg”

// C++ implementation of the approach

#include<bits/stdc++.h>

using namespace std;

// Function to return the maximum

// water that can be stored

int maxWater( int arr[], int n)

{

// To store the maximum water

// that can be stored

int res = 0;

// For every element of the array

for ( int i = 1; i < n-1; i++) {

// Find the maximum element on its left

int left = arr[i];

for ( int j=0; j<i; j++)

left = max(left, arr[j]);

// Find the maximum element on its right

int right = arr[i];

for ( int j=i+1; j<n; j++)

right = max(right, arr[j]);

// Update the maximum water

res = res + (min(left, right) - arr[i]);

}

return res;

}

// Driver code

int main()

{

int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

int n = sizeof (arr)/ sizeof (arr[0]);

cout << maxWater(arr, n);

return 0;

}

https://www.geeksforgeeks.org/trapping-rain-water/ for both codes how to calculate space complexity

O(N) for both.

how did u calculated plz will u explain

you are storing only 1 array which could go upto size N. Everything else is constant we usually ignore it.

1 Like

ty

give a like if you got your answer :wink:

3 Likes

// SPace complexity plz calculate for me anyone with explaination

#include<bits/stdc++.h>

using namespace std;

// Function to return the maximum

// water that can be stored

int maxWater( int arr[], int n)

{

// To store the maximum water

// that can be stored

int res = 0;

// For every element of the array

for ( int i = 1; i < n-1; i++) {

// Find the maximum element on its left

int left = arr[i];

for ( int j=0; j<i; j++)

left = max(left, arr[j]);

// Find the maximum element on its right

int right = arr[i];

for ( int j=i+1; j<n; j++)

right = max(right, arr[j]);

// Update the maximum water

res = res + (min(left, right) - arr[i]);

}

return res;

}

// Driver code

int main()

{

int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

int n = sizeof (arr)/ sizeof (arr[0]);

cout << maxWater(arr, n);

return 0;

}