496-next-greater-element-i

496. Next Greater Element I (Easy) (https://leetcode.com/problems/next-greater-element-i/)

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1. Return an array of length nums1.length such that ans[i] is the next greater element as described above. Constraints: - 1 <= nums1.length <= nums2.length <= 1000 - 0 <= nums1[i], nums2[i] <= 10^4 - All integers in nums1 and nums2 are unique.

• All the integers of nums1 also appear in nums2. Follow up: Could you find an O(nums1.length + nums2.length) solution?

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const stack: number[] = []; // LIFO; хранит числа, ещё не нашедшие next greater
  const nextGreaters: Record<number, number> = {}; // где ключ — число из nums2, значение — его next greater element
 
  for (let i = 0; i < nums2.length; i++) {
    const curr = nums2[i];
 
    // При новом числе — пока оно больше вершины стека, выталкивай вершину и записывай в map map[вершина] = новое_число
    while (curr > stack[stack.length - 1] && stack.length > 0) {
      nextGreaters[stack.pop()!] = curr;
    }
 
    stack.push(curr);
  }
 
  const result = [];
  for (let i = 0; i < nums1.length; i++) {
    result.push(nextGreaters[nums1[i]] ?? -1);
  }
 
  return result;
}
 
// Local check:
console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2])); // [-1,3,-1]
console.log(nextGreaterElement([2, 4], [1, 2, 3, 4])); // [3,-1]

Example 1:
 
    Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
    Output: [-1,3,-1]
    Explanation:
      4 is in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
      1 is in nums2 = [1,3,4,2]. The next greater element is 3.
      2 is in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
 
  Example 2:
 
    Input: nums1 = [2,4], nums2 = [1,2,3,4]
    Output: [3,-1]
    Explanation:
      2 is in nums2 = [1,2,3,4]. The next greater element is 3.
      4 is in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

leetcode