KEMBAR78
Arrays Medium Part2 | PDF
Scribd
Upload
97 views3 pages

Arrays Medium Part2

The document contains revision notes on various array algorithms from the Striver A2Z DSA Sheet. It discusses approaches for problems such as buying and selling stocks, rearranging elements by sign, and finding the next permutation, detailing their time and space complexities. Each problem is approached with multiple methods to optimize performance.

Uploaded by

n200677
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
97 views3 pages

Arrays Medium Part2

The document contains revision notes on various array algorithms from the Striver A2Z DSA Sheet. It discusses approaches for problems such as buying and selling stocks, rearranging elements by sign, and finding the next permutation, detailing their time and space complexities. Each problem is approached with multiple methods to optimize performance.

Uploaded by

n200677
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Revision Notes of Striver A2Z DSA Sheet

Arrays – Medium Part 1.2.2

1. Buy and Sell stock


Approach 1:- Calculate all possible differences, keep a maxprofit variable keep updating it
when you find a great difference. TC:-O(N2) SC:-O(1)
Approach 2:- Keep checking profit, it it becomes negative- update the buyingdate to the
lesser no, keep a maxprofit variable and update it when you find a bigger profit. Tc:- O(N)
SC:-O(1)

Approach 3:- Keep checking the minprice(min ele in array) and check profit for that. Have a
maxprofit variable and check for ele after the minprice. TC:- O(N) SC:-O(1)

VANSHIKA MISHRA 1
Revision Notes of Striver A2Z DSA Sheet

2. Rearrange the elements in array by sign


Approach 1:- make a positive array , make a negative array add ele to them in order. Then
create an ans array and put positive negative ele in it one by one. TC:- O(N) SC:- O(N)
Approach 2:- create an ans array, put postitive ele in positive indices in ans array, and put
negative ele in negative indices ans array. TC:- O(N) SC:-O(N)

3. Next Permutation
Approach 1 :- Find all the permutations then search the input and return the next one. TC:-
O(N!*N) SC:- O(1)
Approach 2:- Find the break point(jidhar se ele ko swap karne se aur badi array mil jayegi). To
find the break point we will the array backward and store the ele where the valu of
arr[i]<arr[i+1]. Breakpoint nhi mila toh yahi max hai bhai reverse karke bhejdo)Agar break
point mil gaya toh breaking pt se leke end tak min number doondho aur use swap kardo. Fir
pure right half ko reverse kardo. TC:-

VANSHIKA MISHRA 2
Revision Notes of Striver A2Z DSA Sheet

Dry run :-
2 1 5 4 3 0 0
Breakpt=

Next smallest no is 3 if we swap 1 and 3 we get 2 3 5 4 1 00

Reversing the right half we will get 2 3 0 0 1 4 5 which is indeed the answer

VANSHIKA MISHRA 3

You might also like