Greater Element I


  • 0

    Click here to see the full article post


  • 0
    F

    I'd like to say that these videos would be much more useful if we could play them step by step like a diaporama, at our own desired speed. Right now they require to totally understand the algorithm to be followed, which defeat their purpose. That would be a major argument for me to keep premium. I hope other people could step in! (Or at least give us the different pictures or anything that is simple enough for you to do)


  • 0

    @floribon Thanks for your idea. We will try to add this feature asap.


  • 0
    S

    I would like to see at least a pause button on the animation.


  • 0
    Y

    stack solution is really wonderful!


  • 0
    A

    @floribon I completely agree. It was really hard for me to follow what was happening. There should be a next button which should allow the user to go to the next step.


  • 0

    I have replaced the gif with the slide show containing next/previous button. Enjoy :)


  • 0
    I

    Nasty typo here: "We push every element nums[i] on the stack if it is larger than the previous element on the top of the stack". This should be "if it is less than the previous element on the top of the stack."


  • 0

    @isaackleinman You are right. I have corrected it. Thanks.


  • 0
    G

    Is the space complexity of second method is O(m+n)? Since the size of the hashmap is n which is the length of nums.


  • 0

    There's a way to do it in O(m+n) time and O(m) space to avoid using the stack. I posted my solution and analysis here: https://discuss.leetcode.com/topic/118140/amortized-o-m-n-in-time-without-using-stack


  • 0
    P
    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] answer = new int[nums1.length];
            
            Map<Integer,Integer> map = new HashMap<>();
            for (int i=0;i<nums2.length;i++){
                map.put(nums2[i],i);                                    
            }
            
            for (int i=0;i<nums1.length;i++){
                int temp = map.get(nums1[i]);
                boolean check = false;
                if (!map.containsKey(nums1[i]) || temp == nums2.length){
                    answer[i]=-1;
                }
                else{
                    
                    for (int j=temp;j<nums2.length;j++){
                        if (nums2[j]>nums1[i]){
                            check = true;
                            answer[i]=nums2[j];
                            break;
                        }
                        
                    }
                    if (!check){answer[i]=-1;}
                }                        
            }        
            return (answer);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.