Algorithm: Next Greater Element I (from leetcode)

Question

can someone please tell me what I'm missing in solving this algorithm? One problem I have is that my first if statement inside the nested loop is not evaluating, but I don't know why it wouldn't evaluate.

Here is the description of the problem:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2. The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].

Output: [-1,3,-1]

Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

link to original description

And here is my code so far:

 var nums1 = [4,1,2];
 var nums2 = [1,3,4,2];

  var nextGreaterElement = function(findNums, nums) {
    var holder = [];

    for (var i = 0; i < findNums.length; i++) {

     //loop through the 2nd array starting at the index of the first loop's current item. 

      for (var j = nums.indexOf(findNums[i]); i < nums.length - j; i++) {

        if (nums[j+1] > nums[j]) {
          holder.push(nums[j+1]);
          break;
        } 

        if (nums[nums.length]) {
          holder.push(-1);
        }
      }
    }
    return holder;
};

nextGreaterElement(nums1, nums2)

Thanks for any help.

i < nums.length - j; i++ Are you sure you didn't mean j < nums.length - i; j++? Or something similar. Basically, I assume you don't want to increment i in your j loop. — Mike Cluck
– Mike Cluck, Commented Apr 26, 2017 at 20:37

hk6279 · Accepted Answer · 2017-04-27 07:40:00Z

1

Problem: Updating variant i, but not variant j in inner loop (j-loop)

Missing: Debugging Effort

Problem Description

Theoretically, your code design should compare each value in nums1 to related parts of nums2. So, it would turn to a outer for-loop to loop on nums1 and an inner for-loop to loop related parts of nums2 for each iteration of the outer for-loop.

In your code, variant i is the index pointer for findNums (i.e. nums1) while variant j is the index pointer for nums (i.e. nums2). Variant i is always updating in both inner for-loop and outer for-loop while variant j is set once for every iteration of outer for-loop. This contradict to what you are suppose to do.

Debugging (Your Missing Work)

Find a piece of paper and a pen. Sit down, dry run the program and keep recording related info (variant i, variant j, findNums[i], nums[j], ...), you could figure out why your code is not working.

Possible Solution

var nextGreaterElement = function(findNums, nums) {
    var holder = [];

    for (var i = 0; i < findNums.length; i++) {
      var hasNextGreaterElement = false;
      // try to serach for next greater element
      for (var j = nums.indexOf(findNums[i])+1; j < nums.length; j++) {
        // handle case for next greater element is found
        if (nums[j] > findNums[i]) {
          holder.push(nums[j]);
          hasNextGreaterElement = true;
          break;
        }
      }
      // handle case for next greater element is not found
      if (!hasNextGreaterElement) {
          holder.push(-1);
      }
    }
    return holder;
};

var findNums=[4,1,2];
var nums=[1,3,4,2];
console.log(nextGreaterElement(findNums, nums));

edited Apr 27, 2017 at 7:40

answered Apr 27, 2017 at 7:12

hk6279

1,8792 gold badges22 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jdag Over a year ago

Thanks for your help. I see a few places where I went wrong - defining variables in my inner loop, and placing the 2nd if statement outside the scope of the nested loop. One question I still have though, is, if the 2nd if statement remains inside the nested loop, why wouldn't it push a -1 to the holder array? Since the first if statement does not evaluate, wouldn't it evaluate the 2nd statement and push a -1 since the hasNextGreaterElement is false?

hk6279 Over a year ago

@JackDagley The 2nd if-statement never evaluated possibly because the value nums[nums.length] is not convertible to true. Try to use debugging tools, like firebug, to display value at runtime.

Wesley · Accepted Answer · 2017-04-26 20:47:39Z

You need to sort the array you are looking in to make it easier to find the number. If the array get big you might want a search algorithm to find the index in the array faster. With the array that is going to be looked in sorted you can grab the next number as the number that is one larger and check to see if you are at the end of the array. If you don't do this check the function will error when you can't find the number or when there is no number larger. Finally your second if statement didn't make sense. So I am checking to make sure that we are at the end of the array before outputting the -1 in the array.

    var nextGreaterElement = function(findNums, nums) {
    var holder = [];
    //Should sort the array to make sure you get the next largest number
    nums = nums.sort();
    for (var i = 0; i < findNums.length; i++) {

     //loop through the 2nd array starting at the index of the first loop's current item. 

      //for (var j = nums.indexOf(findNums[i]); i < nums.length - j; i++) {
        for(var j = 0; j < nums.length; j++){
          //check for value in array and make sure the value is not at the end
          if (findNums[i] == nums[j] && j != nums.length - 1) {
            holder.push(nums[j+1]);
            break;
          } 
        //check for the last element in array if so output -1
        if (j == nums.length - 1) {
          holder.push(-1);
        }
      }
    }
    return holder;
};

Collectives™ on Stack Overflow

Algorithm: Next Greater Element I (from leetcode)

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related