Leetcode discuss: 496. Next Greater Element I

 Here is the link. 

Second practice - C# - reading skill challenge

Dec. 22, 2020
It was so challenge for me to figure out how the test case works. The problem is related to my reading skills.

Case study
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]

I just could not figure out why 2 in the first array called nums1 has no greater element. I thought about 2's index in nums1 is 1, and then check nums2's array starting from index = 1 to find greater element compared to 2, 4 should be the answer.

I read the problem statement again and again, 2 is in num2 array at position of 3, last element, no right side elements in num2.

I was so patient to figure out this interesting challenge in my Leetcode premium online assessment Facebook mock session. Patient is important.

Original statement given in Leetcode
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2.

I think that it should rephrase to make it easier to understand.
"its right" refers to the right side of x's index position in nums2. It is not x's index position in nums1.

Time complexity:
O(M), M is the size of array nums2
Space complexity:
O(M), M is the size of array nums2

public class Solution {
    public int[] NextGreaterElement(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null || nums1.Length > nums2.Length)
            return new int[0];
        
        var length1 = nums1.Length; 
        var length2 = nums2.Length; 
        
        var nextGreater = new int[length1];
        
        var map = new Dictionary<int, int>(); 
        for(int i = 0; i < length2; i++)
        {
            map.Add(nums2[i], i);    
        }
        
        for(int i = 0; i < length1; i++)
        {
            nextGreater[i] = -1; 
        }
        
        for(int i = 0; i < length1; i++)
        {
            var current = nums1[i];
            
            for(int j = map[current] + 1; j < length2; j++)
            {
                if(nums2[j] > current)
                {
                    nextGreater[i] = nums2[j];
                    break;
                }
            }
        }
        
        return nextGreater; 
    }
}