Nearest Smaller Tower || POTD || Problem of the Day || GFG || 24 April '23 || Medium Problem

Join FastForward Coders Community 🔥

GFG Problem Link -

Here we will discuss the GeeksforGeeks Problem based on the Stack Data Structure with ✅ Optimised Approach, 🧠 Intuition, and 👩‍💻Live Coding.

🤙 Connect with me -

TimeStamps -
00:00 Question Discussion
03:06 Intuition
09:49 Optimised Approach
19:31 Live Coding with Explanation
25:27 Time Complexity & Space Complexity

[FastForwardCoders]

Please Like 👍, Share and Subscribe ❤if you really find my explanation helpful.

[manojkr]

bro this approch when did you got when seeing the question or refering some notes

[Shujaathullakhan]

won't we consider prev and next vector for space complexity?

[tanyaarya]

which software u use to write with pen here?

[soumikroy]

class Solution{
int [] nearestSmallestTower(int [] arr){
//Write your code here
int n = arr.length;
Stack<Integer> st = new Stack<>();
int[] left = new int[n];
int[] right = new int[n];
left[0] = -1;
st.push(0);

for(int i=0; i<n; i++){
while(!st.isEmpty() && arr[st.peek()] >= arr[i]){
st.pop();
}

if(st.isEmpty()){
left[i] = -1;
st.push(i);
}else{
left[i] = st.peek();
st.push(i);
}
}

st.clear();
st.push(n-1);
right[n-1] = -1;

for(int i=n-2; i>=0; i--){
while(!st.isEmpty() && arr[st.peek()] >= arr[i]){
st.pop();
}

if(st.isEmpty()){
right[i] = -1;
st.push(i);
}else{
right[i] = st.peek();
st.push(i);
}
}


int ans[] = new int[n];

for(int i=0; i<n; i++){
if(left[i] == -1 && right[i] == -1){
ans[i] = -1;
}else if(left[i] != -1 && right[i] == -1){
ans[i] = left[i];
}else if(left[i] == -1 && right[i] != -1){
ans[i] = right[i];
}else{
int distanceOnLeft = i - left[i];
int distanceOnRight = right[i] - i;
if(distanceOnLeft < distanceOnRight){
ans[i] = left[i];
}else if(distanceOnLeft > distanceOnRight){
ans[i] = right[i];
}else{
if(arr[left[i]] < arr[right[i]]){
ans[i] = left[i];
}else if(arr[left[i]] > arr[right[i]]){
ans[i] = right[i];
}else{
ans[i] = left[i];
}
}
}
}

return ans;
}
}

[maritime_business]

11:36 how did you come to conclusion that 8 will never be of use so just put 3 in stack...you just said that we dont have to find the smallest neighbor element ! we have to find the closest smaller element so now why are you removing 8 by saying it will never be of use because 3 can do whatever 8 can do. what if there is a sequence where 8 is closer to 10 and 3 is far away ?? I dont get it and again how can method of comparing and storing index twice from right and left of stack gives answer ? how did you get that intuition....kaafi din se tutorials dekh rha par boht confusing explanation that aaj ka !