We can also use a "Decreasing monotonic double ended queue". Start iterating from the begining of the array, => If there is no element in the deque, append the element => If the element is smaller than the last element of deque, append it => If the element is bigger than the last element and if there is only one element, no need to add it to the queue => if the element is bigger than the last element and if there are more than one element in the queue, start from the start of queue and delete the elements in the queue if queue[i] < curElement until there is one element left in the queue => In this case dont append the curElement, as it is already bigger than the last element in the queue(As the queue is monotonically decreasing) => Finally if the queue has only one element return True, else return False. Time Complexity: O(N) (at max two passes - 2*N, one to the array and one to the deque itself). Space Complexity: O(N) (in the worst case, the deque can grow larger upto size N if all the elements are in descending order). ---------------------------------------------Sample code in python-------------------------------------------------------- def can_reduce_to_single_node(arr): dq = deque() for node in arr: if not dq: dq.append(node) elif node < dq[-1]: dq.append(node) else: while len(dq) > 1 and dq[0] < node: dq.popleft() return len(dq) == 1
intution - traversing from back and finding nge through monotonic stack . there can be at max only 1 element which has not nge if it is morethan 1 then no otherwise yes
Sir cant we solve this by just mainting index of max and min element and if the index of min is to the left of the index of max ans is always possible else not possible
Can we get the next greater element of all the elements in the array, and then check how many elements don't have a next greater element. If the number is 0, 1, or 2 then YES, else NO
What i thought of was really simple [Claim] : We can check the the max_ele_idx and the min_ele_idx, if the min_ele_idx is after the max_ele_idx, the answer is always no can you suggest some counter example to prove it wrong (only if it is wrong)
Take example of [2, 5, 1, 4, 3], even though index of 5 < index of 1, we can still delete them. Take (2,5) delete 5, take (2, 4) delete 2, then (1, 4) delete 4 and finally (1,3) and delete 3
![Kumar K [Amazon]](http://yt3.ggpht.com/AC31qZhXcWFgj2sgT3X0p-b0zXqCPQ5pl10tdyr72yXkk4-MwpcMg59JZO-TySohn1QkziGf57Y=s48-c-k-c0x00ffffff-no-rj)
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
Superb teaching style 👌👌👌👌
We can also use a "Decreasing monotonic double ended queue".
Start iterating from the begining of the array,
=> If there is no element in the deque, append the element
=> If the element is smaller than the last element of deque, append it
=> If the element is bigger than the last element and if there is only one element, no need to add it to the queue
=> if the element is bigger than the last element and if there are more than one element in the queue, start from the start of queue and delete the elements in the queue if queue[i] < curElement until there is one element left in the queue
=> In this case dont append the curElement, as it is already bigger than the last element in the queue(As the queue is monotonically decreasing)
=> Finally if the queue has only one element return True, else return False.
Time Complexity: O(N) (at max two passes - 2*N, one to the array and one to the deque itself).
Space Complexity: O(N) (in the worst case, the deque can grow larger upto size N if all the elements are in descending order).
---------------------------------------------Sample code in python--------------------------------------------------------
def can_reduce_to_single_node(arr):
dq = deque()
for node in arr:
if not dq:
dq.append(node)
elif node < dq[-1]:
dq.append(node)
else:
while len(dq) > 1 and dq[0] < node:
dq.popleft()
return len(dq) == 1
Nice idea.
@kumarkdsa thank you, btw ur way of simplifying the question is amazing 🤩
@@mentanagavenkatasrinivas9245 Thankyou 😀😁
Brilliant explanation sir 🔥🔥
love you
Brilliant Kumar K sir❤🎉🎉🎉❤
love you
awesome sir 🔥
Problem 🔥🔥🔥
intution - traversing from back and finding nge through monotonic stack . there can be at max only 1 element which has not nge if it is morethan 1 then no otherwise yes
Nice idea.
We can solve it using dsu as well union by rank or size and for optimising we can use path compression
Sir cant we solve this by just mainting index of max and min element and if the index of min is to the left of the index of max ans is always possible else not possible
That does not work as explained in other comment below.
Montonic Stack possible?
Yes possible.
Can we get the next greater element of all the elements in the array, and then check how many elements don't have a next greater element. If the number is 0, 1, or 2 then YES, else NO
Great
What i thought of was really simple
[Claim] : We can check the the max_ele_idx and the min_ele_idx, if the min_ele_idx is after the max_ele_idx, the answer is always no
can you suggest some counter example to prove it wrong (only if it is wrong)
for ex [4 5 6 1 3 2 ] in the test case discused 1 was coming after 6, hence the answer is no
Take example of [2, 5, 1, 4, 3], even though index of 5 < index of 1, we can still delete them. Take (2,5) delete 5, take (2, 4) delete 2, then (1, 4) delete 4 and finally (1,3) and delete 3
@@prashantshukla133 oh thank you, i didn't think it in this way