Final 450 challenging problems.
1. Longest consecutive subsequence
https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence2449/1
observation:
-> for every element I will check if the element-1 is present in the map
-> 2 cases:
if present:
means that current is not the first element
otherwise
current is the first element in the sequence.
-> if found as the first element, then we will check till what the consecutive is found, from element+1
->return the maximum.
Overall Tc: O(n), space: O(n).
2. Count More than n/k Occurences
https://practice.geeksforgeeks.org/problems/count-element-occurences/1#
Observation
-> potential element will be k-1
-> take an array of k-1 length which should have count and value info
-> for every element in arr[] maintain the k length array[Tc:O(n*k)]
two cases:
if the element in the k-1 length array is exceeding its length,
then decrement the count of every element in the k-1 length array and ignore the current element
otherwise
insert the element and update its count in the k-1 length array
->at the end, we will have all the potential k-1 or fewer elements from the original array
-> for every potential element we have to check for its count in the original array. [Tc:O(n*k)]
Overall Tc: O(n*k), space: O(k).
3. Maximum rectangular area in the histogram
https://practice.geeksforgeeks.org/problems/count-element-occurences/1#
Observation
-> Take a stack
-> in the beginning when the stack is empty simply push the first element from the array to the stack
-> After that, whenever you push any other element to the
stack, you had to make sure that the top element of the stack should be lesser than the current element.
-> If the top element is greater simply relax the stack by popping out the top element from the stack and also updating the max area while popping.
-> we can have a separate function for relaxing the stack, there we will give three parameters as input ie. the stack, array and the index element which we are considering.
->inside the function when we pop the top element from the stack, there arise two conditions:
-> stack is empty,
in this case, we will return the value of the current element times the width which is the index element that we have considered.
-> otherwise,
we will return the value of the current element times the which is (index considered -1 -top of the stack)
-> at the end, we will relax the stack by taking the considered
element as the length of the array.
Overall Tc: O(n), space: O(n).