SDE - 1

The idea here is to use the pow function to find N raised to the power M. After finding the power, we start removing the digits from the last until we get the kth digit.

• Create a long long int variable to store the power named as temp. Note that the value of N and M can go up to 15, which means N^M may not fit in the int. So, we have created a long long int type variable.
• Make temp = pow(N,M).
• Create an int variable to store the current digit place from the right named as cnt. Initialize it to 0.
• Create an int variable called ans to store the answer. Initialize it to 0.
• Run a while loop till temp > 0, here we are planning to iterate through the digits of the temp from right to left by using %10 (temp % 10 will give the last digit of temp) :
  • Find the last digit, lastDigit = temp % 10.
  • Increment the cnt by 1.
  • If cnt == K, which implies that we are at the Kth digit so, set ans equal to lastDigit and break the while loop:
  • Otherwise, we have to remove the last digit. So, just divide temp by 10,    temp /= 10.
• Finally, return the variable ans.

Approach (Naive): 

1) Store the coordinates and heights of the buildings paired up with each other with the first building coordinate paired after taking negative of the height and the second coordinate with positive height in a list ‘POINTS’.

2) Now, sort edges present in the ‘POINTS’ list (array) in ascending order.

3) The positions are now sorted from left to right, small to large. Now, initialise a dictionary named 'HEIGHTS' with zero as its first key, having a value of 1 since this would be the last height that would be added.

4) Now, for each pair of an edge in the ‘POINTS’ list (array) and check:
4.1) Update the dictionary if the current edge is a start edge (with negative height) increment the value 
of the key by 1.
4.2) Delete the invalid buildings from the dictionary if an end edge is encountered for a key after 
decrementing its value by 1.
4.3) Now, In each iteration update the 'SKYLINE', which records the highest building from some 
position, and add it to the final list of our 'SKYLINE's if the current highest is no longer the tail of the 
'SKYLINE' (previous highest).

5) We finally return the 'SKYLINE' list (array) that we have formed.


In the test , I could only figure out a O(N^2) solution and hence it gave TLE in the last 5 Test Cases. I later found out a O(N*log(N)) solution which could have passed all the test cases.


Approach (Efficient) :

1) Sort edges with [POSITION, -HEIGHT, VALID_UNTIL]. Here, the first two elements are for iterating edges with the correct sequence, while, the last one is for popping out invalid buildings during the iteration.

2) The positions are now sorted from left to right, small to large.

3) When positions are overlapped, sort the height from high to low, large to a small image

4) Now, for each edge:
4.1) Pop-out invalid buildings from the top of the heap (there might still exist invalid ones in the heap, but 
we just want to make sure the top of the heap is valid).
4.2) And update the heap if the current edge is a start edge
4.3) In each iteration update the 'SKYLINE', which records the highest building from some position, if the 
current highest is no longer the tail of the 'SKYLINE' (previous highest).

5) We finally return the 'SKYLINE' list (array) that we have formed.

Approach :
1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not and
initilialise a variable ans=1 which will store the final answer.

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome ) .

3) Now, run 2 loops first one from i=n-1 to i=0 (i.e., tarverse from the back of the string) and the second one from
j=i+1 to n .

4) For every s[i]==s[j] , check if(j-i==1 i.e., if s[i] and s[ j] are two consecutive same letters) or if(dp[i+1][j-1]==1 or not
i.e., if the string s[i+1,....j-1] is palindrome or not .

5) Because if the string s[i+1,....j-1] is a palindrome and s[i]==s[j] then s[i] and s[j] can be appended at the starting
and the ending position of s[i+1,...j-1] and s[i...j] will then be a palindrome , so mark dp[i][j]=1 and update the answer
as ans=max(ans , j-i+1).

6) Finally return the ans

TC : O(N^2) where N=length of the string s
SC : O(N^2)

In this question too , my code could only pass a few Test Cases . The constraints were quite tight.
I later found out that there is also a O(N) approach to this problem using Manacher's Algorithm but it was quite complex.