Next greater element in an array
Given an array of integers(positive or negative), print the next greater element of all elements in the array. If there is no greater element then print null.
Next greater element of an array element array[i], is an integer array[j], such that
1. array[i] is less than array[j]
2. i is less than j
3. j - i is minimum
i.e. array[j] is the first element on the right of array[i] which is greater than array[i].
Algorithm 1 (Naive):
For every element, iterate over array elements on the right to find the first element which is greater than the current element.
If the end of array is reached, then next greater element for the current element is null.
Time Complexity: O(n^2)
Space Complexity: O(1)
Algorithm 2 (Optimized):
Traverse the array once.
1: If the stack is empty or array[i] is less than stack.top, push the array[i] on the stack.
2: While array[i] is greater than stack.top,
Pop top element & print 'Next Greater Element of top is array[i]'.
3: Push array[i] on the stack.
4: Repeat steps 2-3 till the end of array is reached.
5: Finally, print null as next greater element for all remaining stack elements.
Time Complexity: O(n)
Space Complexity: O(n)
Code and Algorithm Visualization: http://www.ideserve.co.in/learn/next-great-element-in-an-array
Website: http://www.ideserve.co.in
Facebook: https://www.facebook.com/IDeserve.co.in
Видео Next greater element in an array канала IDeserve
Next greater element of an array element array[i], is an integer array[j], such that
1. array[i] is less than array[j]
2. i is less than j
3. j - i is minimum
i.e. array[j] is the first element on the right of array[i] which is greater than array[i].
Algorithm 1 (Naive):
For every element, iterate over array elements on the right to find the first element which is greater than the current element.
If the end of array is reached, then next greater element for the current element is null.
Time Complexity: O(n^2)
Space Complexity: O(1)
Algorithm 2 (Optimized):
Traverse the array once.
1: If the stack is empty or array[i] is less than stack.top, push the array[i] on the stack.
2: While array[i] is greater than stack.top,
Pop top element & print 'Next Greater Element of top is array[i]'.
3: Push array[i] on the stack.
4: Repeat steps 2-3 till the end of array is reached.
5: Finally, print null as next greater element for all remaining stack elements.
Time Complexity: O(n)
Space Complexity: O(n)
Code and Algorithm Visualization: http://www.ideserve.co.in/learn/next-great-element-in-an-array
Website: http://www.ideserve.co.in
Facebook: https://www.facebook.com/IDeserve.co.in
Видео Next greater element in an array канала IDeserve
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Programming Interview Question: How to print all diagonal's sums for a given binary tree?Level Order TraversalReverse a Linked List - IterativeProgramming Interview Question: Searching a 2D Sorted MatrixImplement a fair coin given an unfair coinBuying and selling stocksBinary SearchMinimum length subarray of an unsorted array sorting which results in complete sorted arrayMaximum size square sub-matrix with all 1sBuilding Bridges Dynamic ProgrammingLeaders in an arrayFind intersection of two Linked Lists - O(A + B) Time Complexity and O(1) Space ComplexityCreate a balanced Binary Search Tree (BST) from a sorted arraySpiral level order traversal of a binary treeProgramming Interview Question: Recover Binary Search TreeDetect a loop in a linked listProgramming Interview Question: Find intersection of two Linked ListsFind an element in a sorted rotated arrayDemo of IDeserve web platform www.ideserve.co.inLowest Common Ancestor